4. 布隆过滤器原理：位数组与哈希函数、误判率数学推导、布隆过滤器 vs 传统 Set

布隆过滤器（Bloom Filter）是一种空间效率极高的概率型数据结构，用于判断一个元素是否属于一个集合。它允许一定的误判率（假阳性），但绝不会漏判（假阴性）。在缓存穿透保护场景中，布隆过滤器是拦截不存在 Key 的第一道防线，其核心原理由位数组与哈希函数共同构成。

4.1 核心组成：位数组与哈希函数

布隆过滤器由两个基本组件构成：

• 位数组（Bit Array）：一个长度为 m 的二进制数组，初始所有位均为 0。每个位只能存储 0 或 1。
• 哈希函数集合（Hash Functions）：一组 k 个相互独立的哈希函数，每个函数将输入元素映射到位数组的某个位置（0 到 m-1）。

插入操作：当一个元素加入布隆过滤器时，使用 k 个哈希函数分别计算该元素的哈希值，得到 k 个位数组索引，然后将这些索引位置上的位全部置为 1。

查询操作：检查一个元素是否在集合中时，同样使用 k 个哈希函数计算索引。如果所有索引位置上的位都是 1，则判定元素“可能存在”；如果任意一个位为 0，则判定元素“一定不存在”。

4.2 误判率数学推导

误判率（假阳性率）是布隆过滤器最重要的性能指标。假设位数组长度为 m，哈希函数个数为 k，已插入元素个数为 n，且哈希函数均匀随机，则误判率 p 的近似公式为：

推导过程：

1. 一个特定位在插入一个元素时，被某个哈希函数置为 1 的概率为 1/m，不被置为 1 的概率为 1 - 1/m。
2. 经过 k 个哈希函数后，该位仍为 0 的概率为 (1 - 1/m)^k。
3. 插入 n 个元素后，该位仍为 0 的概率为 (1 - 1/m)^kn ≈ e^-kn/m（当 m 较大时）。
4. 该位为 1 的概率为 1 - e^-kn/m。
5. 查询一个不在集合中的元素时，其 k 个哈希位置全部为 1 的概率（即误判率）为 (1 - e^-kn/m)^k。

最优哈希函数个数：当 m 和 n 固定时，使误判率最小的 k 值为：

下表展示了不同 m/n 比值下的误判率变化：

4.3 布隆过滤器 vs 传统 Set

传统 Set（如 HashSet、TreeSet）与布隆过滤器在缓存穿透保护场景中的对比如下：

4.4 工程实践建议

• 参数选择：根据预估数据量 n 和可接受误判率 p，使用公式 m = -n·ln(p) / (ln2)² 计算位数组大小，再计算最优 k。
• 哈希函数选择：推荐使用 MurmurHash3、FNV-1a 或 CityHash 等高性能非加密哈希函数。避免使用加密哈希（如 SHA-256），因其计算开销过大。
• 容量规划：实际数据量可能超过预估，建议将 m/n 比值设置为预估值的 1.2-1.5 倍，以应对数据增长。
• 与缓存配合：布隆过滤器应部署在缓存层之前，作为第一道过滤。对于布隆过滤器判定“可能存在”的请求，再查询缓存；缓存未命中时再查询数据库。