ブルームフィルタは少数の誤答と引き換えに極めて小さなメモリ使用量を手に入れた

項目の集合が膨大な場合、すべてのキーを保存することは不可能だが、それでもあるものが集合に含まれるかどうかを知る必要がある。ブルームの例は50万語の辞書で、単語の10%だけが高コストなハイフネーション規則を使う。賢明なチェックはディスクアクセスを避けることだったが、辞書は利用可能なメモリ内で誤りなくハッシュ化するには大きすぎた。

ブルームフィルタはビット配列といくつかのハッシュ関数でこれを解決する。項目を追加するとそれらの位置のビットが設定され、検査ではそれらがすべて設定されているかを問い合わせる。いずれかがゼロなら、その項目は確実に存在しないため偽陰性はない。すべてが設定されていれば、その項目は集合に含まれるかもしれないし、他の項目と衝突しただけかもしれず、偽陽性が生じる。

誤りが片側性で調整可能であるため、構造は小さく保たれながら、ほとんどの不要なディスク読み取りを排除できる。誤りなしのハッシュが必要とするサイズのわずか18%のハッシュ領域で、ディスクアクセスの87%が排除され、要素あたり10ビット未満で約1%の偽陽性率が得られる。

ビット配列に「かもしれない」と言わせ、決して誤って「いいえ」と言わせない

コストが追加のチェックだけなら偽陽性は許容できるが、誤った「いいえ」はデータを失うことになる。

いくつかのハッシュ関数を備えたビット配列は、要素あたり数ビットで集合への所属を保存する。

実際の集合を保存せずに、ほとんどの高コストなディスクやネットワークのルックアップを排除する。

「はい」と言う小さな確率が許容でき、誤った「いいえ」が許容できないなら、片側性の誤りを意図的に受け入れるべきである。少数の偽陽性を許すことが、膨大な集合をメモリに収める唯一の方法であることが多い。

ブルームフィルタは高コストなルックアップを避けるためにデータベース、キャッシュ、スペルチェッカー、ネットワークルーティングに広がり、PostgreSQLやApache CassandraからChromiumや大規模キャッシュに至るシステムに現れている。空間のために片側性の誤りを受け入れるという根底の工夫は、今やコンピュータシステム全体における標準的なプリミティブである。