ブルームフィルタ（Bloom Filter）
「確実にない」か「たぶんある」かを超高速に判定する確率的データ構造。偽陽性は許容するが偽陰性は絶対に起きない。
📌ブルームフィルタとは
ブルームフィルタは、1970年にBurton Howard Bloomが提案した確率的データ構造です。「ある要素が集合に含まれているか？」という問いに対し、「確実にない」か「たぶんある」かを超高速・超省メモリで判定します。
最大の特徴は、偽陽性（False Positive）は起こりうるが、偽陰性（False Negative）は絶対に起こらないということです。つまり「ない」と答えたら本当にない。「ある」と答えたときだけ、まれに間違える可能性があります。
メモリ効率が極めて高く、1要素あたりわずか数ビットで管理できます。HashSetなら1要素数十〜数百バイト必要なのに対し、ブルームフィルタは数ビットで済みます。この圧倒的な省メモリ性が、大規模システムで採用される理由です。
🎯このツールの値は何を表している？
上のツールで挿入する「apple」「banana」などは任意の文字列キーです。ブルームフィルタは「このキーがセットに含まれているか？」を高速・省メモリで判定する確率的データ構造です。実際のシステムでは以下のようなデータがキーとして使われます。
Google Chromeのセーフブラウジング。数百万件の危険URLをブルームフィルタに登録し、ユーザーがアクセスするたびにO(1)でチェック。ブルームフィルタが「ない」と言えば100%安全（偽陰性なし）。「ある」と言った場合だけサーバーに問い合わせて精密判定する。全URLリストをダウンロードせずに数MBで判定できるのがポイント。
メールサーバーがスパム送信元のメールアドレスを数百万件ブルームフィルタに登録。受信のたびにO(1)でチェック。偽陽性（正常なメールがスパム判定される）が稀に起きるが、確率は0.1%以下に設定可能。
Mediumの「あなたへのおすすめ」。ユーザーが読んだ記事IDをブルームフィルタに登録し、おすすめ表示時に「この記事は読んだか？」をO(1)で判定。数千件の既読情報を数KBで保持できる。既読記事が再表示されるよりも、たまに未読記事がスキップされる方がマシ（偽陽性の許容）。
Cassandra/HBaseのSSTファイル。ディスク上のデータファイルに目的のキーが存在するかをブルームフィルタで事前チェック。「ない」とわかればディスクI/Oを完全にスキップできる。数テラバイトのデータでも、不要なディスク読み込みを90%以上削減。
なぜ文字列でなくても良い？
ブルームフィルタの入力は最終的にハッシュ関数に通すだけなので、文字列に限らず整数・バイト列・オブジェクトなど何でもキーにできます。ハッシュインデックスと同様、ハッシュ関数が内部で文字列→整数の変換を行います。このツールでは文字列を使っていますが、実際には任意のデータ型が対象です。
ブルームフィルタのパラメータの意味
上のツールのスライダーでm（ビット配列サイズ）とk（ハッシュ関数数）を変えて、偽陽性率の変化を観察してみてください。
💡 tip：「"apple", "banana", "cherry" を挿入した後、"grape" や "melon"（挿入していない単語）を検索してみてください。ほとんどは "存在しない" と正しく判定されますが、まれに "おそらく存在する"（偽陽性）と誤判定されることがあります。ビット配列サイズを小さくすると偽陽性が起きやすくなります。」
⚙️仕組み
1. ビット配列 + 複数ハッシュ関数
ブルームフィルタはm個のビット（0/1）からなる配列と、k個の独立したハッシュ関数で構成されます。初期状態ではすべてのビットが0です。
2. 挿入の流れ
キーを挿入すると、k個のハッシュ関数がそれぞれビット位置を計算し、その位置のビットを1にします。例えば "apple" を3つのハッシュ関数でハッシュすると、位置2, 5, 8が得られ、それらを1にします。
3. 検索の流れ（偽陽性の仕組み）
検索時も同じk個のハッシュ関数でビット位置を計算します。すべてのビットが1なら「たぶんある」、1つでも0なら「確実にない」と判定します。
偽陽性が起きる理由：異なるキーが同じビット位置を使うことがあります。例えば "apple" と "banana" を挿入した後に "grape" を検索すると、"grape" のハッシュ位置がたまたま "apple" と "banana" によって既に1になっていた位置と一致し、「たぶんある」と誤判定されることがあります。
✅特徴
- 🎲確率的判定：「確実にない」は100%正確。「たぶんある」は偽陽性の可能性がある。完全に正確ではないが、その代わりに超高速・超省メモリ。
- 🚫偽陽性あり、偽陰性なし：挿入していないキーを「ある」と誤判定することはあるが、挿入したキーを「ない」と誤判定することは絶対にない。この非対称性が強力。
- 🗑️削除不可（通常のブルームフィルタ）：ビットを0に戻すと他のキーの判定に影響するため、通常は削除できない。削除が必要な場合はCounting Bloom Filterを使う。
- 💾超メモリ効率：1要素あたり約10ビット（約1.2バイト）で1%の偽陽性率を実現。HashSetの数十分の1〜数百分の1のメモリで済む。
- ⚡O(k) の挿入・検索：k個のハッシュ関数を計算するだけ。要素数nに関係なく一定時間で完了。kは通常3〜7程度の小さな定数。
🛠️ユースケース
📖用語解説
📋手順
挿入（Insert）
- キー（例："apple"）を受け取る
- k個のハッシュ関数を適用し、k個のビット位置を計算する（例：h1("apple")=2, h2("apple")=5, h3("apple")=8）
- 計算された各ビット位置を1にセットする（すでに1なら変化なし）
- 完了。キー自体は保存しない（ビット配列のみ更新）
検索（Lookup）
- キー（例："apple"）を受け取る
- 挿入時と同じk個のハッシュ関数で、k個のビット位置を計算する
- 計算された各ビット位置を確認する
- 1つでも0のビットがあれば → 「確実に存在しない」（100%正確）
- すべてのビットが1であれば → 「おそらく存在する」（偽陽性の可能性あり）
偽陽性が起きる具体例
ビット配列サイズ m=8、ハッシュ関数 k=2 の場合を考えます。
Step 1: "apple" を挿入 → h1=1, h2=4 → ビット位置1,4を1にセット
Step 2: "banana" を挿入 → h1=3, h2=6 → ビット位置3,6を1にセット
Step 3: "grape" を検索 → h1=3, h2=4 → ビット位置3(=1),4(=1) → すべて1!
結果: "grape" は挿入されていないのに「たぶんある」と判定される。位置3は "banana" が、位置4は "apple" が埋めていた。これが偽陽性。
⚖️Bloom Filter vs HashSet vs B-Tree
100万件のデータを管理する場合のメモリ使用量の違いに注目してください。ブルームフィルタは圧倒的に少ないメモリで動作します。
| 特性 | Bloom Filter | HashSet | B-Tree |
|---|---|---|---|
| メモリ（100万件） | ~1.2 MB | ~64 MB | ~32 MB |
| 検索速度 | O(k) 定数 | O(1) 平均 | O(log n) |
| 挿入速度 | O(k) 定数 | O(1) 平均 | O(log n) |
| 削除 | 不可 | O(1) | O(log n) |
| 正確性 | 偽陽性あり | 100%正確 | 100%正確 |
| 要素の列挙 | 不可 | 可能 | 可能（ソート順） |
| 1要素あたり | ~10 bit | ~64 byte | ~32 byte |
