ブルームフィルタ
ハッシュ関数は配列上の各位置を同じ確率で選択するものとする。要素をひとつ追加する際、あるビットが特定のハッシュ関数で 1 にセットされない確率は次のようになる。
1 − 1 m {\displaystyle 1-{\frac {1}{m}}} .
従って k 個のハッシュ関数のいずれによっても、1つのビットが 1 にセットされない確率は次のようになる。
( 1 − 1 m ) k {\displaystyle \left(1-{\frac {1}{m}}\right)^{k}} .
n 個の要素を追加した状態で、あるビットがいまだに 0 である確率は次のようになる。
( 1 − 1 m ) k n {\displaystyle \left(1-{\frac {1}{m}}\right)^{kn}} ;
したがって、逆に 1 となっている確率は次のとおり。
1 − ( 1 − 1 m ) k n {\displaystyle 1-\left(1-{\frac {1}{m}}\right)^{kn}} .
ある要素ではないと分かっているデータに対してそれが集合の要素であるかどうかをテストしたとする。このときハッシュ関数で得られる k 個のビットそれぞれが 1 となっている確率は上記の通りである。