布隆过滤器：系统如何快速判断一个东西肯定不存在
布隆过滤器用位数组和多个哈希函数，以极少内存快速筛掉肯定不存在的对象。本文讲清误报与漏报、误报率、删除难题，以及它在缓存、数据库和去重系统中的正确用法。
如果一个网站已经处理过一千万个 URL，现在来了一个新 URL，系统想知道“它是不是见过”。最直接的做法是把所有 URL 放进集合里查找，但集合会占用内存，冷缓存或远程查询还会拖慢请求。布隆过滤器提供了一个很特别的答案：它可以非常快地告诉你“肯定没见过”，但当它说“见过”时，仍然可能认错。
布隆过滤器是一种概率型成员查询结构。它不保存原始对象，只保存一个位数组和若干哈希结果。原始论文讨论的正是如何用更少空间测试一个消息是否属于某个集合，并允许可控的错误概率。Bloom 的原始论文
它为什么能说“肯定不存在”
先准备一个全是 0 的位数组，再选择 k 个哈希函数。加入字符串 apple 时，分别计算 h1(apple)、h2(apple)……，把这些位置设成 1。
查询 apple 时，重新计算这几个位置：
- 只要有一个位置还是 0，
apple就不可能被加入过，因为加入时那个位置一定会被设为 1。 - 如果所有位置都是 1，
apple可能加入过，也可能只是恰好撞上了其他对象留下的 1。
这就是它的核心不对称性：没有误报时，它可以断言“肯定不存在”；出现误报时，它只能说“可能存在”。
一个小例子：用 16 位记录三个单词
假设位数组只有 16 位。加入三个单词后，可能变成：
0001011000101100
查询新单词时，如果它的三个哈希位置分别落在第 2、5、9 位，其中第 5 位是 0，那么可以立刻拒绝它，不必访问数据库。如果三个位置恰好都是 1，系统不能直接把它当成已存在，而应该再做一次真实查询。
布隆过滤器的正确用法通常是“便宜的前置筛选器”：
if (!filter.mightContain(key)) {
return notFound()
}
return database.lookup(key)
它不是权威数据源，不能用来返回真实对象，也不能把“可能存在”当作最终事实。
误报率从哪里来
设位数组长度为 m，加入的元素数量为 n，每个元素使用 k 个哈希函数。元素越多，被设为 1 的位置越多；数组越小，哈希碰撞越密集；哈希函数越多，单次加入会点亮更多位置。三者共同决定误报率。
常见的近似公式是：
p ≈ (1 - e^(-kn/m))^k
不需要把它当成考试公式，只要记住两个方向：想降低误报率，要增加位数；在固定空间下，哈希数量也存在一个合适区间，太少会让不同元素容易碰撞，太多则会过快把位数组填满。
当目标误报率是 p、预计元素数量是 n 时，可以先估算需要的位数，再选择哈希数量。工程上还要为增长留余量，因为过滤器通常不适合无限追加数据。
删除为什么麻烦
普通布隆过滤器只记录 0 和 1。两个对象可能共同把某一位设成 1，删除其中一个对象时，系统不知道这位是否还被另一个对象使用，所以不能安全地把它改回 0。
有几种常见处理方式：
- 不支持删除，只把过滤器当作生命周期固定的快照。
- 使用 Counting Bloom Filter，把每一位换成小计数器。
- 按时间窗口创建多个过滤器，到期后整体丢弃。
- 使用支持扩容或删除的其他近似成员结构。
Counting Bloom Filter 能删除，但每个位置需要更多空间，也会带来计数器溢出和并发更新问题。所谓“支持删除”不是免费升级，而是改变了成本模型。
它适合挡在哪里
在 LSM-Tree 数据库中，布隆过滤器可以先判断某个 SSTable 是否不可能包含目标键，减少磁盘读取；在缓存前，可以先挡住明显不存在的键，降低缓存穿透；在 URL 去重、爬虫任务和数据导入中，它能快速过滤大量重复候选。
但它不适合单独承担安全决策。比如“黑名单过滤器说用户不在黑名单里”只能作为快速路径，不能替代权威权限表；误报只会带来额外查询，漏报却可能导致错误放行，因此要先确认业务能承受它的错误方向。
设计时要问的五个问题
- 元素数量是固定的，还是会持续增长？
- 能否接受误报？误报会带来一次慢查询，还是直接给用户错误结果？
- 是否需要删除？如果需要，是否值得付出计数器空间？
- 过滤器是否需要持久化，还是重启后可以重建？
- 过滤器失效时，真实数据路径是否仍然正确？
最后一个问题最重要。布隆过滤器的设计哲学是“优化慢路径”，不是“替代真相”。只要真实查询仍然是正确的，过滤器即使误报，也只是多做了一次工作。
一句话带走
布隆过滤器用少量内存换取一次快速判断，但它故意只保证一件事：发现 0，就能确定不存在。理解这种“允许误报、不允许漏报”的取舍，也就理解了很多大型系统为什么会先用一个看似不可靠的小结构挡在真正数据库前面。
