Bloom Filter：一个靠"撒谎"节省空间的聪明数据结构
假设你在做一个爬虫，URL 去重是每天都要面对的问题。最直觉的方案是用 HashSet，但当地址库膨胀到十亿级，内存直接爆掉。有人就想：能不能接受一点误判，换来数量级的空间压缩？Bloom Filter 就是这个思路的产物。
它底层就是一个长度为 m 的位数组，全初始化为 0，再配 k 个独立的哈希函数。插入一个元素时，用 k 个哈希函数算出 k 个位置，全部置 1。查询时同样算出 k 个位置，只要有一个是 0，这个元素一定不在集合里——这是确定性结论；但如果全为 1，只能说"可能在"，因为那些 1 位可能被其他元素碰巧填上了。所以 Bloom Filter 的核心特性是：没有假阴性，但有假阳性。
这个"只可能多报，不会漏报"的性质让它特别适合做前置过滤器。Chrome 用它检查恶意 URL，Cassandra 用它减少磁盘 IO，Bitcoin Core 也用它在节点间同步时先过滤不需要的交易块。当 Bloom Filter 说"不在"，你就可以完全信任这个判断，直接跳过后续操作；只有当它说"可能在"时，才需要去精确数据结构里二次确认。
空间效率有多夸张？1% 误判率下，每个元素只需要约 9.6 bit，对比 HashSet 的几十字节，差了两个数量级。误判率随 m 增大而下降、随 n 增大而上升，k 的最优选择大约是 (m/n)·ln2，这可以从最小化假阳性概率的推导中得出。
Bloom Filter 最明显的短板是删除困难——把某元素对应的位清零会影响其他共享这些位的元素。 还有一个常被忽略的性质：多个相同参数的 Bloom Filter 可以直接按位 OR 合并，非常适合分布式场景下各节点独立构建后再汇总。
#CS
假设你在做一个爬虫，URL 去重是每天都要面对的问题。最直觉的方案是用 HashSet，但当地址库膨胀到十亿级，内存直接爆掉。有人就想：能不能接受一点误判，换来数量级的空间压缩？Bloom Filter 就是这个思路的产物。
它底层就是一个长度为 m 的位数组，全初始化为 0，再配 k 个独立的哈希函数。插入一个元素时，用 k 个哈希函数算出 k 个位置，全部置 1。查询时同样算出 k 个位置，只要有一个是 0，这个元素一定不在集合里——这是确定性结论；但如果全为 1，只能说"可能在"，因为那些 1 位可能被其他元素碰巧填上了。所以 Bloom Filter 的核心特性是：没有假阴性，但有假阳性。
这个"只可能多报，不会漏报"的性质让它特别适合做前置过滤器。Chrome 用它检查恶意 URL，Cassandra 用它减少磁盘 IO，Bitcoin Core 也用它在节点间同步时先过滤不需要的交易块。当 Bloom Filter 说"不在"，你就可以完全信任这个判断，直接跳过后续操作；只有当它说"可能在"时，才需要去精确数据结构里二次确认。
空间效率有多夸张？1% 误判率下，每个元素只需要约 9.6 bit，对比 HashSet 的几十字节，差了两个数量级。误判率随 m 增大而下降、随 n 增大而上升，k 的最优选择大约是 (m/n)·ln2，这可以从最小化假阳性概率的推导中得出。
Bloom Filter 最明显的短板是删除困难——把某元素对应的位清零会影响其他共享这些位的元素。 还有一个常被忽略的性质：多个相同参数的 Bloom Filter 可以直接按位 OR 合并，非常适合分布式场景下各节点独立构建后再汇总。
#CS
