布隆过滤器
布隆过滤器用远小于集合本身的空间来测试集合成员，代价是一个小的、可调的假阳性率。这个权衡值得记住：没有假阴性，可能有假阳性。如果过滤器说"不在集合中"，你可以完全相信。如果它说"可能在集合中"，你需要二次的权威校验。
这种不对称性正是它有用的地方：它是一个廉价的负向缓存，让昂贵的系统跳过"自己没有"的条目上的工作。
工作原理
分配一个大小为 m、初始化为 0 的位数组，选择 k 个独立的哈希函数，每个把元素映射到 [0, m) 中的某个位置。
Insert(x)： 计算 x 的 k 个哈希，把所有 k 个位置置 1。
Contains(x)： 计算相同的 k 个哈希。如果 k 个位置中有任意一个为 0，则 x 一定不在集合中。如果 k 位全为 1，则 x 可能在集合中——但也可能是假阳性（k 位碰巧都被其他插入操作置过 1）。
m = 16 位，k = 2 个哈希函数
insert("cat")： 哈希 → (3, 11) 位：0001000000010000
insert("dog")： 哈希 → (1, 7) 位：0101000100010000
contains("cat")： 哈希 → (3, 11) 两位都为 1 → "可能存在"
contains("fox")： 哈希 → (1, 3) 两位都为 1 → 假阳性！
contains("owl")： 哈希 → (5, 9) 第 5 位为 0 → "绝对不存在"
标准实现使用两个哈希函数，通过 h_i(x) = h1(x) + i·h2(x)（Kirsch-Mitzenmacher 技巧）派生出 k 个位置，避免计算 k 个独立哈希。
数学（如何选 m 和 k）
给定预期元素数 n 和期望假阳性率 p，最优大小为：
m = -(n · ln(p)) / (ln(2))² ≈ 对 p = 0.01，9.6 · n 位
k = (m / n) · ln(2) ≈ 对 p = 0.01，7 个哈希函数
实用经验法则：
- 约 10 位/元素 给你 1% 的假阳性率。
- 约 14 位/元素 给你 0.1%。
- 约 20 位/元素 给你 0.0001%。
曲线先陡后平——从 10% 降到 1% 要约 7 位/元素；从 1% 降到 0.1% 只要再多约 5 位。但你在内存上付出的是线性代价。
在线计算器：hur.st/bloomfilter 是选参数的标准参考。
你做不到的事
- 删除元素。 一旦一位被置 1，你就不能清除它，因为可能损害其他也使用此位的元素的成员判断。需要删除的话，用计数型布隆过滤器（单元为计数器而非位）或布谷鸟过滤器。
- 枚举元素。 布隆过滤器只回答成员查询。它不知道自己包含什么。
- 获取精确计数。 你可以从已置位数估计
n，但只是近似。 - 动态增长。 如果你插入的元素数超过了设计量，假阳性率会悄悄恶化。可扩展布隆过滤器通过子过滤器级联来应对这一点。
真实系统在哪里使用它
Cassandra / RocksDB / LevelDB 的 SSTable
经典的 LSM 树用例。每个不可变的有序文件（SSTable / SST）都有一个保存其键的内存布隆过滤器。读取时系统先查各 SSTable 的过滤器再访问磁盘。1% 的假阳性率意味着 99% 的"不存在的键"读取完全跳过磁盘——这是"快"与"不可用"之间的差别，尤其是在键空间无法完全装进 block cache 时。
HBase
模式同 Cassandra，但同时提供行级和行+列级布隆过滤器。列级维护更贵，但能让窄扫描跳过更多 I/O。
Chrome Safe Browsing（历史）
Google Chrome 曾在本地用布隆过滤器检查 URL 是否在已知恶意站点列表中。过滤器只需几 MB，定期刷新；任何命中会触发真正的服务器调用。这个设计后来被变体（Chrome 现在用哈希前缀 + Update 协议）取代，但布隆过滤器时代持续了将近十年。
CDN 缓存淘汰与热键检测
CDN 边缘节点用布隆过滤器跟踪"最近有没有见过这个键？"再决定是否提升进缓存。这能避免把一次性命中的键污染 LRU。
反欺诈与黑名单
布隆过滤器非常适合"这个用户是否被封？"或"这个邮箱是否在抑制列表？"——黑名单可以很大、检查是 O(1)、偶尔的假阳性（拒绝一个合法用户）可以接受，只要很少发生且系统有权威二次校验兜底。
比特币 SPV 客户端
简化支付验证（SPV）钱包向完整节点发送布隆过滤器以请求与它地址相关的交易，而不暴露哪些地址是它的。这方案有已知的隐私缺陷（BIP 37），但展示了"多请求一些、本地过滤"的模式。
值得了解的变种
- 计数型布隆过滤器。 每个单元是一个小计数器（如 4 位），不是 1 位。支持删除，代价是约 4 倍空间。
- 可扩展布隆过滤器。 过滤器级联，当前满了就加一个新的；查询对所有做一遍。应对未知的
n。 - 布谷鸟过滤器。 空间/假阳性率与布隆接近，原生支持删除，且缓存局部性更好。需要支持删除时常作为替代。
- 商数过滤器（Quotient filter）。 更好的缓存行为和合并支持。新一代存储系统在使用。
- 分区布隆过滤器。 把
m切分为k个不相交的区域，每个哈希函数一个。同等大小下假阳性率略差，但分析更简单、并行性更好。 - 块式布隆过滤器（Blocked Bloom filter）。 每次插入只触碰一条缓存行。在现代 CPU 上快得多，假阳性率代价很小。ClickHouse、Impala 等分析引擎在使用。
何时不要用布隆过滤器
- 成员查询本身就是答案，不是预过滤。 如果假阳性没有便宜的兜底校验，你就不能用概率结构。用哈希集合。
- 集合很小。
n < ~1000时，哈希集合更快更简单。布隆过滤器赢在空间，不是时间。 - 频繁且无界的删除。 计数型布隆过滤器在大量插入与删除后会精度衰减。布谷鸟过滤 器也会，只是更平缓。
- 你需要枚举或序列化元素。 布隆过滤器是单向结构。
参见
- 跳表 —— 布隆过滤器通常在 LSM 树 MemTable 中坐在它前面的内存结构。
- B 树与 B+ 树 —— 布隆过滤器保护其免于不必要读取的磁盘存储结构。
- 如何扩展一个 Web 服务？ —— 分片存储需要避免跨分片查找时，布隆过滤器是常用工具。
