布隆过滤器原理
什么是布隆过滤器
布隆过滤器（Bloom Filter）是一种空间效率极高的概率型数据结构，用于判断一个元素是否”可能”存在于一个集合中。它的核心特点是：
- 如果判定不存在 → 一定不存在（零假阴性）
- 如果判定存在 → 可能存在（可能有假阳性，但概率可控）
工作原理
布隆过滤器的本质是一个很长的二进制位数组 + 一组哈希函数。
初始化
- 创建一个长度为 m 的位数组，所有位初始化为 0
- 准备 k 个相互独立的哈希函数
位数组：[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0] (m=18)
哈希函数：h1(), h2(), h3() (k=3)
添加元素
将一个元素加入布隆过滤器时：
def add(element):
for i in range(k): # k=3 个哈希函数
position = hash_i(element) % m
bits[position] = 1
以元素 “user:1001” 为例：
h1("user:1001") % 18 = 3 → bits[3] = 1
h2("user:1001") % 18 = 7 → bits[7] = 1
h3("user:1001") % 18 = 12 → bits[12] = 1
添加后位数组状态：
[0,0,0,1,0,0,0,1,0,0,0,0,1,0,0,0,0,0]
↑ ↑ ↑
查询元素
判断一个元素是否在集合中：
def contains(element):
for i in range(k):
position = hash_i(element) % m
if bits[position] == 0:
return False # 一定不存在
return True # 可能存在
如果检测 “user:1002″：
h1("user:1002") % 18 = 5 → bits[5] == 1? → 是
h2("user:1002") % 18 = 9 → bits[9] == 1? → 是
h3("user:1002") % 18 = 14 → bits[14] == 1? → 是
→ 返回 True（"可能存在"，实际可能不存在——假阳性）
如果检测 “user:9999″：
h1("user:9999") % 18 = 1 → bits[1] == 1? → 否
→ 立即返回 False（一定不存在）
假阳性率
布隆过滤器的核心参数决定了它的性能：
| 参数 | 含义 | 对假阳性率的影响 |
|---|---|---|
| m（位数组长度） | 越大空间越多，假阳性率越低 | 反比 |
| n（元素个数） | 已添加元素越多，假阳性率越高 | 正比 |
| k（哈希函数数） | 越多随机性越好，但过多会填满位数组 | 有最优值 |
最优哈希函数数量
k = (m / n) × ln(2)
假阳性率公式
P = (1 - e^(-kn/m))^k
常见配置参考
| 期望元素数 n | 假阳性率 P | 位数组大小 m | 哈希函数数 k |
|---|---|---|---|
| 100 万 | 1% | 约 12 MB | 7 |
| 100 万 | 0.1% | 约 18 MB | 10 |
| 1000 万 | 1% | 约 120 MB | 7 |
布隆过滤器的局限性
不支持删除
布隆过滤器的位可能被多个元素共享，直接清零会误删其他元素。如果需要支持删除，可以使用 Counting Bloom Filter（用计数器代替位）。
无法遍历
布隆过滤器只能回答”是否存在”，不能遍历或返回存储的元素。
全量数据重建
如果初始数据没有预加载，需要遍历所有合法 Key 来初始化布隆过滤器。
在 Redis 中的实现
方案一：自建（使用位图）
SETBIT bloom:users 0 1
SETBIT bloom:users 1 0
...
但自己实现哈希函数和位操作比较麻烦。
方案二：RedisBloom 模块（推荐）
Redis 官方提供了 RedisBloom 模块：
BF.ADD bloom:users user:1001
BF.EXISTS bloom:users user:1001 → (integer) 1
BF.EXISTS bloom:users user:9999 → (integer) 0
BF.MADD bloom:users user:1001 user:1002
BF.MEXISTS bloom:users user:1001 user:1003
# 自定义参数
BF.RESERVE bloom:users 0.01 1000000 # 假阳性率 1%，容量 100 万
与缓存穿透的结合
顺序：
1. 请求某个 Key
2. 先在布隆过滤器中判断
└── 不存在 → 直接返回 null（拦截在缓存层之前）
└── 可能存在 → 继续查缓存 → 查数据库
布隆过滤器在缓存穿透场景中的核心价值：用极小的内存开销，确定性地排除掉不存在的数据请求。
总结
布隆过滤器的本质是”用少量假阳性换取空间极致压缩”。在缓存穿透防护中，它的价值不是”完全精确”，而是”可以确定地说不”。对于存在 99% 无效请求的攻击场景，布隆过滤器可以用几 MB 内存，将 99% 的无效请求挡在缓存和数据库之外。理解和合理配置其参数（m、n、k），是在面试中展示技术深度的关键。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
暂无评论内容