布隆过滤器用一块位数组加 k 个哈希函数，以极小的空间回答「某个元素是否可能存在」：它说不在就一定不在，它说在则有小概率是误判。这个不对称的特性，决定了它适合做「快速排除」，而不是「保存事实」。

它解决什么问题

海量集合的存在性判断是个经典难题：亿级 URL 爬虫去重、千万级黑名单过滤，如果把原始数据全塞进哈希集合，内存先被压垮。布隆过滤器给出的交易是——不存元素本身，只存它的「指纹」，用可控的误判率换取数量级的空间压缩。它适配的业务画像是：宁可小概率误杀（把不在的说成在），绝不能漏判（把在的说成不在）。

核心原理

结构只有两部分：长度为 m 的位数组（初始化全 0），以及 k 个相互独立的哈希函数。

  • 插入 x：计算 k 个哈希值，把对应的 k 个位置置为 1。
  • 查询 x：检查同样的 k 个位置。只要有一位是 0，x 一定没被插入过；全部为 1，只能说「可能存在」。

误判的来源很直观：位是被所有元素共享的，别的元素的哈希位置恰好把你要查的 k 个位置全部点亮，一个从未插入的元素就会被误报为存在。反过来，已插入元素的 k 个位在插入那一刻就全是 1，只要没有人乱清位，它永远查得到——所以标准布隆过滤器没有假阴性。

这也解释了为什么不能删除：清零某一位，可能同时抹掉了其他元素赖以「自证存在」的标记，直接制造出假阴性，摧毁了布隆过滤器唯一的硬保证。

深入机制

假阳性率的直觉推导

往 m 位的数组里置一位，某个特定位仍为 0 的概率是 1 - 1/m；一个元素置 k 位后仍是 0 的概率约 (1 - 1/m)^k；插入 n 个元素后，该位仍是 0 的概率约 e^(-kn/m)。查询一个不在集合中的元素，要求它的 k 个位恰好全为 1，于是假阳性率：

p ≈ (1 - e^(-kn/m))^k

结论：n 固定时，m 越大 p 越低；m 固定时，n 越接近设计容量，位数组越「满」，p 越高。超过预估容量继续加数据，误判率会不可控地攀升。

参数怎么估：m、n、k 的关系

给定预估元素数 n 和目标误判率 p，可以反推出最优配置。数学上可以证明，当 k = (m/n)·ln 2 时 p 取到最小，此时每位成本为：

m/n ≈ -1.44 · log2(p)

代入几个数感受一下：p = 1% 时每个元素约需 9.6 bit、最优 k ≈ 7；p = 0.1% 时每元素约 14.4 bit、k ≈ 10。也就是说，一亿条数据做到 1% 误判率，只需要约 120 MB——远小于存原始字符串。

k 为什么不能乱取？太少，k 个位置的区分度不够，误判高；太多，每次插入点亮的位太多，数组更快饱和，且每次查询要多算几次哈希。最优 k 恰好让位数组维持在约一半为 1 的「半满」状态，信息密度最高。Guava 的 BloomFilter.create(funnel, n, fpp) 内部就是按这套公式反推 m 和 k。

// 预估插入 100 万个整数，目标误判率 1%
BloomFilter<Integer> filter = BloomFilter.create(
        Funnels.integerFunnel(), 1_000_000, 0.01);

filter.put(42);
boolean maybe = filter.mightContain(42);   // true：可能存在
boolean no    = filter.mightContain(-7);   // false：一定不存在

注意 mightContain 返回 true 的语义是「不能排除」，而不是「有 99% 把握存在」——1% 是对未插入元素的误报率，不是后验概率。

支持删除的变体

  • 计数布隆过滤器：把每一位换成一个小计数器，插入 +1、删除 -1，归零即清除。代价是空间放大 3~4 倍，还要处理计数溢出。
  • 布谷鸟过滤器：换个思路，存元素的指纹（fingerprint）而不是共享位。每个元素有两个候选桶，插入失败时把桶里已有元素踢到它的另一个候选桶，级联重定位。它支持删除、查询最多只摸两个桶（缓存友好），高负载下空间利用率甚至优于布隆过滤器；弱点是踢出链过长时插入会失败，且重复插入同一元素次数有上限。

工程实践

  • 缓存穿透防护：把数据库里存在的 key 预先灌进过滤器，请求先过一道——过滤器说不在就直接返回，恶意刷不存在 key 的流量打不到数据库。代价是少量误判请求会多查一次库，可接受。
  • 爬虫与推荐去重：亿级 URL 粗去重，误判的代价只是漏爬极少数页面；推荐系统用它过滤已曝光内容。
  • LSM 存储引擎：LevelDB、RocksDB、HBase 给每个 SSTable 文件挂一个布隆过滤器，读键前先问过滤器「这个文件里可能有吗」，把大量无效的磁盘 IO 直接省掉。
  • 单机还是分布式：Guava 实现活在进程内，简单高效；多节点共享同一份过滤状态时用 RedisBloom（Redis 8 起已内置），代价是每次判断多一次网络往返。

对比与权衡

维度 布隆过滤器 计数布隆过滤器 布谷鸟过滤器 哈希集合
精确性 有误判，无漏判 同左 同左 完全精确
删除 不支持 支持（计数器） 支持 支持
空间 每元素约 1.44·log2(1/p) bit 约为前者的 3~4 倍 高负载时更优 存原始元素，最大
查询成本 k 次哈希 + k 次访位 同左 最多 2 个桶，缓存友好 1 次哈希 + 比较
容量超限 误判率攀升 误判率攀升 + 溢出风险 插入可能失败 扩容继续用

面试视角

为什么会误判？会不会漏判？ 位被所有元素共享，别的元素可能恰好把某个未插入元素的 k 个位全点亮，产生假阳性；而已插入元素的 k 个位在写入时就全部置 1，只要位不被清掉就永远查得到，所以没有假阴性。

为什么不能删除？ 清零共享位会误伤其他元素，制造假阴性。要删除就换计数布隆过滤器或布谷鸟过滤器。

位数组开多大、哈希函数用几个？ 由预估容量 n 和目标误判率 p 反推：每元素约需 1.44·log2(1/p) bit，最优 k = (m/n)·ln 2。拍脑袋开一块位图而不做容量规划，是布隆过滤器最常见的误用。

容量估小了会怎样？ 元素超过设计值后位数组迅速饱和，误判率失控上升，且无法原地扩容——只能按更大的容量重建并重新灌入全量数据。

它适合做什么、不适合做什么？ 适合「快速排除不可能」：穿透防护、粗去重、读前过滤。不适合当权威数据源：所有「可能存在」的命中都必须回源确认，更不能拿它做安全鉴权。

小结

  • 布隆过滤器 = 位数组 + k 个哈希，语义是「一定不在 / 可能在」，用可控误判换数量级的空间节省。
  • 假阳性率 p ≈ (1 - e^(-kn/m))^k，最优 k 下每元素约需 1.44·log2(1/p) bit。
  • 标准版不能删除；需要删除时用计数布隆过滤器或布谷鸟过滤器。
  • 工程定位是前置挡板：挡得住的绝不回源，挡不住的回源确认。