ブルームフィルタ
全てが 1 となっている確率、すなわちブルームフィルタがそのデータが集合の要素であると誤って判定してしまう確率は次のようになる。
( 1 − ( 1 − 1 m ) k n ) k ≈ ( 1 − e − k n / m ) k {\displaystyle \left(1-\left(1-{\frac {1}{m}}\right)^{kn}\right)^{k}\approx \left(1-e^{-kn/m}\right)^{k}} .
明らかに、m(配列のビット数)が大きければ偽陽性の発生率は低くなり、n(追加する要素数)が多くなれば偽陽性の発生率は高くなる。いま m と n が決まっているとき、偽陽性発生率を最小にする k(ハッシュ関数の個数)は次のようになる。
k = m n ln  2 ≈ 9 m 13 n ≈ 0.7 m n {\displaystyle k={\frac {m}{n}}\ln 2\approx {\frac {9m}{13n}}\approx 0.7{\frac {m}{n}}} ,
このときの偽陽性の発生確率は次の通り。
( 1 2 ) k ≈ 0.6185 m / n {\displaystyle \left({\frac {1}{2}}\right)^{k}\approx {0.6185}^{m/n}} .
空のブルームフィルタは全てのビットが 0 に設定された m ビットのビット配列である。また、同時に k 個のハッシュ関数が定義されており、それぞれがキー値を m 個の配列位置のいずれかにマッピングする。
幅広い出力をする良いハッシュ関数では、その生成するハッシュ値の各ビットの値は相互の関連がほとんどないはずなので、ハッシュ値を適当なビット位置で分割して複数の異なるハッシュ関数として使うことができる。あるいは、ハッシュ関数の内部で使われる初期値をk 個の異なる値(例えば 0, 1, ...... k-1)にしたり、それらの値をキー値に加算(あるいは連結)することで k 種類のハッシュ関数としたりできる。
要素を追加するには、それを k 個のハッシュ関数に入力して k 個の配列インデックスを得る。そして、それらの位置のビットを全て 1 にする。
ある要素がその集合に含まれるかどうかを調べる(クエリ)には、それを k 個のハッシュ関数に入力して k 個の配列への添字を得る。それらの位置にあるビット群のどれかひとつでも 0 である場合は、その要素はその集合には含まれていない。