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

双重哈希（Double Hashing）常见于两个场景：

在开放寻址哈希表中生成冲突后的探测位置；
在 Bloom Filter 中由两个基础哈希值派生多个位图索引。

两种场景使用相同的数学形式，但解决的问题和约束并不完全相同。本文先介绍其数学原理，再分别分析它在哈希表和 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
...

可以把它理解为：

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

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

1.1 递增计算

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

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

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

1.2 步长为零的问题

如果：

h_2(x) = 0

那么所有位置都相同：

p_i(x) = h_1(x) mod m

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

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

2.1 哈希冲突

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

index = h(x) mod m

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

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

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

双重哈希的探测序列为：

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

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

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

2.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

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

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

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

gcd(h_2(x), m) = 1

这样可以保证探测序列在重复前遍历所有槽位。

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

0 → 2 → 4 → 6 → 0

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

如果步长改为 3：

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

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

2.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 的幂。

2.5 优缺点

双重哈希的优点：

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

它的代价包括：

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

三、Bloom Filter 中的双重哈希

3.1 Bloom Filter 的基本原理

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

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

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

判断结果具有以下语义：

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

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

3.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 次简单整数运算。

3.3 参数计算

设：

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

可以先估算位图长度：

m ≈ n × b

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

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

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

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

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

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

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

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

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

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

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

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

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

四、匿名化工程实例

4.1 问题背景

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

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

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

优化后的结构分为三层：

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

查询流程如下：

热点缓存命中
    → 直接返回

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

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

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

4.2 启动构建

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

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

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

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

4.3 使用双重哈希生成索引

下面是一段经过泛化处理的 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.

插入或查询时，只计算一次基础哈希：

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

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

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

4.4 分块位图

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

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

完整位图
├── 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
>>.

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

4.5 插入流程

插入一个元素时：

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

4.6 查询流程

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

任意块不存在
    → false

任意目标位为 0
    → false

全部目标位为 1
    → true

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

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

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

4.7 新增和删除的正确性

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

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

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

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

常见处理方式是：

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

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

4.8 失败降级

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

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

跳过 Bloom Filter
直接查询数据库

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