布隆过滤器（Bloom Filter）：原理、误判与经典应用
布隆过滤器（Bloom Filter）是一种空间效率极高的概率型数据结构，用于快速判断：
一个元素“一定不存在”或者“可能存在”于某个集合中。
它最大的特点是：
-
查询速度极快：O(k)
-
占用内存极小
-
允许误判（False Positive）
-
不允许漏判（False Negative）
一、先看它解决什么问题
假设有一个系统：
已经注册的用户：
user1
user2
user3
...
user1亿
现在来了一个请求：
查询 user999999 是否存在
传统方案：
HashMap
Redis
MySQL
都需要存储完整数据。
如果只是想知道：
这个用户有没有可能存在？
没必要存完整字符串。
例如：
user1
可能占：
5~20字节
1亿个用户：
≈ 几GB
而 Bloom Filter：
可能只需要几百MB
就能完成判断。
二、核心思想
假设有一个超大的位图（Bitmap）：
索引：
0 1 2 3 4 5 6 7 8 9
值：
0 0 0 0 0 0 0 0 0 0
全部初始化为：
0
插入一个元素
插入：
apple
经过多个哈希函数：
Hash1(apple) = 2
Hash2(apple) = 5
Hash3(apple) = 8
于是：
0 0 1 0 0 1 0 0 1 0
把对应位置设为：
1
再插入：
banana
哈希得到：
1
4
8
设置：
0 1 1 0 1 1 0 0 1 0
三、如何查询
查询：
apple
再次计算：
Hash1 = 2
Hash2 = 5
Hash3 = 8
检查：
bit[2] = 1
bit[5] = 1
bit[8] = 1
全部为1：
可能存在
四、为什么说“一定不存在”
查询：
cat
哈希得到：
3
5
9
检查：
bit[3] = 0
发现一个位置为0：
一定不存在
因为：
如果插入过 cat
3位置一定被置为1
现在还是0：
说明从没插入过
这是 Bloom Filter 最重要的性质：
发现0
=
100%不存在
五、为什么会误判
看下面情况：
apple -> 2 5 8
banana -> 1 4 8
dog -> 2 4 7
位图变成：
0 1 1 0 1 1 0 1 1 0
查询：
cat
哈希结果：
1 5 8
检查：
bit[1]=1
bit[5]=1
bit[8]=1
全部为1。
Bloom Filter：
可能存在
但实际上：
cat 从未插入过
这就是：
False Positive
假阳性
误判。
六、为什么不会漏判
假设：
apple 已插入
对应：
2
5
8
这些位都已经置为1。
Bloom Filter 永远不会把：
1 改回 0
因此：
apple
再次查询：
2 5 8
一定都为1。
所以：
已存在的数据
不会被判断不存在
即：
False Negative = 0
没有漏判。
七、数学本质
本质上：
多个元素共享一个 Bitmap
例如：
10亿个元素
可能映射到：
100亿个位
每个元素：
不用存自身
只存：
k个哈希位置
例如：
7个位置
所以空间极省。
八、参数怎么选
Bloom Filter 有两个关键参数：
m
位图大小
Bitmap长度
k
哈希函数数量
Hash1
Hash2
...
HashK
经验公式：
k = (m/n) ln2
其中：
n = 元素个数
误判率：
p ≈ (1-e^(-kn/m))^k
结论：
位图越大
误判越低
哈希函数越合理
误判越低
九、实际应用场景
场景1：Redis缓存穿透
最经典。
正常流程：
请求
↓
Redis
↓
MySQL
攻击者：
查询不存在的数据
例如：
user999999999999
Redis：
Miss
数据库：
也不存在
大量请求：
数据库被打爆
解决：
请求
↓
Bloom Filter
↓
Redis
↓
MySQL
如果：
Bloom Filter 判断不存在
直接返回：
404
数据库都不用查。
场景2：爬虫去重
例如：
已爬取：
a.com
b.com
c.com
新的URL：
d.com
先查 Bloom Filter：
可能存在？
避免重复爬取。
场景3：黑名单系统
例如：
恶意IP
有：
几亿条
每个请求：
先查 Bloom Filter
快速判断。
场景4：数据库索引优化
例如：
-
Cassandra
-
HBase
-
LevelDB
-
RocksDB
都会使用 Bloom Filter。
读取数据：
先查 Bloom Filter
如果：
一定不存在
连磁盘都不用访问。
大幅减少 IO。
十、Redis 中的 Bloom Filter
Redis 官方模块：
常见命令：
BF.ADD users user1
添加。
BF.EXISTS users user1
查询。
返回：
1
可能存在。
返回：
0
一定不存在。
十一、Bloom Filter 的缺点
1. 有误判
例如：
cat
没插入过。
但返回：
存在
2. 不能删除
假设：
apple -> 2 5 8
banana -> 2 4 7
共同使用：
位置2
删除 apple：
把2改成0
会影响：
banana
导致漏判。
所以标准 Bloom Filter：
只支持增
不支持删
3. 数据越多误判越高
随着位图越来越满：
0越来越少
最终：
全部变成1
此时：
任何查询
=
可能存在
过滤效果失效。
十二、一句话理解
可以把 Bloom Filter 想成一个特殊的门卫：
问：张三在公司吗？
门卫回答：
如果看到某个登记位没被打勾：
→ 张三一定不在
如果所有登记位都被打勾：
→ 张三可能在
因此布隆过滤器本质上是：
Bitmap
+
多个Hash函数
+
允许误判
不允许漏判
它用极小的内存换取超快的存在性判断，因此广泛用于：
Redis缓存穿透
大规模去重
数据库索引
搜索引擎
分布式存储系统
爬虫系统
黑名单系统
如果你已经理解了 Bitmap，我还可以进一步画一张「Bitmap → Bloom Filter → Redis 缓存穿透防护」的结构图，把哈希映射、位图变化和误判产生过程放到同一张图里，一眼就能看懂。