布隆过滤器：用概率换空间的魔法
你有没有想过，Chrome 是怎么在几十亿个恶意 URL 里快速判断一个网址"可能有毒"的？它不可能把所有恶意 URL 都装进内存逐条比对——那就太蠢了。答案是它用了一个叫布隆过滤器的东西，根本不存原始数据，就能告诉你"这个 URL 大概有问题"或者"这个 URL 绝对没问题"。
做 Burton Bloom 在 1970 年提出的这个结构，核心想法极其简洁：用一个 m 位的位数组加 k 个哈希函数。插入元素时，把元素送进 k 个哈希函数，得到的 k 个位置全部置 1。查询时同理，算出 k 个位置，如果全是 1，说明"可能在"；只要有一个是 0，就可以断言"绝对不在"。
这里的"可能在"是关键。因为不同元素可能哈希到相同的位置，所以数组里某些位被置 1 可能是别的元素干的——这就是假阳性。但反过来说，假阴性永远不会发生：如果元素确实插入过，那它对应的 k 个位一定都是 1，不会凭空变回 0。
这个性质让布隆过滤器非常适合做"前置过滤器"：先用地毯式的布隆过滤器筛一遍，如果能确定"不在"，就省去了后续昂贵的查询（比如磁盘读取或网络请求）；如果判断"可能在"，再去做确认。Cassandra 用它避免了对 SSTable 的无效磁盘读取，Bitcoin 用它过滤不相关的交易，SpamAssassin 用它快速排白名单，原理都一样——用极小的内存代价换掉大部分无效查询。
假阳性率怎么控制？数学推导的结果是：当位数组大小为 m、哈希函数个数为 k、已插入 n 个元素时，假阳性概率大约是 (1 - e^(-kn/m))^k。这揭示了一个反直觉的结论——哈希函数不是越多越好。k 太大，每位组被淹没，所有位都变成 1，不管查什么都返回"可能在"；k 太小，冲突集中，假阳性率也高。最优 k 大约是 (m/n) × ln2。比如你给每个元素分配 10 位，最优 k ≈ 7。
还有一个容易踩的坑：布隆过滤器不支持删除。把某元素对应的 k 个位清零，可能会影响其他元素。想要支持删除，得用计数布隆过滤器（Counting Bloom Filter），把每一位扩展成几位的计数器，插入加 1，删除减 1，但空间开销也跟着涨。
下次你看到某个系统说"O(1) 判否、概率判是"，大概率背后就站着一个布隆过滤器。
#CS
你有没有想过，Chrome 是怎么在几十亿个恶意 URL 里快速判断一个网址"可能有毒"的？它不可能把所有恶意 URL 都装进内存逐条比对——那就太蠢了。答案是它用了一个叫布隆过滤器的东西，根本不存原始数据，就能告诉你"这个 URL 大概有问题"或者"这个 URL 绝对没问题"。
做 Burton Bloom 在 1970 年提出的这个结构，核心想法极其简洁：用一个 m 位的位数组加 k 个哈希函数。插入元素时，把元素送进 k 个哈希函数，得到的 k 个位置全部置 1。查询时同理，算出 k 个位置，如果全是 1，说明"可能在"；只要有一个是 0，就可以断言"绝对不在"。
这里的"可能在"是关键。因为不同元素可能哈希到相同的位置，所以数组里某些位被置 1 可能是别的元素干的——这就是假阳性。但反过来说，假阴性永远不会发生：如果元素确实插入过，那它对应的 k 个位一定都是 1，不会凭空变回 0。
这个性质让布隆过滤器非常适合做"前置过滤器"：先用地毯式的布隆过滤器筛一遍，如果能确定"不在"，就省去了后续昂贵的查询（比如磁盘读取或网络请求）；如果判断"可能在"，再去做确认。Cassandra 用它避免了对 SSTable 的无效磁盘读取，Bitcoin 用它过滤不相关的交易，SpamAssassin 用它快速排白名单，原理都一样——用极小的内存代价换掉大部分无效查询。
假阳性率怎么控制？数学推导的结果是：当位数组大小为 m、哈希函数个数为 k、已插入 n 个元素时，假阳性概率大约是 (1 - e^(-kn/m))^k。这揭示了一个反直觉的结论——哈希函数不是越多越好。k 太大，每位组被淹没，所有位都变成 1，不管查什么都返回"可能在"；k 太小，冲突集中，假阳性率也高。最优 k 大约是 (m/n) × ln2。比如你给每个元素分配 10 位，最优 k ≈ 7。
还有一个容易踩的坑：布隆过滤器不支持删除。把某元素对应的 k 个位清零，可能会影响其他元素。想要支持删除，得用计数布隆过滤器（Counting Bloom Filter），把每一位扩展成几位的计数器，插入加 1，删除减 1，但空间开销也跟着涨。
下次你看到某个系统说"O(1) 判否、概率判是"，大概率背后就站着一个布隆过滤器。
#CS
