布隆过滤器（Bloom Filter）是"防缓存穿透"时绕不开的数据结构。它最反直觉的一点是：没查数据库，凭什么判断一个 key 不存在？ 这篇把布隆过滤器的原理、数据来源、应用和代价从头讲清楚。

---

一、一句话理解

布隆过滤器是一个"可能存在、一定不存在"的集合——它能快速判断一个元素"可能存在"还是"一定不存在"，但不能精确判断"一定存在"。

"不存在"是 100% 准确的，"存在"可能误判。 所以它只能用来"排除一定不存在的"，不能当精确查询。

二、原理：位数组 + 多个哈希函数

底层就两样东西：一个位数组（一堆 0/1）+ 多个哈希函数。

• 添加元素：对元素算几个哈希，把对应的位都置成 1；
• 查询元素：算同样的哈希，看那几个位是不是都是 1：
  • 有任一位是 0 → 一定不存在（准确）
  • 全是 1 → 可能存在（可能误判，因为别的元素也可能把这些位碰巧置 1 了）

哈希值 → 取模 → 位置

先澄清一个容易混的点：哈希函数返回的是"哈希值"（一个整数），不是"位置"。比如 Java 的 hashCode() 返回 32 位 int，范围约 ±21 亿，位数组不可能开 21 亿长，所以要用取模把哈希值压缩到位数组下标：

int m = 1_000_000;   // 位数组长度

// hash(item, seed) 返回哈希值（int），% m 取模映射到 0~m-1 的位置
bits[hash(item, 1) % m] = true;
bits[hash(item, 2) % m] = true;
bits[hash(item, 3) % m] = true;

完整的 add / contains 就这两个方法：

class BloomFilter {
    boolean[] bits;   // 位数组，初始全 false
    int m;            // 位数组长度
    int k = 3;        // 哈希函数个数

    void add(String item) {
        for (int i = 1; i <= k; i++) {
            int pos = hash(item, i) % m;  // 哈希值取模 → 位置
            bits[pos] = true;
        }
    }

    boolean contains(String item) {
        for (int i = 1; i <= k; i++) {
            int pos = hash(item, i) % m;  // 同样的哈希 + 取模
            if (!bits[pos]) {
                return false;             // 有任一位是 0 → 一定不存在
            }
        }
        return true;                      // 全 1 → 可能存在
    }
}

对应上面那张图走一遍：

• add("user:1001")：3 个哈希函数分别算出位 0、5、9 → 把这三位置 1；
• contains("user:1001")：同样算出位 0、5、9 → 都是 1 → 返回 true；
• contains("user:9999")：算出位 1、3、6 → 发现位 1 是 0 → 直接 return false。

hash(item, i) 里的 i 表示"第几个哈希函数"——同一个元素用不同哈希函数（或同一个哈希加不同盐）算出多个不同位置，这就是"一个元素对应多个位"的来源。

为什么"一定不存在"准，而"存在"会误判

• 为什么"一定不存在"准：元素只要被 add 过，它对应的位就一定是 1；反过来说，只要有位是 0，这个元素就肯定没被 add 过。
• 为什么"存在"会误判：不同元素会共享同一位（哈希冲突）。查询一个没 add 过的元素，它的位可能恰好被别的元素都填成 1 了——布隆过滤器分不清这些 1 是谁置的，只能返回"可能存在"。

取模必然冲突（鸽笼原理）

哈希值范围约 21 亿，位数组长度假设 100 万，把 21 亿个哈希值塞进 100 万个位置，必然大量重复——这就是哈希冲突，布隆过滤器（以及 HashMap 等所有哈希结构）都躲不开。冲突带来两个后果：

1. 误判：没 add 过的元素，它的位被别的元素填满 → 误判成"可能存在"（误判率的来源）。
2. 不能删除：位是共享的，删元素要把位改回 0，但会误伤共用该位的其他元素 → 只能定期重建。

一句话记牢：位是 0 可靠（一定不存在），位是 1 不可靠（可能存在）。

三、为什么能判断"不存在"：数据来源

这是最容易困惑的地方——它没查数据库，怎么知道 key 不存在？

答案是：它初始化时把数据库里所有已存在的 ID 全量灌进去了。

• 启动时（或定时），把数据库里所有真实存在的 ID 逐个 add 进布隆过滤器；
• 之后查询 contains(key)，返回"一定不存在"，本质是"数据库里所有存在的 ID 都被我记过了，你没被记，说明数据库里根本没有你"。

这里要分清"缓存"和"布隆过滤器"存的东西不一样：

	缓存（Redis）	布隆过滤器
存什么	完整数据（key → 完整 value）	只存"存不存在"（几个哈希位）
内存开销	大	极小（每个元素只占几个 bit）
能否全量	不能，只存热点	能，全量 ID 都装得下

比如 1 亿个用户 ID：存缓存要几 GB（每条完整数据），但布隆过滤器只记"存在性"，几百 MB 就够了——所以它能全量装载，缓存不能。

四、防穿透应用

缓存穿透是"查一个根本不存在的 key，每次都穿过缓存打到数据库"。布隆过滤器的用法是：

// 启动时：全量灌入数据库所有存在的 ID
for (String id : dbIds) {
    bloomFilter.add(id);
}

// 查询时：先 contains 判断
if (!bloomFilter.contains(key)) {
    return null;          // 一定不存在 → 直接拦截，不打数据库
}
// 可能存在 → 继续查缓存 / 数据库

数据库 MySQL（全量 ID）
    │ ① 启动时全量 add（一次性）
    ▼
布隆过滤器（位图，只记存在性）
    │ ② contains(key)？
    ▼
   ├─ false → 一定不存在 → 拦截
   └─ true  → 可能存在 → 查缓存 / 数据库

五、误判率：空间和精度的权衡

tryInit(预计元素数, 误判率) 两个参数决定了位数组大小和哈希函数个数：

• 预计元素数越多 → 位数组越大；
• 误判率要求越低 → 位数组越大、哈希函数越多。

0.03 误判率的含义：存满 10 万个元素后，对"没存过的元素"查询，有 3% 的概率误判成"可能存在"。误判率越低越占内存，本质是用空间换精度。

六、代价和边界

1. 初始化有成本：启动时要全量扫一遍数据库，逐个 add。数据量大时做成异步/后台预热。
2. 新增要同步：新商品/新用户要 add 进去，否则新数据会被误判成"不存在"。
3. 不支持删除：一个位可能被多个元素共用，没法安全地把某个位从 1 改回 0。数据删了布隆过滤器里还留着"可能存在"，误判率会慢慢升高 → 一般定期重建整个布隆过滤器来兜底。

七、怎么用（实现）

• Redisson（Java 常用）：RBloomFilter，见《Redisson 实战》里的布隆过滤器一节。
• Google Guava：com.google.common.hash.BloomFilter，本地内存场景用。
• Redis 原生：BF.ADD / BF.EXISTS（RedisBloom 模块）。

小结

• 布隆过滤器 = "可能存在、一定不存在"的集合，靠位数组 + 多个哈希实现
• 能判断"不存在"的前提：初始化时把数据库全量 ID 灌进去了
• 缓存存完整数据（不能全量），布隆过滤器只存存在性（能全量），这是它俩的本质区别
• 防穿透：查询前 contains，false 拦截、true 继续
• 代价：初始化开销、新增要同步、不支持删除需定期重建

想了解缓存穿透/击穿/雪崩的完整解法，看《Redis 快速入门》里的缓存三问；想了解布隆过滤器在 Java 里的具体用法，看《Redisson 实战》。