ハッシュ関数は配列上の各位置を同じ確率で選択するものとする。セットされない確率は次のようになる。セットされない確率は次のようになる。ある確率は次のようになる。なっている確率は次の通り。.あるメンバーでないことが分かっている要素がメンバーかどうかをテストするとする。なっている確率は上記の通りである。なっている確率、すなわちブルームフィルタが誤ってある要素がメンバーであると判定してしまう確率は次のようになる。.明らかに、m(配列のビット数)が大きければ偽陽性発生率は低くなり、n(追加要素数)が大きければ偽陽性発生率は高くなる。k(ハッシュ関数の個数)は次のようになる。このときの偽陽性発生確率は次の通り。.特性[編集]ハッシュテーブルと大きく異なり、一定の長さのブルームフィルタで、任意の要素数を持つ集合を表現できる。いくらでもメンバーを追加することができる。埋めていくだけであるから、失敗することは無い。メンバー数が増えると偽陽性発生率も上がっていく。2つの集合から、同じハッシュ関数群を使って同じサイズのブルームフィルタをそれぞれ作ったとしよう。ビット配列は、2つの集合の和集合を表現するブルームフィルタと同じものである。すると、2つの集合の積集合を表すブルームフィルタ(と同じようなもの)を作ることができるが、この場合、積集合から一から作成したものより偽陽性の確率が大きくなってしまう。ブルームフィルタの実装の一種で、再生成せずに要素を削除できるものである。ビットのカウンタに拡張されている。場合と見なすこともできる。要素の追加は各配列要素のインクリメントになり、参照は各配列要素がゼロでないことを確認することになる。削除する場合、対応する配列要素のカウンタをデクリメントすればよい。カウンタのオーバフローが発生する問題が考えられるため、カウンタサイズはそのようなことがなるべく発生しないように十分大きくしなければならない。オーバフローが発生したら、ブルームフィルタ本来の偽陽性発生がありうるという性質に基づき、そのカウンタを要素の追加や削除で変更せず、最大値のままにしておくのがよいとされている。ブルームフィルタに追加した要素と関連させた値を持つ連想配列を設計した。ブルームフィルタと同様、このデータ構造も空間効率が良く、偽陽性発生の可能性がある。偽陽性は、キー値がマッピングされていないのに値が返される場合である。マッピングされているキー値に対しては不正な値を返すことはない。