布隆过滤器只做一次哈希，怎么模拟 7 次独立哈希？

一句话结论（30s）

双重哈希的本质是：用一次 128 位哈希的高、低 32 位构造出 h1、h2 两个哈希函数，再通过线性组合 h_i(x) = h1 + i × h2 派生出 k 个哈希位置，用「两个哈希函数生成 k 个哈希」来降低碰撞——之所以成立，是因为 Kirsch & Mitzenmacher 在论文里证明了这种线性组合取模后的分布均匀性与 k 次独立哈希等价，所以只调一次 MurmurHash3 就能模拟 7 次独立哈希，把哈希计算开销降为原来的 1/k。

背景诉求

布隆过滤器定位一个元素需要 k 个独立哈希函数来计算 k 个位数组位置，如果每个位置都单独调一次 MurmurHash3，插入和查询的开销都会被放大 k 倍。在缓存穿透防护场景里，布隆过滤器挡在 Redis 和数据库之前，承担每秒百万级查询的过滤，哈希计算是热路径上的固定成本——逐个计算 k 次哈希的开销太大，这是必须要解决的痛点。

目标边界

目标：用一个（或极少）哈希调用，模拟出 k 个统计上独立的哈希位置，同时不损失误判率的控制精度。
边界：不追求「完美独立哈希」，只要求组合后位置分布的均匀性等价即可；同时不处理删除语义——因为缓存穿透防护的场景是「只加不删」。

核心难点

哈希相关性：如果由同一个哈希函数机械地派生 k 个位置，这些位置之间可能高度相关，导致同一元素的位置聚集、位数组利用率下降、实际误判率上升。
误判率控制：误判率由 m、n、k 共同决定（p ≈ (1 - e^(-kn/m))^k），派生的 k 个位置必须保持统计独立，否则理论误判率公式就会失效。

关键取舍

取舍一：k 次独立哈希 vs 双重哈希。前者数学上最干净但 CPU 开销大；后者用一次 128 位哈希 + 线性组合，换来初始化时间约 40% 的下降。
取舍二：依赖 MurmurHash3 128 位输出高、低 32 位统计独立的特性，用「一次调用拆成两个哈希」替代「两次调用」。
取舍三：位数组大小 m 与误判率的平衡。m 决定内存占用（约 5.7MB），误判率（1%）决定可接受的漏过滤代价——空间与精度的 trade-off。

个人行动

在项目中用 Guava BloomFilter 落地缓存穿透防护：配置预期 500 万 Key、误判率 1%，让库自动算出 m = 47,962,029 bits ≈ 5.7MB、k = 7，底层只用 1 次 MurmurHash3 调用。
读懂并复述双重哈希的实现：一次 128 位哈希拆成高、低 32 位，再用 combinedHash = hash1 + i * hash2 做取模定位。

结果与复盘

结果：初始化时间从 k 次独立哈希的 ~18s 降到 ~11s，减少约 40%；查询热路径上每定位一次少算 6 次 MurmurHash3。
复盘：最大的收益其实不在初始化，而在 contains() 每秒百万级查询里实打实省下的 CPU——「用一个数学上等价的技巧替代 k 个调用」是通用的性能优化思路。留一个钩子：删除场景可用 Counting Bloom Filter（每个位置扩成 4 bit 计数器）解决，但空间膨胀 4 倍。

三版本回答

30 秒版（一句话）

双重哈希的本质是：用一次 128 位哈希的高、低 32 位构造 h1、h2 两个哈希，再线性组合 h1 + i × h2 派生 k 个位置，因为数学上被证明与 k 次独立哈希等价，所以只调一次 MurmurHash3 就能模拟 7 次独立哈希，既降低碰撞又把哈希开销降为原来的 1/k。

2 分钟版（电梯陈述）

布隆过滤器需要 k 个独立哈希函数定位 k 个位置，逐个计算开销太大。难点在于：由同一个哈希函数机械派生位置，会导致位置高度相关、误判率失控。Guava 用双重哈希解决——一次 MurmurHash3 128 位输出拆成高、低 32 位作为 h1、h2，再按 h1 + i × h2 线性组合出 k 个位置；Kirsch & Mitzenmacher 的论文证明了这种组合取模后的分布与 k 次独立哈希等价。落地后，初始化时间从 k 次独立哈希的 ~18s 降到 ~11s（约 40%），而更大的收益在 contains() 每秒百万级查询里省下的 6 次哈希调用。

5-10 分钟版（深度展开）

可以分四层展开：

源码细节：hash64 = murmur3_128(key).asLong() 只调一次，hash1 = (int) hash64 取低 32 位、hash2 = (int) (hash64 >>> 32) 取高 32 位，然后 for (i = 0; i < k; i++) combinedHash = hash1 + i * hash2，对位数组大小 m 取模定位。
数学等价：论文 Less Hashing, Same Performance（Kirsch & Mitzenmacher, 2008）证明 h_i(x) = h_1(x) + i × h_2(x) 线性组合取模后的分布均匀性与 k 次独立哈希等价；两个关键约束是 h1、h2 相互独立（MurmurHash3 128 位输出的高、低 32 位在统计上独立），以及 m 与哈希值满足一致分布。
边界与删除：位数组的一个 bit 可能被多个 Key 共用，直接清零会误删其他 Key；删除场景要用 Counting Bloom Filter（每个位置从 1 bit 扩成 4 bit 计数器，插入 +1、删除 -1），代价是空间膨胀 4 倍。Guava 没有内置实现，因为它的设计场景就是「只加不删」的缓存穿透防护。
数据闭环：k 次独立哈希初始化 ~18s → 双重哈希 ~11s（约 40% 下降）；项目配置里 500 万 Key、1% 误判率自动算出 m ≈ 4796 万 bits（约 5.7MB）、k = 7。

