双重哈希：从开放寻址到 Bloom Filter 工程实践

一、问题来源

某在线服务维护了一个规模较大的持久化键集合，最初的实现会在进程启动时把全部记录加载到内存索引中。

随着历史数据增长，这种方式逐渐暴露出两个问题：

大量低频数据长期占用内存；
某些内部流程会反复查询不存在的键，造成大量无效持久化读取。

优化后的结构分为三层：

热点缓存
    ↓ miss
Bloom Filter
    ↓ possibly present
持久化存储

查询流程如下：

热点缓存命中
    → 直接返回

热点缓存未命中，Bloom Filter 返回 false
    → 确定不存在，不访问持久化存储

热点缓存未命中，Bloom Filter 返回 true
    → 查询持久化存储
    → 命中后写入热点缓存

Bloom Filter 不是权威数据源，也不能替代持久化存储。它只负责快速判断一个键是否一定不存在。

引入 Bloom Filter 后又出现了一个计算问题：一次插入或查询需要生成 k 个位图索引，如果为每个索引执行一次完整哈希，高频路径上的 CPU 成本会随 k 增长。

开放寻址哈希表中也有一个相似问题：发生冲突后必须继续寻找其他槽位，但固定步长容易形成聚集，选择不当还可能只访问到部分槽位。

双重哈希（Double Hashing）的价值正在这里：只计算两个基础哈希值，再用简单的整数运算生成一组分散的位置。它在 Bloom Filter 中减少完整哈希次数，在开放寻址哈希表中生成冲突后的探测路径。

两种场景使用相同的数学形式，但解决的问题和约束并不完全相同。下面先从这个共同解法入手，再分别说明它为什么有效，最后回到上述服务的工程落地。

二、共同解法：起点加步长

为了用较低的计算成本生成足够分散的位置，双重哈希只计算两个基础哈希值，然后用一个线性关系生成位置序列：

p_i(x) = (h_1(x) + i × h_2(x)) mod m

其中：

x：待处理的元素；
h_1(x)：第一个哈希值，决定序列起点；
h_2(x)：第二个哈希值，决定序列步长；
i：序号，从 0 开始；
m：可用位置的总数。

当 i 依次取 0、1、2…… 时，得到：

p_0(x) = h_1(x) mod m
p_1(x) = (h_1(x) + h_2(x)) mod m
p_2(x) = (h_1(x) + 2 × h_2(x)) mod m
...

可以把它理解为：

第一个哈希决定从哪里开始
第二个哈希决定每次向前走多远

不同元素不仅起点可能不同，步长也可能不同，因此生成的位置序列通常比固定步长更分散。

2.1 递增计算

直接使用公式时，每一轮都要计算 i × h_2(x)。实际实现可以使用递增方式：

position_0 = h1
position_1 = position_0 + h2
position_2 = position_1 + h2
...

每次递增后对 m 取模即可，从而把乘法转换为加法。

2.2 步长为零的问题

如果：

h_2(x) = 0

那么所有位置都相同：

p_i(x) = h_1(x) mod m

因此工程实现通常会把零步长修正为一个非零值。

三、开放寻址哈希表中的双重哈希

3.1 哈希冲突

哈希表通过哈希函数将键映射到槽位：

index = h(x) mod m

不同键可能得到相同槽位，这就是哈希冲突。

开放寻址法不使用额外链表保存冲突元素，而是在哈希表内部继续寻找其他槽位。常见探测方式包括：

线性探测；
二次探测；
双重哈希。

双重哈希的探测序列为：

index_i = (h_1(x) + i × h_2(x)) mod m

查询或插入时，从 i = 0 开始依次探测，直到：

找到目标键；
找到可插入的空槽；
或者确认探测失败。

3.2 示例

假设哈希表长度为 7：

h_1(x) = x mod 7
h_2(x) = 5 - (x mod 5)

依次插入 14、21、28。

插入 14

h_1(14) = 0

槽位 0 为空，直接插入。

插入 21

初始位置仍然是 0，发生冲突：

h_2(21) = 4

第一次探测：

(0 + 1 × 4) mod 7 = 4

槽位 4 为空，将 21 插入槽位 4。

插入 28

初始位置同样是 0：

h_2(28) = 2

第一次探测：

(0 + 1 × 2) mod 7 = 2

槽位 2 为空，将 28 插入槽位 2。

最终分布如下：

槽位	元素
0	14
2	28
4	21

三个键具有相同起点，但第二个哈希值不同，因此沿不同路径探测。

3.3 为什么步长要与表长互质

开放寻址哈希表通常要求：

gcd(h_2(x), m) = 1

这样可以保证探测序列在重复前遍历所有槽位。取模将每个探测位置限制在 [0, m - 1] 中，而步长与表长的最大公因数决定序列能覆盖其中多少个位置。

令步长为 s = h_2(x)。探测序列中的两个位置 p_i 和 p_j 相同，当且仅当：

(i - j) × s mod m = 0

