布隆过滤器（Bloom Filter）是一种用极小空间做”海量去重”和”存在性判断”的概率型数据结构：它能在几十 MB 内存里判重上亿条 URL，也是抵御缓存穿透的经典方案。本文从位数组与哈希函数的底层原理讲起，推导误判率公式，并给出 Java 手写、Guava、Redis 三种可直接落地的实现，帮你把”缓存穿透防护”从概念变成代码。
一、布隆过滤器到底是什么
普通 Set 判重需要把元素完整存下来，1 亿条字符串就要几个 GB。布隆过滤器只用一个长度为 m 的位数组（BitMap）和 k 个互相独立的哈希函数，不存原值，只存”某几位被置 1″。所以它占的空间极小，代价是：判断”可能存在”或”一定不存在”——存在判断有极小误判率，不存在判断 100% 准确。
布隆过滤器的典型用法非常广：邮箱服务用它判断”这个发件地址是否在黑名单”、网络爬虫用它做海量 URL 去重、分布式数据库用它快速判断”某一行是否可能存在”以避免无谓的磁盘 IO、CDN 与缓存系统用它拦截非法回源请求。只要业务能接受”极小概率误判存在、但绝不错杀不存在”的语义，它几乎都是最省内存的那把钥匙。理解这一点，就能判断你的场景该不该用它。
1.1 插入与查询流程
插入一个元素：用 k 个哈希函数算出 k 个下标，把位数组对应位置全部置 1。查询一个元素：同样算 k 个下标，只要有一位为 0，就”一定不存在”；全部为 1，则”可能存在”（可能误判）。这正是它适合做缓存穿透防护的原因——对不存在的 key 能零误判地拦在缓存之前。
// 伪代码：插入与查询
void add(x):
for i in 1..k:
bit[ hash_i(x) % m ] = 1
boolean mightContain(x):
for i in 1..k:
if bit[ hash_i(x) % m ] == 0:
return false // 一定不存在
return true // 可能存在（有误判概率）二、误判率公式：m、n、k 怎么选
设位数组长度 m、插入元素数量 n、哈希函数个数 k，理论误判率约为：
p ≈ (1 - e^(-k·n/m))^k给定期望误判率 p 和元素量 n，最优参数近似为：
m = - n·ln(p) / (ln2)^2 // 位数组长度
k = m/n · ln2 // 最优哈希个数经验值：想要 1% 误判率、存 1 亿个元素，m 大约需要 9.6 亿 bit ≈ 114 MB，k≈7。也就是说，用一百多 MB 内存就能给上亿级数据做判重，这是普通 Set 做不到的。注意 n 要用”未来上限”估算，元素超量会显著抬高误判率。
举个具体例子帮助建立直觉：假设要存 n=1 亿条、允许误判率 p=0.01，套公式得到 m≈9.58 亿 bit（约 114 MB），最优 k≈6.64 取 7。对比之下，若用 HashSet 存 1 亿条平均长度 32 字节的字符串，仅字符串本身就要约 3.2 GB，再算上对象头、指针与哈希桶开销轻松突破 10 GB。两者相差近 100 倍，而布隆过滤器只有 1% 误判——对绝大多数判重场景，这点误判完全可以接受。这也是为什么大型系统宁愿承受极小误判也要换这百倍的内存节省。
三、手写一个简易布隆过滤器（Java）
下面用 BitSet 和两个哈希函数演示核心逻辑，帮助理解原理。生产环境更推荐直接用 Guava 或 Redis 实现（见第四节）。
import java.util.BitSet;
public class SimpleBloomFilter {
private final BitSet bits;
private final int m;
private final int k;
public SimpleBloomFilter(int m, int k) {
this.m = m;
this.bits = new BitSet(m);
this.k = k;
}
private int[] indexes(String value) {
int[] idx = new int[k];
// 用两个不同的种子模拟 k 个独立哈希
int h1 = value.hashCode();
int h2 = h1 >>> 16 ^ Integer.hashCode(value.length());
for (int i = 0; i < k; i++) {
idx[i] = Math.floorMod(h1 + i * h2, m);
}
return idx;
}
public void add(String value) {
for (int i : indexes(value)) bits.set(i);
}
public boolean mightContain(String value) {
for (int i : indexes(value)) {
if (!bits.get(i)) return false;
}
return true;
}
}四、生产级落地：Guava / Redis / 原生
三种常见实现各有取舍，选型时看"是否需要跨进程共享"和"是否要持久化"：
| 方案 | 优点 | 缺点 | 适用场景 |
|---|---|---|---|
| Guava BloomFilter | 单机 API 简单、性能高 | 内存不跨进程、重启失效 | 单 JVM 内去重、限流判重 |
| Redis SETBIT | 跨进程共享、可持久化 | 多哈希需多次命令、有网络开销 | 分布式缓存穿透防护 |
| Redisson / RedisBloom | 一条命令完成、支持计数 | 需装 RedisBloom 模块 | 高并发判重、可删除场景 |
4.1 Guava 实现
import com.google.common.hash.BloomFilter;
import com.google.common.hash.Funnels;
// 期望插入 1000 万、误判率 1%
BloomFilter<CharSequence> bf = BloomFilter.create(
Funnels.stringFunnel(Charset.defaultCharset()),
10_000_000, 0.01);
bf.put("https://fsdata.site/a");
boolean hit = bf.mightContain("https://fsdata.site/b");4.2 Redis 用 Bitmap 实现
缓存穿透防护最经典的用法：查询 DB 前先问布隆过滤器，不存在直接返回，避免打到数据库。
# 写入：用多个 hash 把对应 bit 置 1（假设 k=3，偏移由 hash 计算）
SETBIT bf:urls 12345 1
SETBIT bf:urls 67890 1
SETBIT bf:urls 34567 1
# 查询：所有 bit 都为 1 才放过
GETBIT bf:urls 12345
GETBIT bf:urls 67890
GETBIT bf:urls 34567五、实战场景一：缓存穿透防护
缓存穿透指大量请求查询"数据库和缓存都不存在"的 key（如恶意构造的无效 ID），绕过缓存直接压垮 DB。在缓存前加一层布隆过滤器，只放行"可能存在"的 key，能把无效请求挡在 99% 以上。关于缓存穿透、击穿、雪崩的完整防护体系，可进一步参考 Redis 缓存设计：穿透、击穿、雪崩与最佳实践。查询流程如下：
Object get(String key) {
if (!bloom.mightContain(key)) {
return null; // 一定不存在，直接拦截
}
Object v = redis.get(key);
if (v == null) {
v = db.query(key); // 才允许回源数据库
redis.set(key, v, TTL);
}
return v;
}注意：新建过滤器时要先"预热"——把存量合法 key 全部 put 进去，否则会误拦真实请求。布隆过滤器本身与 一致哈希 这类分布式路由思路一样，都是用低成本结构解决大规模判重/定位问题。
需要特别强调：在缓存穿透防护里，布隆过滤器的误判只会产生"本可命中缓存的 key 被多查一次 DB"的极小代价，绝不会让非法 key 漏过——因为"不存在"判断零误判。这与它的数学性质完全吻合，也正是它适合放在回源查询之前拦截恶意穿透请求的原因。
六、实战场景二：爬虫 URL 去重
爬虫需要判断"这个 URL 是否抓过"。上亿 URL 用 Set 内存爆炸，用布隆过滤器只需百 MB 级内存。误判只会让极少数已抓 URL 被当成"未抓"重复抓一次，几乎无业务影响，性价比极高。配合 Docker 把去重服务容器化，横向扩容也很方便。
有人担心误判会让 URL 漏抓，其实漏抓只发生在"已抓过的 URL 被误判为未抓"时，最多导致重复抓取一次，不会丢数据；而真正危险的反向误判——把未抓的 URL 判为已抓——是不可能发生的，因为"不存在"判断永远 100% 准确。这也是它比对每个 URL 做精确去重更划算的根本原因：它用可控的重复抓取，换来了数量级的内存下降。
七、常见误区与排障
| 误区 | 真相 / 对策 |
|---|---|
| 布隆过滤器能删元素 | 标准实现不支持删除（会误删他人 bit）；要删除用 Counting Bloom Filter 或 RedisBloom |
| 误判率可以忽略 | 元素超量会显著升高；n 用未来上限估算并留余量 |
| 哈希越多越好 | k 过大反而填满 bit 抬高误判；按公式取最优 k |
| 不预热就上线 | 会误拦真实请求；上线前先批量 put 存量 key |
八、落地清单
① 先估算 n 和期望误判率 p，用公式算 m、k；② 单进程用 Guava，分布式/需持久化用 Redis Bitmap 或 RedisBloom；③ 上线前预热存量 key；④ 监控误判影响，误删需求上 Counting Bloom Filter；⑤ 缓存穿透场景务必把过滤器放在回源查询之前。掌握好布隆过滤器，你就能用极小的成本，解决海量去重、爬虫判重、缓存穿透这三类高频难题。
