布隆过滤器：用1%内存判断“这个东西见过吗”

一、问题从哪里来

做爬虫时，同一个 URL 被重复抓取几十次，既浪费带宽还可能被目标站封 IP；做缓存时，大量根本不存在的 key 穿透到数据库，直接把 DB 打垮；做消息推送时，同一条消息被重复下发，用户体验极差。这些场景的共同点是：需要快速判断“某个元素之前是否出现过”，而且数据量巨大，动辄上亿。

最直观的做法是把所有元素塞进 HashSet。假设有 1 亿个 URL，每个平均 64 字节，光存字符串就要 6.4GB，还没算哈希表本身的开销。内存撑不住，怎么办？

二、布隆过滤器是什么

布隆过滤器（Bloom Filter）是一种空间效率极高的概率型数据结构，由 Burton Howard Bloom 在 1970 年提出。它的结构很简单：一个很长的二进制位数组，加上 k 个哈希函数。

它的结论只有两种：“一定不在集合中”，或者“可能在集合中”——注意，没有“一定在”。

写入时，把元素分别送入 k 个哈希函数，得到 k 个下标，把位数组上这些位置都置为 1。查询时，同样算出 k 个下标：如果其中有一个位置是 0，说明这个元素一定没被写入过；如果 k 个位置全是 1，说明这个元素“可能”被写入过——也可能是其他元素恰好把这些位置都置成了 1，这就是误判（false positive）。

布隆过滤器永远不会漏判，但会有一定概率误判。工程上我们通过调参，把误判率控制在可接受的范围，比如 1%。

三、误判率与参数选择

设位数组长度为 m，元素个数为 n，哈希函数个数为 k。某个特定位在全部写入完成后仍为 0 的概率约为 e^(-kn/m)，那么查询一个不存在的元素时，k 个位置恰好全为 1 的概率约为 p = (1 - e^(-kn/m))^k。

当 k = (m/n)·ln2 时误判率最低。实际使用中有个经验公式：想把误判率控制在 1%，每个元素大约需要 9.6 个 bit；控制在 0.1%，大约需要 14.4 个 bit。也就是说，1 亿个元素、1% 误判率，只需要约 120MB 内存，是 HashSet 方案的几十分之一。

四、一个 Java 示例（Guava）

Google 的 Guava 库提供了开箱即用的布隆过滤器：

BloomFilter<String> filter = BloomFilter.create(
        Funnels.stringFunnel(StandardCharsets.UTF_8),
        100000000, 0.01);
filter.put("https://example.com/page1");
filter.mightContain("https://example.com/page1"); // true：可能存在
filter.mightContain("https://example.com/page2"); // 大概率 false：一定不存在

注意 API 的名字就叫 mightContain——“可能包含”，时刻提醒你它存在误判。

五、典型应用场景

1. 缓存穿透防护：在缓存前面加一层布隆过滤器，拦截掉绝大部分不存在的 key，只有“可能存在”的请求才打到数据库。
2. 爬虫 URL 去重：已抓取的 URL 写入布隆过滤器，新 URL 先查一遍，避免重复抓取。
3. 黑名单拦截：把恶意 URL、垃圾邮件发件人放进布隆过滤器，查询极快且内存占用小。
4. LSM-Tree 存储引擎：HBase、Cassandra、RocksDB 都用布隆过滤器快速判断某个 SSTable 里“一定没有”目标 key，从而减少磁盘 IO。

六、不适合的场景

需要精确删除元素的场景不适合——把某一位从 1 改回 0，可能会影响其他元素。需要精确回答“是否存在”的场景也不适合。如果业务需要删除，可以用计数布隆过滤器（Counting Bloom Filter，把位换成计数器）或布谷鸟过滤器（Cuckoo Filter），后者在支持删除的同时空间效率更高。

七、小结

布隆过滤器的精髓，是用“允许小概率误判”换取“极低的内存占用”。当你面临“数据量巨大、内存有限、允许少量误判”的成员查询问题时，它往往是最优雅的答案。先想清楚业务能不能接受误判，再套公式定参数，最后选一个成熟的库落地（Guava、RedisBloom、pybloom-live），基本不会踩坑。