ブルームフィルタを使う方法

问题

ある要素が巨大な集合に含まれるかどうかを判定したいが、集合全体をメモリに保持するコストが高すぎる状況です。

前提条件

• ハッシュ関数の理解
• 確率的データ構造に関する知識

ステップ

1. 1. Size the filter

   Choose the expected number of items (n) and the desired false positive rate (p). The optimal number of bits (m) and hash functions (k) are derived from these: m = -n*ln(p)/(ln(2)^2), k = (m/n)*ln(2). For 1 million items at 1% FPR, you need about 1.19 MB.

   入力

   n=1M, p=0.01

   输出

   m=9.6M bits, k=7

2. 2. Add items to the filter

   To add an item, compute k hash values and set the corresponding k bits in the bit array. The same item always sets the same bits. Adding is O(k) and never fails.

   入力

   add 'apple'

   输出

   set bits at h1..h7

3. 3. Test membership

   To test if an item is in the set, compute the k hash values and check if all corresponding bits are set. If any bit is 0, the item is definitely not in the set. If all bits are 1, the item is probably in the set (with false positive rate p). Bloom filters never produce false negatives.

   入力

   test 'banana'

   输出

   probably present / definitely absent

期待される結果

偽陰性なしに集合への所属を判定でき、偽陽性率を制御できる、メモリ効率の良いデータ構造。

よくあるエラー

Treating a positive result as certain

Bloom filters have false positives. A positive means 'probably in the set'. Always verify with the actual data if exactness is required.

Too many items for the filter size

If the number of items exceeds the design capacity, the false positive rate increases. Re-size the filter or use a counting Bloom filter.

トラブルシューティング指引

• If the false positive rate is too high, increase the bit array size or the number of hash functions.
• Bloom filters cannot remove items. Use a counting Bloom filter if deletion is needed.

セキュリティ上の制限

• Bloom filters are probabilistic. Never use them for security-critical membership decisions without a fallback verification.
• This is an educational explanation.