什么是Bloom filter，它做出了什么trade-off？

Question

Accepted Answer

**Bloom filter**是一个空间效率高的**概率性**数据结构，用于回答集合成员资格查询，但有一个特点：它可能有**假正例**但**永远不会有假负例**。"绝对不存在"是确定的；"可能存在"需要进一步验证。

## 工作原理

一个大小为`m`的bit数组和`k`个hash函数。要**添加**一个元素，设置它hash到的`k`个bit。要**查询**，检查这`k`个bit——如果任何一个为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) bits |
| query | O(k) | — |

没有假负例；假正例率随着`m`（和调整后的`k`）增大而下降。

## Trade-offs

- **优势：** 相比存储完整的key，内存占用极小；常数时间操作。
- **劣势：** 假正例存在；**无法删除**（标准Bloom filter）；无法列举成员。

## 为什么这很重要

Bloom filter能廉价地跳过昂贵的工作：数据库（例如Cassandra、HBase）使用它们来避免对**肯定**不在磁盘上的key进行磁盘读取。

它们体现了经典的系统trade-off——以很小的、有界的误报率为代价换取内存和I/O使用量的巨大减少。