大家好我是程序员小策。先做个自测——你的系统里判断用户是否已注册用的是什么方案A. 直接查数据库 — 简单粗暴但每秒 10 万次注册检查数据库先扛不住B. 用 HashSet 全量缓存 — 查得快但 1 亿用户吃掉好几 GB 内存C. 用布隆过滤器 — 省内存但删不了数据用户注销了怎么办D. 用布谷鸟过滤器 — 能删、省内存、查询还更快选 C 的同学你已经摸到门道了。但选 C 的时候你心里肯定犯嘀咕布隆过滤器不能删除那用户注销了怎么办今天这篇文章分两步走先把布隆过滤器讲透再引出它的上位替代——布谷鸟过滤器。问题定义查存在性但不想把所有数据都装进内存场景很常见判断一个元素可能存在还是一定不存在。注册时检查用户名是否重复、爬虫判断 URL 是否已抓取、缓存穿透时拦截非法请求……这些场景有一个共同特点你不需要知道元素的具体内容只需要知道在不在。朴素方案是 HashSet把所有元素都存一份。1 亿个手机号每个 11 字节就是 1.1 GB。换成布隆过滤器呢1% 误判率下1 亿个元素只需要约 114 MB——省了 90% 的内存。这就是布隆过滤器存在的意义用极少的内存快速判断一定不存在。布隆过滤器公告栏上的便签布隆过滤器Bloom Filter一个位数组 多个哈希函数的组合。插入时将元素经多个哈希函数映射到位数组的多个位置并置 1查询时检查这些位置是否全为 1——全为 1 则可能存在有 0 则一定不存在。打个比方布隆过滤器像是一个公告栏。每个人来了都在上面贴便签置 1便签可能重叠——张三和李四的便签贴在了同一个位置。你看到某个位置有便签只能说可能有人在因为不知道是谁贴的。但如果你看到某个位置是空的那一定没人——因为只要有人来过就一定会贴便签。翻译回技术语言公告栏布隆过滤器便签贴在多个位置多个哈希函数映射多个 bit便签重叠不同元素可能映射到同一个 bit看到便签 可能有人在bit 全 1 可能存在空位 一定没人有 bit 为 0 一定不存在布隆过滤器的代码实现importcom.google.common.hash.BloomFilter;importcom.google.common.hash.Funnels;importjava.nio.charset.StandardCharsets;publicclassBloomFilterDemo{publicstaticvoidmain(String[]args){BloomFilterStringfilterBloomFilter.create(Funnels.stringFunnel(StandardCharsets.UTF_8),1_000_000,0.01);filter.put(user:10086);filter.put(user:10087);System.out.println(user:10086 存在filter.mightContain(user:10086));// trueSystem.out.println(user:99999 存在filter.mightContain(user:99999));// 大概率 false// 删除不支持没有 remove 方法// filter.remove(user:10086); // 编译错误}}Guava 的BloomFilter.create()两个关键参数预期元素数量和误判率。Guava 会自动计算需要多少个 bit 和多少个哈希函数。1% 误判率下每个元素约占 9.6 bit1 亿元素约 114 MB。布隆过滤器的边界与陷阱陷阱一误判是单向的。说存在可能是假的但说不存在一定是真的。布隆过滤器只适合过滤不可能存在的不适合确认一定存在的。陷阱二哈希函数数量不是越多越好。哈希函数越多每个元素置 1 的 bit 越多位数组越快被填满误判率反而上升。让 Guava 自动计算最优值就好公式是 k (n/m) × ln2。陷阱三满了不会报错只是误判率升高。插入元素超过预期容量时布隆过滤器不会报错但误判率会持续上升。这是个优雅的退化——不会崩但越来越不准。布隆过滤器在 Redis 中的实战生产环境通常不会在 JVM 内存里放布隆过滤器——多节点部署时每个节点各持一份插入操作无法同步。Redis 4.0 提供了 BF 模块RedisBloom把布隆过滤器搬到 Redis 里所有节点共享一份BF.RESERVE my_filter0.011000000# 创建误判率 1%容量 100 万BF.ADD my_filteruser:10086# 插入BF.EXISTS my_filteruser:10086# 查询1 可能存在BF.EXISTS my_filteruser:99999# 查询0 一定不存在集群模式下需要注意布隆过滤器的 key 是一个整体不能跨分片。超大数据量需要在应用层做分片——按 key 前缀路由到不同的 Redis 节点。布隆过滤器的致命缺陷不能删除讲到这里布隆过滤器看起来很完美了。省内存、查询快、Redis 原生支持。但有一个场景它搞不定用户注销。用户注销了账号你需要从布隆过滤器中移除这个用户。但布隆过滤器没有 remove 方法——因为多个元素可能共享同一个 bit 位你把一个元素对应的 bit 清零其他元素就被误判为不存在了。回到公告栏的类比张三和李四的便签贴在了同一个位置。你想撕掉张三的便签但一撕就把李四的也撕了。所以你只能贴不能撕。这就是核心矛盾你需要一个既省内存、又能删除的概率型数据结构。布隆过滤器做不到。但布谷鸟过滤器做到了。布谷鸟过滤器储物柜里的名片布谷鸟过滤器Cuckoo Filter基于布谷鸟哈希的概率型数据结构。插入时存储元素的指纹fingerprint而非 bit 位查询时通过指纹匹配判断存在性删除时直接移除指纹——天然支持删除。2014 年CMU、Harvard 和 Intel 的团队发表了论文“Cuckoo Filter: Practically Better Than Bloom”标题就差把我比布隆强写脸上了。继续用类比如果说布隆过滤器是公告栏那布谷鸟过滤器就是储物柜。每个人来了分配一个格子里面放一张名片指纹。要查谁在不在看有没有他的名片就行要删谁直接把名片抽走——互不干扰。储物柜布谷鸟过滤器每人一个格子放名片每个元素存一个 fingerprint抽走名片 人走了删除 fingerprint 元素移除看到名片 可能有人在fingerprint 匹配 可能存在为什么是可能存在而不是一定存在因为指纹是截断的——不同元素可能算出相同的指纹就像两个人名片上的名字恰好一样。但这个误判率是可控的指纹越长误判率越低。布谷鸟过滤器的核心原理鸠占鹊巢布谷鸟过滤器的名字来自布谷鸟哈希Cuckoo Hashing。布谷鸟下蛋时会把别的鸟的蛋推出鸟巢换成自己的——这就是鸠占鹊巢。插入过程对元素做哈希算出两个候选桶bucket第一个桶有空位直接放进去第一个桶满了踢走一个已有元素把自己的指纹放进去被踢走的元素去找它的另一个候选桶……如此循环直到所有元素都找到位置或者达到最大踢出次数插入失败布谷鸟过滤器的代码实现开源实现参考CuckooFilter4Jimportcom.mgunlogson.cuckoofilter.CuckooFilter;importcom.mgunlogson.cuckoofilter.CuckooFilter.Builder;publicclassCuckooFilterDemo{publicstaticvoidmain(String[]args){CuckooFilterStringfilternewBuilderString((long)1_000_000).withFingerprintLength(12).build();filter.put(user:10086);filter.put(user:10087);System.out.println(user:10086 存在filter.mightContain(user:10086));// trueSystem.out.println(user:99999 存在filter.mightContain(user:99999));// 大概率 false// 删除这是布隆过滤器做不到的booleandeletedfilter.delete(user:10086);System.out.println(删除 user:10086deleted);// trueSystem.out.println(删除后查询filter.mightContain(user:10086));// false}}关键区别一目了然布谷鸟过滤器有delete()方法布隆过滤器没有。Redis 中同样支持布谷鸟过滤器。RedisBloom 从 2.2.0 起提供了CF.ADD/CF.DEL命令CF.RESERVE my_cuckoo1000000# 创建布谷鸟过滤器CF.ADD my_cuckoouser:10086# 插入CF.DEL my_cuckoouser:10086# 删除布隆过滤器做不到布谷鸟过滤器的边界与陷阱陷阱一重复元素删除有坑。插入同一个元素两次删除一次只会移除一个 fingerprint查询时仍然可能返回存在。更糟的是只插入一次却删除两次可能会误删别人的 fingerprint。解法要么保证不插入重复元素要么自己维护计数。陷阱二有容量上限满了直接插入失败。布隆过滤器满了只是误判率升高不会报错——这是优雅退化。但布谷鸟过滤器满了会直接插入失败——踢出次数达到上限所有桶都塞满了。解法设置合理的容量预期监控填充率快满时扩容重建。陷阱三踢出链可能很长。最坏情况下踢出链很长甚至无限循环。实践中只要填充率不超过 95%平均踢出次数通常在 2-3 次以内。对比表格维度布隆过滤器布谷鸟过滤器查询性能O(k)k 为哈希函数数通常 7 次O(1)最多查 2 个桶插入性能O(k)均摊 O(1)最坏 O(踢出次数)删除❌ 不支持✅ 支持空间效率ε 3%1.44n·log₂(1/ε) bit1.05n·log₂(1/ε) 3.15n bit空间效率ε 3%更优更差误判率可控✅ 参数可调✅ 通过指纹长度调整重复元素不影响删除时可能误删容量溢出误判率升高优雅退化插入失败硬性报错实现复杂度简单位数组 哈希较复杂桶 踢出逻辑成熟度极高Guava、RedisBloom较新生态不完善一句话总结误判率要求低于 3% 且需要删除 → 布谷鸟过滤器不需要删除或误判率要求宽松 → 布隆过滤器。面试追问追问 1布隆过滤器误判率 1% 是什么意思100 个查询里一定有 1 个错→ 回答方向不是。1% 误判率是指对于一个确实不存在的元素过滤器错误地判断为存在的概率是 1%。如果查询的元素大部分都存在实际误判次数远少于 1%。误判率是针对不存在元素的条件概率。追问 2布谷鸟过滤器的踢出机制会不会导致插入性能退化→ 回答方向会。最坏情况下踢出链很长甚至无限循环达到最大踢出次数后插入失败。实践中只要填充率不超过 95%平均踢出次数通常在 2-3 次以内。这是为什么布谷鸟过滤器需要预留足够的容量。追问 3缓存穿透场景下布隆过滤器和空值缓存该选哪个→ 回答方向不是二选一而是配合使用。布隆过滤器拦截大部分非法请求一定不存在的直接返回空值缓存兜底布隆过滤器的误判可能存在但数据库查不到的缓存空值并设短 TTL。两者互补不互斥。追问 4布谷鸟过滤器真的比布隆过滤器更好吗论文标题可是Practically Better Than Bloom。→ 回答方向论文的更好有前提条件——误判率低于 3% 且需要删除。如果不需要删除布隆过滤器的实现更简单、生态更成熟、容量溢出时更优雅只是误判率升高而非插入失败。工程选型不是比谁论文写得好是比谁在你的场景下更合适。总结布隆过滤器解决在不在线的快速判断布谷鸟过滤器解决走了也能删的动态管理。读完这篇你应该能用 Guava 写一个生产可用的布隆过滤器、解释为什么布隆过滤器不能删除以及布谷鸟过滤器如何解决、在面试中说出两者的空间效率分界线误判率 3%、根据业务场景做出正确的选型判断。
布隆过滤器：从位图到布谷鸟的演进之路——缓存穿透的终极防线
发布时间：2026/5/27 3:00:11
大家好我是程序员小策。先做个自测——你的系统里判断用户是否已注册用的是什么方案A. 直接查数据库 — 简单粗暴但每秒 10 万次注册检查数据库先扛不住B. 用 HashSet 全量缓存 — 查得快但 1 亿用户吃掉好几 GB 内存C. 用布隆过滤器 — 省内存但删不了数据用户注销了怎么办D. 用布谷鸟过滤器 — 能删、省内存、查询还更快选 C 的同学你已经摸到门道了。但选 C 的时候你心里肯定犯嘀咕布隆过滤器不能删除那用户注销了怎么办今天这篇文章分两步走先把布隆过滤器讲透再引出它的上位替代——布谷鸟过滤器。问题定义查存在性但不想把所有数据都装进内存场景很常见判断一个元素可能存在还是一定不存在。注册时检查用户名是否重复、爬虫判断 URL 是否已抓取、缓存穿透时拦截非法请求……这些场景有一个共同特点你不需要知道元素的具体内容只需要知道在不在。朴素方案是 HashSet把所有元素都存一份。1 亿个手机号每个 11 字节就是 1.1 GB。换成布隆过滤器呢1% 误判率下1 亿个元素只需要约 114 MB——省了 90% 的内存。这就是布隆过滤器存在的意义用极少的内存快速判断一定不存在。布隆过滤器公告栏上的便签布隆过滤器Bloom Filter一个位数组 多个哈希函数的组合。插入时将元素经多个哈希函数映射到位数组的多个位置并置 1查询时检查这些位置是否全为 1——全为 1 则可能存在有 0 则一定不存在。打个比方布隆过滤器像是一个公告栏。每个人来了都在上面贴便签置 1便签可能重叠——张三和李四的便签贴在了同一个位置。你看到某个位置有便签只能说可能有人在因为不知道是谁贴的。但如果你看到某个位置是空的那一定没人——因为只要有人来过就一定会贴便签。翻译回技术语言公告栏布隆过滤器便签贴在多个位置多个哈希函数映射多个 bit便签重叠不同元素可能映射到同一个 bit看到便签 可能有人在bit 全 1 可能存在空位 一定没人有 bit 为 0 一定不存在布隆过滤器的代码实现importcom.google.common.hash.BloomFilter;importcom.google.common.hash.Funnels;importjava.nio.charset.StandardCharsets;publicclassBloomFilterDemo{publicstaticvoidmain(String[]args){BloomFilterStringfilterBloomFilter.create(Funnels.stringFunnel(StandardCharsets.UTF_8),1_000_000,0.01);filter.put(user:10086);filter.put(user:10087);System.out.println(user:10086 存在filter.mightContain(user:10086));// trueSystem.out.println(user:99999 存在filter.mightContain(user:99999));// 大概率 false// 删除不支持没有 remove 方法// filter.remove(user:10086); // 编译错误}}Guava 的BloomFilter.create()两个关键参数预期元素数量和误判率。Guava 会自动计算需要多少个 bit 和多少个哈希函数。1% 误判率下每个元素约占 9.6 bit1 亿元素约 114 MB。布隆过滤器的边界与陷阱陷阱一误判是单向的。说存在可能是假的但说不存在一定是真的。布隆过滤器只适合过滤不可能存在的不适合确认一定存在的。陷阱二哈希函数数量不是越多越好。哈希函数越多每个元素置 1 的 bit 越多位数组越快被填满误判率反而上升。让 Guava 自动计算最优值就好公式是 k (n/m) × ln2。陷阱三满了不会报错只是误判率升高。插入元素超过预期容量时布隆过滤器不会报错但误判率会持续上升。这是个优雅的退化——不会崩但越来越不准。布隆过滤器在 Redis 中的实战生产环境通常不会在 JVM 内存里放布隆过滤器——多节点部署时每个节点各持一份插入操作无法同步。Redis 4.0 提供了 BF 模块RedisBloom把布隆过滤器搬到 Redis 里所有节点共享一份BF.RESERVE my_filter0.011000000# 创建误判率 1%容量 100 万BF.ADD my_filteruser:10086# 插入BF.EXISTS my_filteruser:10086# 查询1 可能存在BF.EXISTS my_filteruser:99999# 查询0 一定不存在集群模式下需要注意布隆过滤器的 key 是一个整体不能跨分片。超大数据量需要在应用层做分片——按 key 前缀路由到不同的 Redis 节点。布隆过滤器的致命缺陷不能删除讲到这里布隆过滤器看起来很完美了。省内存、查询快、Redis 原生支持。但有一个场景它搞不定用户注销。用户注销了账号你需要从布隆过滤器中移除这个用户。但布隆过滤器没有 remove 方法——因为多个元素可能共享同一个 bit 位你把一个元素对应的 bit 清零其他元素就被误判为不存在了。回到公告栏的类比张三和李四的便签贴在了同一个位置。你想撕掉张三的便签但一撕就把李四的也撕了。所以你只能贴不能撕。这就是核心矛盾你需要一个既省内存、又能删除的概率型数据结构。布隆过滤器做不到。但布谷鸟过滤器做到了。布谷鸟过滤器储物柜里的名片布谷鸟过滤器Cuckoo Filter基于布谷鸟哈希的概率型数据结构。插入时存储元素的指纹fingerprint而非 bit 位查询时通过指纹匹配判断存在性删除时直接移除指纹——天然支持删除。2014 年CMU、Harvard 和 Intel 的团队发表了论文“Cuckoo Filter: Practically Better Than Bloom”标题就差把我比布隆强写脸上了。继续用类比如果说布隆过滤器是公告栏那布谷鸟过滤器就是储物柜。每个人来了分配一个格子里面放一张名片指纹。要查谁在不在看有没有他的名片就行要删谁直接把名片抽走——互不干扰。储物柜布谷鸟过滤器每人一个格子放名片每个元素存一个 fingerprint抽走名片 人走了删除 fingerprint 元素移除看到名片 可能有人在fingerprint 匹配 可能存在为什么是可能存在而不是一定存在因为指纹是截断的——不同元素可能算出相同的指纹就像两个人名片上的名字恰好一样。但这个误判率是可控的指纹越长误判率越低。布谷鸟过滤器的核心原理鸠占鹊巢布谷鸟过滤器的名字来自布谷鸟哈希Cuckoo Hashing。布谷鸟下蛋时会把别的鸟的蛋推出鸟巢换成自己的——这就是鸠占鹊巢。插入过程对元素做哈希算出两个候选桶bucket第一个桶有空位直接放进去第一个桶满了踢走一个已有元素把自己的指纹放进去被踢走的元素去找它的另一个候选桶……如此循环直到所有元素都找到位置或者达到最大踢出次数插入失败布谷鸟过滤器的代码实现开源实现参考CuckooFilter4Jimportcom.mgunlogson.cuckoofilter.CuckooFilter;importcom.mgunlogson.cuckoofilter.CuckooFilter.Builder;publicclassCuckooFilterDemo{publicstaticvoidmain(String[]args){CuckooFilterStringfilternewBuilderString((long)1_000_000).withFingerprintLength(12).build();filter.put(user:10086);filter.put(user:10087);System.out.println(user:10086 存在filter.mightContain(user:10086));// trueSystem.out.println(user:99999 存在filter.mightContain(user:99999));// 大概率 false// 删除这是布隆过滤器做不到的booleandeletedfilter.delete(user:10086);System.out.println(删除 user:10086deleted);// trueSystem.out.println(删除后查询filter.mightContain(user:10086));// false}}关键区别一目了然布谷鸟过滤器有delete()方法布隆过滤器没有。Redis 中同样支持布谷鸟过滤器。RedisBloom 从 2.2.0 起提供了CF.ADD/CF.DEL命令CF.RESERVE my_cuckoo1000000# 创建布谷鸟过滤器CF.ADD my_cuckoouser:10086# 插入CF.DEL my_cuckoouser:10086# 删除布隆过滤器做不到布谷鸟过滤器的边界与陷阱陷阱一重复元素删除有坑。插入同一个元素两次删除一次只会移除一个 fingerprint查询时仍然可能返回存在。更糟的是只插入一次却删除两次可能会误删别人的 fingerprint。解法要么保证不插入重复元素要么自己维护计数。陷阱二有容量上限满了直接插入失败。布隆过滤器满了只是误判率升高不会报错——这是优雅退化。但布谷鸟过滤器满了会直接插入失败——踢出次数达到上限所有桶都塞满了。解法设置合理的容量预期监控填充率快满时扩容重建。陷阱三踢出链可能很长。最坏情况下踢出链很长甚至无限循环。实践中只要填充率不超过 95%平均踢出次数通常在 2-3 次以内。对比表格维度布隆过滤器布谷鸟过滤器查询性能O(k)k 为哈希函数数通常 7 次O(1)最多查 2 个桶插入性能O(k)均摊 O(1)最坏 O(踢出次数)删除❌ 不支持✅ 支持空间效率ε 3%1.44n·log₂(1/ε) bit1.05n·log₂(1/ε) 3.15n bit空间效率ε 3%更优更差误判率可控✅ 参数可调✅ 通过指纹长度调整重复元素不影响删除时可能误删容量溢出误判率升高优雅退化插入失败硬性报错实现复杂度简单位数组 哈希较复杂桶 踢出逻辑成熟度极高Guava、RedisBloom较新生态不完善一句话总结误判率要求低于 3% 且需要删除 → 布谷鸟过滤器不需要删除或误判率要求宽松 → 布隆过滤器。面试追问追问 1布隆过滤器误判率 1% 是什么意思100 个查询里一定有 1 个错→ 回答方向不是。1% 误判率是指对于一个确实不存在的元素过滤器错误地判断为存在的概率是 1%。如果查询的元素大部分都存在实际误判次数远少于 1%。误判率是针对不存在元素的条件概率。追问 2布谷鸟过滤器的踢出机制会不会导致插入性能退化→ 回答方向会。最坏情况下踢出链很长甚至无限循环达到最大踢出次数后插入失败。实践中只要填充率不超过 95%平均踢出次数通常在 2-3 次以内。这是为什么布谷鸟过滤器需要预留足够的容量。追问 3缓存穿透场景下布隆过滤器和空值缓存该选哪个→ 回答方向不是二选一而是配合使用。布隆过滤器拦截大部分非法请求一定不存在的直接返回空值缓存兜底布隆过滤器的误判可能存在但数据库查不到的缓存空值并设短 TTL。两者互补不互斥。追问 4布谷鸟过滤器真的比布隆过滤器更好吗论文标题可是Practically Better Than Bloom。→ 回答方向论文的更好有前提条件——误判率低于 3% 且需要删除。如果不需要删除布隆过滤器的实现更简单、生态更成熟、容量溢出时更优雅只是误判率升高而非插入失败。工程选型不是比谁论文写得好是比谁在你的场景下更合适。总结布隆过滤器解决在不在线的快速判断布谷鸟过滤器解决走了也能删的动态管理。读完这篇你应该能用 Guava 写一个生产可用的布隆过滤器、解释为什么布隆过滤器不能删除以及布谷鸟过滤器如何解决、在面试中说出两者的空间效率分界线误判率 3%、根据业务场景做出正确的选型判断。
