Bloom filterとは何か、またどのようなトレードオフを行うのか

Question

IT Interview Practice · Accepted Answer

**Bloom filter**は、セットメンバーシップに答える空間効率的な**確率的**構造です。ただし、1つのひねりがあります。**偽陽性**を持つことができますが、**決して偽陰性を持つことはありません**。「確実に存在しない」は確実です。「おそらく存在する」は実際の確認が必要です。

## 動作原理

`m`個のビットと`k`個のハッシュ関数を持つビット配列。アイテムを**追加**するには、ハッシュされた`k`ビットを設定します。**クエリ**するには、その`k`ビットを確認します — いずれかが0の場合、そのアイテムは確実に存在しません。

```text
bits: [0 0 0 0 0 0 0 0]
add "cat":  hash->bits 1,4,6  -> [0 1 0 0 1 0 1 0]
query "dog": hashes to 1,3,6 -> bit 3 is 0 -> DEFINITELY absent
query "cat": all of 1,4,6 set -> "probably present"
```

## Code

```python
class BloomFilter:
    def __init__(self, m, hashes):
        self.bits = [0]*m
        self.m, self.hashes = m, hashes   # list of hash fns
    def add(self, x):
        for h in self.hashes:
            self.bits[h(x) % self.m] = 1
    def __contains__(self, x):            # False = certain; True = maybe
        return all(self.bits[h(x) % self.m] for h in self.hashes)
```

| 操作 | 時間 | スペース |
|---|---|---|
| add | O(k) | O(m)ビット |
| query | O(k) | — |

偽陰性はなく、偽陽性率は`m`（および調整された`k`）が増加するにつれて低下します。

## トレードオフ

- **長所:** 完全なキーを格納する場合と比べて非常に小さいメモリフットプリント；定時間操作。
- **短所:** 偽陽性；**削除できない**（標準Bloom filter）；メンバーをリストできない。

## なぜ重要なのか

Bloom filterは高コストの作業を安価にスキップします。データベース（例：Cassandra、HBase）はそれを使用して、**確実に**ディスク上にないキーのディスク読み取りを回避します。

これは古典的なシステムトレードオフを具現化しています — メモリとI/Oの大幅な削減と引き換えに、小さく制限されたエラー率を受け入れます。

動作原理

Code

トレードオフ

なぜ重要なのか

関連する質問