ブルームフィルタ
ハッシュテーブルとは大きく異なり、長さが一定のブルームフィルタにより任意の要素数を持つ集合が表現できる。つまり要素をいくらでも追加できる。要素の追加は単にデータ構造を徐々に 1 で埋めていくだけであるので失敗することは無い。ただし要素数が増えるにつれて偽陽性の発生率も増加する。
2つの集合から、同じハッシュ関数群を使って同じサイズのブルームフィルタをそれぞれ作ったとしよう。それら2つのブルームフィルタのビットごとの OR で得られる m ビットの配列は、2つの集合の和集合を表現するブルームフィルタと一致する。いっぽうでこれら2つのブルームフィルタのビットごとの AND により、2つの集合の積集合を表すブルームフィルタ(のようなもの)を作ることができるが、そのようにして得られるものは、最初から積集合に対して作成されたブルームフィルタに比べれば偽陽性の確率が大きくなる。
以上で、データ構造と検索アルゴリズムが与えられた。新たなキーと値のペアを格納する方法は次の通りである。このとき、プログラムは同じキーに両方の値を設定するような動作は絶対にしてはならない。いま値が 0 の場合には、キーをA0 に追加し、そのキーをB0 も持っていると(嘘を)答えるかどうかを調べる。もしも B0 が(持っているという)偽陽性の結果を返すならば、そのキーを次のレベルの A1 にも追加して、以下同様の処理をする。最終のレベルにまで到達したら、そのキーを単純に挿入する。あるいは値が 1 の場合であれば、この操作を A と B を入れ替えておこなえばよい。
さて、これでキーに対して値 0 または値 1 を正しくマッピングすることができるようになったが、任意の値を格納するにはどうすればよいであろうか? それは簡単である。値の各ビットを返すような Bloomier filter をビット幅の個数だけ作成すればよい。値のビット幅が大きい場合には、値そのものではなくて何らかのハッシュ値を Bloomier filter が返すようにする。n ビットの値を扱う Bloomier filter が必要とする空間量はブルームフィルタ 2n 個分よりも若干大きいだけである。
ブルームフィルタ(英語: Bloom filter)は、1970年に Burton H. Bloom が考案した空間効率の良い確率的データ構造であり、あるデータが集合の要素である(集合に含まれている)かどうかの判定に使われる。ただし判定は正確ではなくて、含まれていないのに含まれていると誤って判定すること偽陽性(false positive)の可能性がある。しかし含まれているものを含まれていないと誤判定すること偽陰性(false negative)はない。なお集合に要素を追加することはできるが、集合から要素を削除することはできない(ただし、拡張をした counting filter であれば削除もできる)。集合に要素を追加していくにつれて偽陽性の可能性は増す。