布隆过滤器（腾讯）¶

一、是什么¶

布隆过滤器（Bloom Filter）是一个空间效率很高的概率型数据结构，用于判断一个元素一定不存在或可能存在。

判断"存在"：可能误判（假阳性）。
判断"不存在"：一定准确。

二、原理¶

一个 bit 数组 + 多个哈希函数。

加入元素：用 k 个哈希函数算出 k 个位置，置为 1。
查询元素：同样算 k 个位置，如果有任意一位是 0，一定不存在；全是 1，可能存在。

数组:  [0] [0] [1] [0] [1] [0] [1] [0]
加 "abc" -> h1=2, h2=4, h3=6 置 1
查 "abc" -> 2,4,6 都是 1 -> 可能存在
查 "xxx" -> 有 0 -> 一定不存在

三、应用场景¶

1. 缓存穿透¶

大量查询不存在的 key，每次打到 DB。先过布隆过滤器，不存在直接返回，不查 DB。

请求 -> 布隆过滤器(不存在) -> 返回空
          ↓ 可能存在
        Redis -> DB

2. 爬虫 URL 去重¶

判断 URL 是否已经爬过。

3. 黑名单 / 白名单¶

4. 大规模数据去重¶

四、参数选择¶

bit 数组大小 m。
哈希函数个数 k。
元素个数 n。

误判率 p：

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

经验：n=1 亿，p=1%，m 约 1.2 亿 bit ≈ 14MB，k=7。

五、缺点¶

不能删除元素：一个 bit 可能被多个元素共享，删了会影响其他。
Counting Bloom Filter：用计数器代替 bit，支持删除。
有误判：业务要容忍假阳性。
不支持遍历。

六、Java 实现¶

Guava：

BloomFilter<String> filter = BloomFilter.create(
    Funnels.stringFunnel(StandardCharsets.UTF_8),
    100_000_000,   // 预期元素数
    0.01           // 误判率
);
filter.put("user_123");
boolean mightContain = filter.mightContain("user_123");

Redis 也支持布隆过滤器模块（RedisBloom）。

面试加分

缓存穿透、缓存击穿、缓存雪崩区别：
穿透：查不存在的数据（用布隆过滤器）。
击穿：热点 key 过期，瞬间大量请求打 DB（用互斥锁、永不过期）。
雪崩：大量 key 同时过期（随机过期时间）。