也就是 (i - j) × s 能被 m 整除。设：

g = gcd(s, m)

那么序列回到起点前的周期为：

period = m / g

因此：

当 g = 1 时，周期为 m，可以访问全部 m 个槽位；
当 g > 1 时，周期小于 m，只能访问部分槽位。

例如，表长为 8、步长为 2 时：

0 → 2 → 4 → 6 → 0

该序列只能访问一半槽位。即使其他槽位仍然为空，插入过程也无法到达。

如果步长改为 3：

0 → 3 → 6 → 1 → 4 → 7 → 2 → 5 → 0

由于 3 和 8 互质，因此能够遍历全部槽位。

质数的特殊作用

质数 p 只有 1 和 p 两个正因数。因此，如果表长 m 是质数，那么任意满足以下范围的步长：

1 ≤ s < m

都必然与 m 互质，也就必然产生长度为 m 的完整探测周期。这是双重哈希中使用质数的真正原因：它用一个简单的范围约束，替代了对每个步长单独计算最大公因数。

这里容易混淆的是：真正的条件是步长与表长互质，而不是步长本身必须是质数。

表长 m = 8、步长 s = 3：3 是质数且与 8 互质，可以遍历全表；
表长 m = 8、步长 s = 5：同样可以遍历全表；
表长 m = 15、步长 s = 3：虽然 3 是质数，但它是 15 的因数，周期只有 15 / 3 = 5；
表长 m = 7、步长 s = 4：虽然 4 不是质数，但它与 7 互质，仍可遍历全表。

因此常见设计是：

表长取质数，并把第二个哈希结果限制在 [1, m - 1]；
表长取 2 的幂，并强制步长为奇数；
表长为一般合数时，显式保证或检查 gcd(s, m) = 1。

同样的周期规律也适用于有固定间隔的键。若键为 A + i × d，对 m 取模后的周期也是：

m / gcd(d, m)

当 m 是质数时，只要 d 不是 m 的倍数，这些余数就会遍历全部槽位。这解释了为什么质数模数对等差、倍数、对齐等规律输入通常更稳健。但质数并不能弥补质量很差的基础哈希函数；工程上仍需要让 h_1 和 h_2 充分混合输入信息。

3.4 表长为 2 的幂

如果表长满足：

m = 2^r

那么任意奇数都与 m 互质。因此可以把第二个哈希值修正为奇数：

normalize_step(Value, Modulus) ->
    case (Value bor 1) rem Modulus of
        0 -> 1;
        Step -> Step
    end.

同时，模运算可以转换为位与：

hash mod m

等价于：

hash & (m - 1)

但这个优化只在 m 确实为 2 的整数幂时成立。长度按某个块大小对齐，并不代表总长度一定是 2 的幂。

3.5 优缺点

双重哈希的优点：

不同键通常具有不同的探测步长；
能缓解线性探测的一级聚集；
相比二次探测，具有相同起点的键不容易共享探测路径；
在较高负载因子下通常比简单线性探测稳定。

它的代价包括：

需要计算两个基础哈希值；
跳跃访问的缓存局部性较差；
删除通常需要墓碑标记；
步长设计不当时可能无法遍历整个表。

四、Bloom Filter 中的双重哈希

4.1 Bloom Filter 的基本原理

Bloom Filter 是一种空间效率较高的概率型集合结构，由以下部分组成：

一个长度为 m 的位图；
k 个索引位置；
插入和查询操作。

插入元素时，将对应的 k 个位置设置为 1。查询元素时，检查这些位置是否全部为 1。

判断结果具有以下语义：

存在任意一个 0：元素一定不存在
所有位置均为 1：元素可能存在

因此，Bloom Filter 允许假阳性（false positive），但正常实现不应产生假阴性（false negative）。

4.2 多次完整哈希的成本

理论描述通常假设 Bloom Filter 使用 k 个相互独立的哈希函数：

f_1(x), f_2(x), ..., f_k(x)

如果每次插入或查询都执行 k 次完整哈希，哈希计算本身可能成为高频路径上的开销。

双重哈希只计算两个基础哈希值：

a = h_1(x)
b = h_2(x)

然后派生出 k 个位置：

g_i(x) = (a + i × b) mod m

其中：

i = 0, 1, ..., k - 1

这样，一次操作只需要：

2 次完整哈希；
k 次简单整数运算。

4.3 参数计算

设：

n：预计插入的元素数量；
m：位图长度；
k：哈希次数；
b：平均为每个元素分配的位数。

可以先估算位图长度：

m ≈ n × b

理论上较合适的哈希次数约为：

k = (m / n) × ln(2)

工程实现通常会对 k 取整，并设置合理的上下限，避免异常容量导致单次操作计算过多索引。

Bloom Filter 的假阳性概率近似为：

p ≈ (1 - e^(-k × n / m))^k

增加位图长度通常可以降低误判率，但会增加内存占用；增加哈希次数只在一定范围内有效，超过理论最优值后反而可能降低效率。

