ブルームフィルタ とは？

1億個のURLが集合にあるか判定する場合、HashSetだと数GBのメモリが必要。ブルームフィルタなら同じ要素数で偽陽性率1%でも約120MBで済む。「確実に存在しない」がわかれば十分なケースが多いんだ。存在するかもしれない場合だけ本格的な検索に進む二段階チェックが典型的な使い方だよ

①kビット長のビット配列を0で初期化、②要素追加時にk個のハッシュ関数で位置を計算し、そのビットを1にする、③判定時にk個のハッシュ関数で位置を計算し、すべてのビットが1なら「たぶん含まれる」、1つでも0なら「確実に含まれない」。他の要素のハッシュが偶然同じビットを立てるのが偽陽性の原因だよ

①Chromeのセーフブラウジング（悪意あるURLの判定）、②Cassandraのデータ読み取り（存在しないキーのディスクアクセスを回避）、③Mediumの「この記事はもう読んだ」判定、④ビットコインのSPVノード。キャッシュの前段でDBにないキーへの無駄なクエリを防ぐのも定番の使い方だよ

標準のブルームフィルタは削除できない。ビットを0に戻すと他の要素の判定に影響するから。削除が必要ならCounting Bloom Filter（各ビットをカウンターにする）やCuckoo Filter（削除可能で偽陽性率も低い）を使う。実務ではRedisのBFモジュールやGuavaのBloomFilterが簡単に使えるよ