Theory · Data Structure · Bloom Filter
用误判率换内存：bit 数组 + k 个哈希 · "可能存在，绝不存在" · 缓存穿透的第一道闸门
m 位数组 + k 个独立哈希函数——插入置 1，查询验 1
返回"可能存在"或"一定不存在"——单向、可误判、不可删除
1% 误判率只需每元素约 10 bit——比哈希表省 10~20 倍内存
Bit Array + k Hashes
False Positive · m, k, n Trade-offs
p ≈ (1 − e^(−kn/m))^k
m 位数组、k 个哈希、已插 n 个元素。最优哈希个数 k = (m/n)·ln2 ≈ 0.69·(m/n)，此时 p ≈ 0.6185^(m/n)。
每元素 8 bit → p≈2.2%；10 bit → 0.8%；16 bit → 0.05%。每元素 10 bit、k=7 是工程默认档位。
先定可接受的误判率 → 算出每元素 bit 数 → 算出 m 和 k。反过来：内存预算固定时，能容忍的误判率被锁死——空间、精度、容量三角。
① 容量溢出：n 超过设计值，误判率快速恶化——要预估容量或用可扩展布隆（Scalable BF）；② 哈希质量：k 个哈希要近似独立（工程常用 double hashing：h₁+h₂·i 模拟 k 个）。
| 每元素 bit（m/n） | 最优 k | 误判率 p |
|---|---|---|
| 6 | 4 | ≈ 5.6% |
| 8 | 6 | ≈ 2.2% |
| 10 | 7 | ≈ 0.82% |
| 12 | 8 | ≈ 0.32% |
| 16 | 11 | ≈ 0.045% |
Cache Penetration · Standard Fix
穿透：查不存在的 key，缓存与 DB 都没有 → 每次都打到 DB（恶意可放大）；击穿：热点 key 过期瞬间；雪崩：大批 key 同时失效。布隆过滤器专治穿透。
① 布隆过滤器挡在缓存前：一定不存在的直接拒绝，DB 零压力；② 不存在的 key 缓存空值（短 TTL）；③ 限流/参数校验兜底。三层递进，布隆是最省资源的第一道闸。
穿透流量查的是"海量随机不存在的 key"——布隆的负判断零误差正好匹配：说没有就是没有，放心拒绝；说可能存在才放行到缓存/DB（少量误判会多查一次空，可接受）。
DB 新增 key 后要同步加入布隆过滤器；布隆不支持删除 → 删除的 key 会继续"可能存在"（放行后查 DB 为空，由空值缓存兜底）。详见 缓存模式 deck。
| 场景 | 布隆过滤器的用法 |
|---|---|
| 缓存穿透 | key 是否可能存在，不存在直接拒 |
| 爬虫去重 / URL 去重 | 亿级 URL 判"见过没有" |
| 垃圾邮件 / 黑名单 | 可能命中才细查规则库 |
| 推荐已读过滤 | 已推荐内容过滤（误判=少推一次，无害） |
| LevelDB/LSM | 每个 SSTable 一个 BF，避免无效读盘 |
| HBase / Cassandra | 同上：读之前先问 BF |
Limitations · Variants
一个位被多个元素共享，清零会误伤他人。对症：Counting Bloom Filter——每位换 4 bit 计数器，删除减一；空间 ×4。
n 超设计容量后 p 恶化且不可逆。对症：Scalable BF——满了自动加一层新 BF（查询逐层问）。
只回答"可能在"，不能枚举、不能计数。对症：Cuckoo Filter（布谷鸟）——支持删除、空间更优（同等误判率省 ~25%），且能查"大约多少个"。RedisBloom 模块两者都有。
Counting BF（可删）、Scalable BF（自动扩容）、Cuckoo Filter（可删+更强）、Bloomier（存值）、HyperLogLog（基数统计——另一支概率家族）。
| 结构 | 删除 | 空间 | 场景 |
|---|---|---|---|
| Bloom Filter | ✗ | 10 bit/元素 | 默认选择 |
| Counting BF | ✓ | ~40 bit/元素 | 频繁删除 |
| Scalable BF | ✗ | 分层增长 | 容量不可预估 |
| Cuckoo Filter | ✓ | 更优 ~25% | 删除+查询更强 |
| HyperLogLog | — | 12KB 计数亿级 | 去重计数（UV） |
Go Implementation · LeetCode
type Bloom struct { bits []uint64 m uint32 // 位数 k uint32 // 哈希个数 } // double hashing：每元素只算两个独立哈希 func (b *Bloom) Add(x string) { h1, h2 := fnv32(x), fnv32(x+"salt") for i := uint32(0); i < b.k; i++ { b.set((h1 + i*h2) % b.m) // h1+i·h₂ } } func (b *Bloom) MayContain(x string) bool { h1, h2 := fnv32(x), fnv32(x+"salt") for i := uint32(0); i < b.k; i++ { if !b.get((h1 + i*h2) % b.m) { return false // 一定不存在 } } return true // 可能存在 }
① k 个哈希用 double hashing 模拟（h₁+i·h₂），省掉 k 次完整哈希——理论依据：两个独立哈希可生成近似独立的 k 个；② 位操作 set/get 用 uint64 分桶；③ 容量与误判率初始化时锁定。
Redis RedisBloom 模块（BF.ADD / BF.EXISTS，Cuckoo 也有）；Go 库 bits-and-blooms/bloom；LevelDB/RocksDB 内建（每个 SSTable 一个）。
705 设计哈希集合 E（对照：真哈希 vs 布隆的语义差）；706 设计哈希映射 E；面试官口头题：设计"网页爬虫 URL 去重"系统——10 亿 URL、内存 1GB → 布隆是唯一解（10 bit/URL ≈ 1.25GB？调整到 8bit+可容忍误判 ≈ 1GB）。
给容量 → 算 bit 数 → 给误判率 → 谈删除需求选变体 → 数据一致性（新增同步写入）。一条链把本 deck 全部知识点串起来。
Interview QA
多个元素的哈希位共享，全 1 可能是别人盖的章 → 假阳性（判为存在但实际没有）；假阴性不可能——存在过的元素位永远不会被清零。
p ≈ (1−e^(−kn/m))^k，只与"每元素平均 bit 数 m/n"和 k 有关。10 bit/元素 + k=7 → ≈0.8%。
不是。k 大了位数组被填满更快、任一位为 0 的概率下降。最优 k* = (m/n)·ln2，此时 p 最低 ≈ 0.6185^(m/n)。
一个位可能被多个元素共用，清零会误伤。需要删除 → Counting BF（4bit 计数器）或 Cuckoo Filter（空间更优）。
需要"确切内容 + 无误判" → 哈希表；只要"存在性判断 + 内存极限" → 布隆。布隆省 10~20 倍空间，代价是误判和不可取回。
LevelDB/RocksDB 每个 SSTable 配一个布隆：查 key 先问 BF，"一定不存在"就跳过该文件——把磁盘读次数从"逐文件试探"降到"只读命中的"。
标准布隆会"残留"已删元素（继续判可能存在）。方案：定期全量重建；或 Counting/Cuckoo 支持真删除；缓存场景由空值缓存兜底误判。
同属概率数据结构：布隆管成员查询、HLL 管基数计数（UV 去重，12KB 计数亿级）、CMS 管频次估计——同一哲学：允许小误差换数量级的空间。
Related & References
缓存模式 →（穿透三兄弟与三层防御）
Redis 数据结构 →（RedisBloom 模块载体）
复杂度分析 →（概率结构的"保证"语义辨析）
参考来源（本 deck 结论可溯源至下列一手材料）
| B. Bloom (1970) · Space/Time Trade-offs in Hash Coding | 原始论文：误判率公式与 m/k/n 权衡 |
| LevelDB util/bloom.cc · RocksDB bloom | 工业实现：double hashing 与 SSTable 集成 |
| Fan et al. (2014) · Cuckoo Filter | 布谷鸟过滤器：可删除、空间更优 |
| Redis RedisBloom 文档 · BF.ADD/BF.EXISTS | Redis 概率模块的命令语义 |
| oi-wiki.org/ds/bloom-filter | 误判率推导的中文对照 |