缓存、爬虫、数据库、浏览器——大量系统的某个角落都在回答同一个问题：这个元素，我之前见过吗？ 用户名是否已被注册？这条 URL 爬过没有？这个 key 在缓存里存在吗？用哈希表回答当然精确，但如果「见过」的集合有 90 亿条 URL，全量 key 的内存账单会先压垮你。布隆过滤器（Bloom Filter）是 1970 年给出的答案：每元素不到 10 个 bit，换来一个不对称的承诺——它可能把没见过的说成「可能见过」（可控制在 1% 甚至更低），但绝不会把见过的说成没见过。很多场景里，这个不对称正好够用。
一个不对称的承诺
先看清这个承诺的形状。布隆过滤器对「元素在集合中吗」只有两种回答：
- 「一定不在」：100% 可信；
- 「可能 在」：大概率在，小概率是误判（false positive）。
假阴性（false negative，把见过的说成没见过）在标准布隆过滤器里数学上不可能——这一点是全部应用的根基。为什么这个残缺的承诺反而有用？因为多数真实场景里，两种答案的后续代价天差地别：爬虫判断「没爬过」才去爬（误判的代价只是少爬一条）；缓存层判断「一定不存在」就直接返回（挡住穿透，误判的代价只是多查一次数据库）；恶意 URL 初筛为「可能恶意」才进昂贵的完整检查。过滤器的回答只是便宜的初筛，误判由下游的精确查询兜底——设计一个系统用布隆过滤器，本质是在设计「误判之后发生什么」。
工作原理：k 个哈希，一位不增
结构简单到不像话：一个 m 位的位数组，外加 k 个哈希函数。
插入：元素过 k 个哈希函数得到 k 个位置，全部置 1。 查询：同样算出 k 个位置，任一位为 0 → 一定不在（如果插入过，这些位必然全被置 1——假阴性由此封死）；全为 1 → 可能在（可能只是碰巧，别的元素把这些位都占了）。
关键在空间账怎么算。整个数组 m 位、塞 n 个元素、目标误判率 ε，最优配置是：
m = −n · ln ε / (ln 2)² → 每元素约 −2.08 · ln ε 个 bit
k = (m/n) · ln 2 → 只取决于目标误判率
代入数字：1% 误判率只要 9.6 bit/元素，k = 7；误判率每压低 10 倍，每元素加约 4.8 bit。内存账用真实量级算一遍：1 亿个平均 32 字节的 key，哈希表哪怕不计 value、只存 key 加指针开销也要 4.8 GB 上下；布隆过滤器 1% 误判率只要 0.12 GB——四十倍的差距，而 0.1% 误判率也才 0.18 GB。对比例不空缺的理想哈希表，布隆过滤器不存元素本身、开销是每元素常数个 bit，代价就是那句不对称的承诺。
误判率有一个闭式公式，也是所有调参的依据：一位在插入 n 个元素后仍是 0 的概率约 e^(−kn/m)（某次插入没碰它的概率 1−1/m 连乘 n·k 次），查询时 k 个特定位恰好全被别人置 1 的概率就是：
ε ≈ (1 − e^(−kn/m))^k
Wikipedia 词条还给了 Goel–Gupta（2010）的严格上界，含义可以理解为「近似公式最多多算半个元素、少算一位」——对工程调参来说，近似式足够准。
k 不是越多越好：一条 U 形曲线
公式里最反直觉的是 k 的取舍。多一个哈希函数，「误判需要的位被占满」当然更难；但每个元素也会多占几位，数组更满，留给别人的空位反而更少。两种力量一正一反，误判率对 k 是一条 U 形曲线。固定每元素 9.6 bit，把 k 从 1 扫到 20，理论误判率是：
| k | 1 | 3 | 5 | 7 | 10 | 14 | 20 |
|---|---|---|---|---|---|---|---|
| 误判率 | 9.9% | 1.94% | 1.11% | 1.00% | 1.30% | 2.47% | 7.04% |
最低点正好落在 k = (m/n)·ln 2 ≈ 6.65 取整的 7 上——k 的公式不是经验值，是这条 U 形曲线的最低点。实用推论：哈希函数不是白来的，超过最优点后每加一个都是纯损失；反过来，离最优点差一两个（k=5 对 k=7），代价只有 11%，工程上完全可接受。
实战范式：挡在缓存前面的第一道闸
布隆过滤器最高频的落地场景是缓存穿透：恶意请求拿着大量不存在的 key 打接口，每一发都绕过缓存直击数据库，轻则慢、重则雪崩。标准的三层布防：
- 启动/定时把全量合法 key 灌入布隆过滤器（放内存，1 亿 key 约 0.12 GB）；
- 请求先问过滤器——「一定不在」直接返回，数据库零流量；
- 「可能在」才走正常链路：查缓存，未命中再查库；查完发现确实不存在（那 1% 误判），就把空结果短暂缓存，挡住同一个 key 的连发。
这套布防的精妙处在分工：布隆过滤器负责「批量说不存在」，空值缓存负责「盯住个别误判」，两者互补，谁也不能单独替代谁。新 key 的加入是实时的（add 一个位图操作），删除则处理不了——已失效的 key 只能等误判率上飘后整表重建，或者直接上 Counting 变体。把这套结构用在注册查重、爬虫去重、消息去重上，模式一模一样，换的只是「合法 key 集合」是谁。
本地实测：公式准到什么程度
按上面的配置写一个最小实现（工程上常用 Kirsch–Mitzenmacher 的双哈希技巧：用两个基础哈希 h1 + i·h2 线性组合出 k 个位置，省掉 k 次完整哈希）：
import hashlib, math, struct
class BloomFilter:
def __init__(self, n: int, eps: float):
self.m = math.ceil(-n * math.log(eps) / math.log(2) ** 2) # 总位数
self.k = max(1, round(self.m / n * math.log(2))) # 哈希个数
self.bits = bytearray((self.m + 7) // 8)
def _pos(self, item: str):
h = hashlib.sha256(item.encode()).digest()
h1 = struct.unpack_from("<Q", h, 0)[0]
h2 = struct.unpack_from("<Q", h, 8)[0] | 1 # 取奇数防周期退化
return [(h1 + i * h2) % self.m for i in range(self.k)]
def add(self, item):
for p in self._pos(item):
self.bits[p >> 3] |= 1 << (p & 7)
def __contains__(self, item):
return all(self.bits[p >> 3] >> (p & 7) & 1 for p in self._pos(item))
插入 10 万个随机元素后实测，理论值与实测值几乎重合：
| 目标误判率 | k | 实测 bit/元素 | 理论误判率 | 实测误判率 |
|---|---|---|---|---|
| 1% | 7 | 9.59 | 0.01004 | 0.00971 |
| 0.1% | 10 | 14.38 | 0.00100 | 0.00099 |
同时验证了 10 万个已插入元素全部查询为真——零假阴性。20 行代码，教科书公式，实测即所见。
它活在哪儿
「便宜的初筛 + 昂贵的精确查询」这个模式，在各路系统里反复上演：
| 系统 | 用它挡什么 | 一句话说明 |
|---|---|---|
| Chrome（曾用） | 恶意 URL 全量比对 | 本地布隆初筛，命中才请求完整安全列表 |
| Firefox | 证书吊销与恶意扩展 | 级联布隆过滤器（CRLite），阳性再查精确结构 |
| Bigtable / HBase / Cassandra / ScyllaDB / PostgreSQL | 不存在的行/列的磁盘读 | 先查内存里的过滤器，一定不存在就不碰磁盘 |
| Akamai CDN | 「只被访问一次」的对象 | 第二次请求才落缓存，磁盘写入率几乎减半 |
| Bitcoin（曾用） | 钱包同步过滤交易 | 后因隐私泄露风险弃用（误报集合可暴露钱包地址） |
| Grafana Tempo / Medium | 不存在的 trace / 已推荐过的内容 | 初筛避免昂贵的精确查询与重复推荐 |
注意 Cassandra 这类数据库的用法是标准范式：过滤器说「不在」就跳过磁盘 IO，说「可能在」才去走正常的查询路径——误判的代价被精确地限制为一次多余的磁盘读。Bitcoin 的弃用则是另一面的警示：过滤器不加密，误报的「可能见过」集合本身可能泄露信息，用它做涉及隐私的初筛要格外小心。
代价与边界
布隆过滤器不是免费午餐，四条边界要刻在脑子里：
第一，不能删除。元素的 k 个位可能被其他元素共享，清掉任何一位都可能制造假阴性——这会击穿整个结构的根基。要删除就得用 Counting Bloom Filter（Fan 等人，2000）：把每个位换成 3–4 位的计数器，插入递增、删除递减，查询查非零。空间涨 3–4 倍，还引入计数器溢出与「需要预知容量」的新问题。
第二，容量必须预估。装填超过设计容量后误判率快速上飘，全满之后所有查询都返回「可能在」，过滤器报废。规划时按增长上限留余量，或用可扩容的变体。
第三，有 44% 的理论税。信息论下界是每元素 log₂(1/ε) 个 bit，布隆过滤器实际用 1.44 · log₂(1/ε)——比理论最优多 44%，这是「只用一个位数组、不存元素」这个简洁性换来的。另外元素数很小或能精确枚举时，一个普通位数组（每候选元素 1 bit）可能比布隆更省：千级规模、全集可枚举的场景，1000 个 bit 的确定性数组就能做到零误判，布隆的空间优势要 n 足够大、全集不可枚举时才真正显现。
第四，查询结果是初筛不是结论。返回「可能在」后必须由业务侧精确确认（查数据库、查完整列表）。把布隆过滤器的「可能」直接当成「是」，是这类结构在生产事故里最常见的原因。
选型时还有一张变体地图值得知道：需要删除，看 Cuckoo Filter（2014，指纹 + 两个候选桶，空间与最优布隆相当且支持删除）；数据集静态（建好不再加），看 Xor / Binary Fuse Filter（Graf 与 Lemire 2020 起的系列，比布隆更小更快，代价是建成后不能插入）；数据量会持续增长，看 Scalable Bloom Filter（分段扩容）。而默认的心智模型仍然是布隆本身——生态最熟、实现最多、面试最爱问，2026 年它依然是这个领域的通用语。
结语
布隆过滤器把一个工程真理做成了数据结构：多数时候你并不需要精确答案，只需要一个便宜且不会说谎一半的初筛。它用假阳性的自由换来了假阴性的绝迹，用 9.6 bit/元素换掉了全量存储。什么时候该想起它？当你发现自己在为「见过吗」这个问题存全量 key、而误判的后果只是一次多余查询的时候——那一刻，这 55 年前的老结构就是最优解。
参考资料
- Bloom filter — Wikipedia：公式推导、空间下界与应用清单的整理来源。
- Space/Time Trade-offs in Hash Coding with Allowable Errors — Burton H. Bloom, CACM 1970：原始论文。
- Counting Bloom Filter — Wikipedia：可删除变体的计数器设计与权衡。
- Cuckoo Filter — Wikipedia：支持删除的布隆替代品，指纹与候选桶机制。
- Xor Filters: Faster and Smaller Than Bloom and Cuckoo Filters — arXiv:1912.08258：静态场景下更小更快的新一代过滤器。
- Bloom filter（中文）— Wikipedia：中文术语对照与原理补充。
读者留言
COMMENTS 暂无还没有留言，来说第一句？