布隆过滤器 (Bloom Filter)

引言：“可能”机器

假设你想知道一个用户名是否在 10 亿个已注册用户中被占用。

• 哈希表： 需要 20GB+ 内存。太贵了。
• 布隆过滤器： 只需要 100MB。虽然它有时会误报（当用户不存在时说“存在”），但如果它说“不存在”，那就 100% 确定不存在。

布隆过滤器 是一种节省空间的概率型数据结构，专门用于測試一个元素是否属于一个集合。

算法要解决什么问题？

• 输入： 一个元素。
• 输出： False (绝对不在) 或 True (可能在)。
• 承诺： 在成员判定任务中实现海量的内存节省。

核心思想 (直觉版)

想象一个长度为 $M$ 的 位数组 (Bit Array)，初始全是 0。

1. 添加元素： 将元素通过 $K$ 个不同的哈希函数。每个哈希函数会给你一个索引。将位数组中这 $K$ 个索引位置全部设为 1。
2. 查询元素： 同样使用这 $K$ 个哈希函数计算索引。
   • 如果 任何一个 位置是 0：该元素 绝对 没有被添加过。
   • 如果 全部 位置都是 1：该元素 可能 被添加过（也可能是其他元素的哈希值碰巧凑齐了这几个 1）。

为什么要用它？

它充当 昂贵操作 前面的 廉价过滤器。

• 先查布隆过滤器。
• 如果结果是“不在”：跳过昂贵的数据库/磁盘查询。
• 如果结果是“在”：再执行昂贵的查询以进行确认。

典型业务场景

• ✅ 弱密码检测： 检查用户密码是否在包含 1000 万个泄漏密码的黑名单中，而无需将黑名单全部加载到内存。

• ✅ 恶意网址拦截： Google Chrome 使用它快速检查 URL 是否为已知的恶意网站。

• ✅ 数据库性能优化： Cassandra 和 BigTable 使用它来避免在磁盘上搜索不存在的行键。

• ✅ CDN 缓存过滤： 只有当一个資源被请求过至少一次后才进行缓存（防止“一过性”流量浪费缓存空间）。

• ❌ 刪除： 标准布隆过滤器 不支持删除。如果你把某个位设回 0，可能会误删其他共享该位的元素。如果需要删除，请使用 计数布隆过滤器 (Counting Bloom Filter)。

性能与复杂度总结

• 时间： $O(K)$，$K$ 是哈希函数的个数（常数级）。
• 空间： $O(M)$，$M$ 是位数组的大小。通常 1% 误报率下每个元素只需约 10 个比特位。

小结：一句话记住它

“布隆过滤器是终极保镖。它能瞬间告诉你谁肯定‘不在名单上’，让你免于在整个夜店里寻找那些根本没来的人。”