布隆过滤器（Bloom Filter）的原理是什么？适合什么场景？

简化版

布隆过滤器用一个位数组加多个哈希函数判断「一个元素可能存在，还是一定不存在」。加入元素时，用 k 个哈希函数算出 k 个位置全置 1；查询时若这 k 个位置有任意一个是 0，说明一定不存在；若全是 1，说明可能存在（有误判率）。它极省空间、查询快，但有假阳性、且标准版不能删除。典型用来挡缓存穿透。

详细版

结构：一个长度为 m 的位数组（初始全 0）+ k 个相互独立的哈希函数。

加入元素 x：算 h1(x), h2(x), ..., hk(x)，把这 k 个下标的位都置 1。

查询元素 x：算同样 k 个下标：

• 只要有一位是 0 → x 一定不在集合里（因为若加入过，这些位必然都被置 1）。
• 全是 1 → x 可能在集合里（也可能是别的元素把这些位凑巧都置 1 了 → 假阳性）。

核心特性：

• 有假阳性（false positive），无假阴性：说「没有」一定没有，说「有」不一定真有。
• 极省空间：只存 bit，不存元素本身，几亿数据几十 MB 就能搞定。
• 标准版不能删除：把某位清 0 可能误伤其他共享该位的元素。要删除得用计数布隆过滤器（每位改成计数器）。

完整版教学

一、为什么它能又省又快

普通做法判断「元素在不在一个大集合里」，要么把所有元素存 HashSet（占内存巨大），要么查数据库（慢）。布隆过滤器不存元素本身，只用一个位数组记录「这些哈希位置被人占用过」，所以：

• 空间：n 个元素只需约 n × 10 bit 就能把误判率压到 1% 左右，比存原数据小几个数量级。
• 时间：加入和查询都只是算 k 次哈希、读写 k 个 bit，O(k) ≈ O(1)。

代价就是「不精确」——它换来了空间和速度。

二、为什么「说不在一定不在，说在不一定在」

• 无假阴性：如果 x 真的加入过，它的 k 个位置必然全被置 1且再不会变 0（标准版不删）。所以查询时只要有一位是 0，就铁定没加入过。
• 有假阳性：x 没加入过，但它的 k 个位置可能被其他若干元素分别置过 1，凑巧全是 1，于是误报「可能存在」。集合越满、位数组越小、哈希越少，误判率越高。

三、误判率与参数选择

误判率 p 由三者决定：位数组长度 m、元素个数 n、哈希函数个数 k。

• 最优哈希个数 k = (m/n) · ln2。
• 给定 n 和目标误判率 p，所需位数 m = − n·ln p / (ln2)²。

直观规律：位数组越大、元素越少 → 误判越低；哈希函数不是越多越好（太多会让位数组过快填满，反而升高误判），有个最优值。

四、为什么标准布隆过滤器不能删除

多个元素可能共享同一个 bit。如果为了删除 x 而把它的某个位清 0，而这个位恰好也是 y 置的，那 y 之后会被误判成「不存在」（产生假阴性，破坏了核心保证）。所以标准版只能加不能删。需要删除就用计数布隆过滤器（Counting Bloom Filter）：每个位置存一个小计数器，加入 +1、删除 −1，代价是空间变大几倍。

五、典型应用场景

• 挡缓存穿透：查询一个数据库里根本不存在的 key，会一路穿透缓存打到 DB。先用布隆过滤器存「所有存在的 key」，查询先问它，返回「一定不存在」就直接挡掉，不查 DB。
• 爬虫 URL 去重：判断一个 URL 是否已抓过，省内存。
• 黑名单/垃圾邮件过滤：快速判断是否在名单里。
• 大数据判重：HBase、Redis（BloomFilter 模块）、比特币等广泛使用。

用它挡缓存穿透时要接受「小概率放过一些不存在的 key（假阳性）」，这些会正常查一次 DB，无害；但它绝不会把「存在的 key」误挡（无假阴性），所以安全。

六、常见误区与追问

查询结果	真实含义	原因
某一位为 0	一定不存在	插入时所有对应位都会置 1
所有位为 1	可能存在	这些 1 可能来自其他元素
误判	把不存在判断为可能存在	多个元素哈希位重叠
漏判	把存在判断为不存在	标准布隆过滤器正常不会发生

插入 keyA: h1=2, h2=5, h3=9  -> bit[2,5,9]=1
查询 keyB: h1=2, h2=5, h3=8  -> bit[8]=0，所以 keyB 一定不存在
查询 keyC: h1=2, h2=5, h3=9  -> 全为 1，只能说 keyC 可能存在

记忆钩子：布隆过滤器牺牲的是“确定存在”，保留的是“确定不存在”。它适合挡掉大量不存在请求，不适合当最终事实库。

数字例子：如果用 1000 万 bit 记录 100 万个 key，平均每个 key 分到 10 bit 的空间，再配合多个哈希函数，空间会远小于直接存 100 万个字符串。但随着插入 key 越来越多，bit 数组里 1 的比例升高，查询一个不存在 key 时所有哈希位都撞成 1 的概率也会上升。

• 误区：布隆过滤器说存在就一定存在。 它只能说可能存在，最终是否存在仍要查缓存、数据库或真实集合。
• 误区：布隆过滤器会漏掉已经插入的元素。 标准实现只置 1 不清 0，已插入元素对应位都在，正常不会漏判。
• 误区：布隆过滤器可以随便删除元素。 直接清 0 可能影响其他元素，标准布隆过滤器不支持安全删除。
• 追问：为什么哈希函数个数不是越多越好？ 太少误判高，太多会更快把 bit 数组置满，也增加计算成本。
• 追问：缓存穿透里怎么用？ 先用布隆过滤器判断 key 是否可能存在，不存在则直接拦截，减少打到数据库的无效请求。
• 追问：需要删除怎么办？ 可以考虑计数布隆过滤器，但要付出更多空间，并处理计数溢出等问题。

七、加强记忆

布隆过滤器 = 位数组 + k 个哈希函数。加入时把 k 个位都置 1；查询时有 0 则一定不存在，全 1 则可能存在——无假阴性、有假阳性、标准版不可删。它不存原数据、极省空间、查询 O(k)。经典用途是挡缓存穿透（先问它，“一定没有” 就不查库）。要删除用计数布隆过滤器。