4.4 Bloom 场景是否要求步长互质

开放寻址哈希表可能需要遍历全部槽位，因此通常要求步长与表长互质。

Bloom Filter 只使用序列中的前 k 个位置，不需要遍历完整位图。因此，步长与位图长度互质并不是正确性的硬性条件。

不过，如果两者存在较大的公因数，可能造成：

派生位置更容易重复；
实际有效哈希次数减少；
位分布质量下降；
假阳性概率升高。

因此仍应避免零步长，并尽量选择分散性较好的步长。

将步长修正为奇数是一种成本很低的工程手段。如果位图长度是 2 的幂，奇数步长可以保证互质；如果位图长度只是按块对齐，则奇数步长并不能严格保证互质。

五、工程落地

前文的问题背景给出了整体查询结构，本章继续说明 Bloom Filter 的构建、存储和正确性处理。

5.1 启动构建

服务启动时遍历持久化数据，完成以下工作：

统计实际元素数量；
根据元素数量计算位图长度；
计算哈希次数；
将已有键加入 Bloom Filter；
只把真正的热点记录预热到内存缓存。

这样可以避免把全部业务数据常驻内存，同时保留对不存在键的快速拦截能力。

如果启动时元素数量为 0，也不应创建长度为 0 的位图。通常需要使用一个合理的默认容量，以便运行期新增元素仍然能够写入过滤器。

5.2 使用双重哈希生成索引

下面是一段经过泛化处理的 Erlang 风格伪代码：

base_hashes(Item, BitCount) ->
    First = erlang:phash2({seed_a, Item}, BitCount),
    RawStep = erlang:phash2({seed_b, Item}, BitCount),
    Step = normalize_step(RawStep, BitCount),
    {First, Step}.

normalize_step(Value, Modulus) ->
    case (Value bor 1) rem Modulus of
        0 -> 1;
        Step -> Step
    end.

position(First, Step, Round, BitCount) ->
    (First + Round * Step) rem BitCount.

插入或查询时，只调用一次 base_hashes/2，得到两个基础哈希值：

{First, Step} = base_hashes(Item, BitCount),

Positions = [
    position(First, Step, Round, BitCount)
    || Round <- lists:seq(0, HashCount - 1)
].

两个 salt 用于区分两次基础哈希的输入域，不需要包含任何业务信息。

5.3 分块位图

如果使用一个很大的二进制保存整个位图，那么修改其中一个位可能需要重新构造较大的二进制。

一种更灵活的方案是将位图切分成固定大小的块：

完整位图
├── block 0
├── block 1
├── block 2
└── ...

这些块可以按需保存在 Map 中：

#{
    BlockNumber => BlockBinary
}

给定一个全局位索引，可以这样定位：

BlockNumber = Index div BlockBits,
OffsetInBlock = Index rem BlockBits,
ByteOffset = OffsetInBlock div 8,
BitOffset = 7 - (OffsetInBlock rem 8).

设置对应位：

<<Prefix:ByteOffset/binary, Byte:8, Suffix/binary>> = Block,

UpdatedBlock = <<
    Prefix/binary,
    (Byte bor (1 bsl BitOffset)):8,
    Suffix/binary
>>.

这种设计只需要重新构造命中的块，不需要重建整个逻辑位图。没有使用过的块也不需要提前分配。

5.4 插入流程

插入一个元素时：

1. 计算两个基础哈希值；
2. 派生 k 个位索引；
3. 将每个索引转换为块编号和块内偏移；
4. 读取对应块，不存在时创建全 0 块；
5. 设置目标位；
6. 保存更新后的块。

5.5 查询流程

查询时检查全部派生位置：

任意块不存在
    → false

任意目标位为 0
    → false

全部目标位为 1
    → true

可以使用 lists:all/2 表达这种语义：

lists:all(
    fun(Index) ->
        bit_is_set(Index, Blocks)
    end,
    Positions
).

空 Bloom Filter 可以直接返回 false，避免不必要的哈希和位图计算。

5.6 新增和删除的正确性

新增键时，必须同步更新 Bloom Filter：

写入持久化存储
    +
加入 Bloom Filter

如果持久化存储已经存在某个键，而 Bloom Filter 没有记录它，查询可能被错误拦截，从而产生假阴性。

普通 Bloom Filter 通常不支持安全删除。因为同一个位可能同时被多个元素使用，直接清零可能影响其他元素。

常见处理方式是：

删除持久化记录
保留 Bloom Filter 中原有的位

删除后可能增加假阳性，但不会造成假阴性。Bloom Filter 返回 true 时继续查询持久化存储，仍能得到正确结果。

5.7 失败降级

Bloom Filter 是性能优化层，不应成为正确性的单点。

如果过滤器构建失败、状态不可用，或者无法确认是否包含全部已有键，安全的降级方式是：

跳过 Bloom Filter
直接查询权威存储

不能把“过滤器不可用”解释为“键不存在”。