ビット配列へ複数の印を付ける
標準的なBloomフィルタは、最初はすべて0のビット配列と複数のハッシュ計算を使います。キーを追加するとき、そのキーから得られる複数の位置を1にします。元のキーや値そのものは保存しません。検索では同じ位置を調べ、一つでも0があれば、そのキーは追加されていません。すべて1の場合は、他のキーが付けた印かもしれないため、「存在する可能性がある」という答えになります。
小さな例で偽陽性を見る
8ビットの配列を考え、キーAが位置1と4を、Bが位置3と6を1にしたとします。未登録のCが位置1と6へ対応すると、両方が既に1なので存在候補と判定されます。これは偽陽性です。一方、Dが位置2と4へ対応し、位置2が0なら確実に未登録と判定できます。追加後にビットを壊さず、同じハッシュ規則を使うという条件下では、登録済みキーを未登録と答える偽陰性は生じません。
領域・個数・ハッシュ回数の関係
登録数に対してビット数が少ないと、1が増えて偽陽性が出やすくなります。ハッシュ回数を増やすと検索時の確認は増えますが、追加時により多くのビットも1になります。そのため回数を増やし続ければ必ず改善するわけではありません。一般的な近似モデルでは、ビット数m、登録数n、ハッシュ数kから偽陽性率を見積もりますが、ハッシュの独立性などの仮定と、実際の登録数を確認して容量設計します。
確定検索の前に置く
たとえばストレージへ問い合わせる前にBloomフィルタを見て、未登録と分かるものを省略します。存在候補と答えた場合には、本体で確定検索を行います。アクセス許可のように誤判定が許されない最終判断を、フィルタだけに任せてはいけません。また標準のビット配列では、あるキーを削除するために印を0へ戻すと、同じ印を共有する別のキーを壊します。削除が必要ならCounting Bloomフィルタなど別の設計を検討します。