底层深入（技术细节）

问题

布隆过滤器需要 k 个独立的哈希函数来定位 k 个位数组位置。直接调 k 次 MurmurHash3 计算量太大，Guava BloomFilter 只调了一次哈希是怎么模拟出 7 次独立效果的？

原理：Double Hashing

Guava 使用”双哈希（Double Hashing）“技巧，原理来自论文 Less Hashing, Same Performance: Building a Better Bloom Filter（Kirsch & Mitzenmacher, 2008）：

long hash64 = Hashing.murmur3_128(key).asLong();  // 只调一次 MurmurHash3
long hash1 = (int) hash64;                         // 低 32 位
long hash2 = (int) (hash64 >>> 32);                // 高 32 位

for (int i = 0; i < k; i++) {
    // h_i(x) = hash1 + i × hash2
    long combinedHash = hash1 + i * hash2;
    bitArray.set(combinedHash % m);
}

为什么数学上等价

Kirsch & Mitzenmacher 在论文中证明了：h_i(x) = h_1(x) + i × h_2(x) 这种线性组合在取模后的分布均匀性与 k 次独立哈希函数等价。

关键约束：

h_1 和 h_2 是相互独立的哈希函数（MurmurHash3 的 128 位输出的高 32 位和低 32 位在统计上独立）
位数组大小 m 和哈希值需要满足一致分布

想一想：为什么一次哈希就能模拟 k 次独立哈希？ 因为 128 位哈希的高 32 位和低 32 位在统计上相互独立，正好充当两个独立哈希 h1、h2；再用 h_i = h1 + i × h2 线性组合出第 i 个位置。论文证明这种组合取模后的分布均匀性与 k 次独立哈希等价——也就是说”独立性”这个性质，用两个独立的种子就能派生出 k 个位置，而不必真去算 k 次。

性能收益

方案	哈希调用次数	5 千万 Key 初始化时间
k 次独立 MurmurHash3	k 次	~18s
Double Hashing	1 次	~11s（减少约 40%）

布隆过滤器日常操作里 contains() 也需要 k 次哈希定位——每秒百万次查询时，减少 6 次 MurmurHash3 调用是实打实的 CPU 省下来。

想一想：为什么真正的收益在 contains() 而不只是初始化？ 因为初始化的 18s → 11s 是一次性的，而 contains() 在缓存穿透防护里每秒要执行百万次，每次都省 6 次 MurmurHash3 调用，这个节省是持续的、累计的。所以性能优化要看”热路径上的固定成本”，而不是只看一次性开销。

补充：布隆过滤器为什么不能删除

位数组的一个 bit 可能被多个 Key 共用——删除一个 Key 时把它对应的 bit 清零，会导致其他共用这个 bit 的 Key 被”误删”。

解决方案：Counting Bloom Filter——每个位置从 1 bit 扩展为计数器（4 bit），插入 +1，删除 -1。代价是空间膨胀 4 倍。Guava 没有内置实现，因为 Guava 设计场景是”只加不删”的缓存穿透防护。

项目中的配置

BloomFilter<String> filter = BloomFilter.create(
    Funnels.stringFunnel(StandardCharsets.UTF_8),
    5_000_000,    // 预期 500 万 Key
    0.01          // 误判率 1%
);
// → 自动计算：m = 47,962,029 bits ≈ 5.7 MB
//           k = 7 个哈希函数
//           只用 1 次 MurmurHash3 调用

章末提问

Q1：为什么只用一次哈希就能模拟 k 次独立哈希？ 结论先行：因为把一次 128 位哈希的高、低 32 位拆成两个独立哈希 h1、h2，再用线性组合 h1 + i × h2 派生出 k 个位置。因为 MurmurHash3 的 128 位输出高、低 32 位在统计上独立，天然提供两个独立种子；Kirsch & Mitzenmacher 的论文证明 h_i(x) = h1 + i × h2 取模后的分布均匀性与 k 次独立哈希等价。于是只调一次哈希，就拿到 k 个”统计独立”的位置。

Q2：双重哈希数学上等价有什么约束条件？ 结论先行：两个关键约束——h1、h2 必须相互独立，且位数组大小 m 与哈希值满足一致分布。因为等价性的前提是”种子独立”，若 h1、h2 相关，派生出的位置会聚集、误判率失控；而 m 与哈希值的一致分布保证取模后位置均匀。这两个条件任一不满足，理论误判率公式 p ≈ (1 - e^(-kn/m))^k 就失效。

Q3：布隆过滤器为什么不能删除？要删除怎么办？ 结论先行：因为位数组被多个 key 共享，清零一个 bit 会误伤其他 key；要删除就得换 Counting BF，但空间膨胀 4 倍。因为过滤器不记录”某个 bit 是哪个 key 置的”，删除是不可逆的。Counting BF 把每个位置从 1 bit 扩成 4 bit 计数器，插入 +1、删除 -1，解决了删除问题，代价是空间膨胀 4 倍。Guava 没有内置它，因为缓存穿透防护是”只加不删”场景，用不上。

布隆过滤器的双重哈希技巧