算法与数据结构 · 第 11 课

双重哈希与 Robin Hood Hashing:如何控制聚集和探测距离?

2026 年 10 月 30 日|第 2 周 · 第 4 节|正文约 17 分钟(自测另计)

上节课的线性探测靠“home 后面逐格 +1”寻找位置,容易形成连续团簇。本节研究两种不同的改进:Double Hashing 改变探测路径;Robin Hood Hashing 不改变线性探测路径,而改变冲突时谁留下。 它们解决的不是同一个问题。

一、学习目标与问题模型(约 1 分钟)

学完应能:(1) 判断双重哈希是否能遍历整张表;(2) 手工执行 Robin Hood 的抢位交换;(3) 证明“位移小者阻止继续查找”的提前终止规则;(4) 正确删除而不让后面的键失踪;(5) 区分确定性最坏保证与依赖散列随机性的平均表现。

设表长为 (m),索引为 (0,\ldots,m-1),每访问一个槽计 1 次 probe。键唯一,比较及计算机器字长哈希为 (O(1))。本节分析的 Robin Hood 表无墓碑,始终至少留一个 EMPTY 槽;更新已有键时先 FIND,确认不存在后再做抢位插入。 双重哈希允许说明墓碑,但不把两套删除规则混用。

二、两条路线:换路径,还是换优先权?(约 2 分钟)

普通线性探测 (p_i(x)=(h(x)+i)\bmod m)。两个键即使初始 home 不同,碰撞后也可能进入同一连续区间,形成 primary clustering。

路线 A:Double Hashing(双重哈希)。 让不同键拥有不同步长:

[ \boxed{p_i(x)=\big(h_1(x)+i\,h_2(x)\big)\bmod m.} ]

这样两个键 home 相同,却可能沿完全不同的路径前进;不过若 (h_1,h_2) 都相同,它们的整个探测序列仍相同,叫 secondary clustering,并未彻底消失。

路线 B:Robin Hood Hashing。 仍然逐格 (+1),但记录键从 home 走了多远:

[ \boxed{d(x,j)=(j-h(x)+m)\bmod m.} ]

发生冲突时,若待插入键的当前位移 (d_{\rm new}) 严格大于占用者的 (d_{\rm old}),就交换:让“走得更远的穷人”抢到眼前的位置,原占用者继续向后探测。位移相等则不交换。

flowchart TD
  S["开放寻址出现碰撞"] --> A{"改进哪一环?"}
  A -->|"改变探测序列"| D["Double Hashing: home + i × step"]
  A -->|"改变冲突优先权"| R["Robin Hood: 比较当前位置的 displacement"]
  D --> C["验证 gcd(step,m)=1 才能遍历全表"]
  R --> I["距离更远的键抢位;保留提前终止不变量"]
  C --> Z["减少聚集不等于最坏 O(1)"]
  I --> Z

三、Double Hashing:为什么步长不可以随意选?(约 3 分钟)

示例取 (m=11)(素数),

[ h_1(x)=x\bmod 11,\qquad h_2(x)=1+(x\bmod10). ]

依次插入 ([0,11,22,33]):

键 home (h_1) 步长 (h_2) 实际尝试的槽 放置位置
0 0 1 0 0
11 0 2 0 → 2 2
22 0 3 0 → 3 3
33 0 4 0 → 4 4

如果改用线性探测,这四个 home 为 0 的键将依次堆在 0、1、2、3;双重哈希则把后面三个键分散开。表中的路径是确定的演示,不是对所有输入的性能保证。

核心定理: 固定一步长 (s=h_2(x)),探测序列恰好访问

[ \boxed{\frac{m}{\gcd(s,m)}} ]

个不同槽。因此走遍全部 (m) 槽当且仅当 (\gcd(s,m)=1)。

证明:第 (i) 步和第 (j) 步相同,等价于 ((i-j)s\equiv0\pmod m)。使 (ts\equiv0\pmod m) 成立的最小正整数为 (t=m/\gcd(s,m)),这就是循环周期。

反例: (m=12,s=4) 时,从 home 0 只能反复访问 (0\to4\to8\to0),其余九个槽即使为空,也无法到达。

一个简便设计是让 (m) 为素数,并确保 (1\le h_2(x)\le m-1);更一般地,对每个可能步长都检查与 (m) 互素。注意保证完整周期只意味着最迟能扫完整张表,并不保证头几次就找到位置。

DH_FIND(x):
    for i = 0 .. m-1:
        j = (h1(x) + i*h2(x)) mod m
        if T[j] == EMPTY: return NOT_FOUND
        if T[j] == ACTIVE and T[j].key == x: return FOUND
        # 其他 ACTIVE 或 DELETED:继续
    return NOT_FOUND

插入时同样沿此路径找位置;若支持更新和墓碑,应先沿路径查重直到 EMPTY 或一整圈,再复用记录的墓碑。其正确性不变量仍是:在每个 ACTIVE 键从其 home 到存放槽的探测前缀中,不存在 EMPTY。

四、Robin Hood 的数值 Trace:交换究竟发生在哪里?(约 3 分钟)

设 (m=11,h(x)=x\bmod11),依次插入 ([0,1,11,22,12])。括号中是当前位移 (d)。

插入 0、1:
槽 0: 0(d0)     槽 1: 1(d0)

插入 11(home=0):
在槽0:11 的 d0 = 0 的 d0,不交换;
在槽1:11 的 d1 > 1 的 d0,交换;
1 被挤到槽2,变为 d1。

插入 22(home=0):
槽0:0 对 0,不换;
槽1:22 的 d1 = 11 的 d1,不换;
槽2:22 的 d2 > 1 的 d1,交换;
1 被挤到槽3,变为 d2。

插入 12(home=1):一路未获得抢位机会,最后放槽4。
槽号 0 1 2 3 4 5
键 0 11 22 1 12 EMPTY
位移 0 1 2 2 3 —

算法必须小心计算被交换出去的旧键的 home,而不是继续使用最初新键的 home:

RH_INSERT_ABSENT(x):       # 事先 FIND 确认 x 不存在,且表未满
    j = h(x); d = 0
    loop:
        if T[j] == EMPTY:
            T[j] = x; return
        y = T[j]
        dy = (j - h(y) + m) mod m
        if d > dy:
            T[j] = x
            x = y; d = dy       # 继续搬运被挤出的 y
        j = (j+1) mod m
        d += 1

这个算法保持每个键从 home 沿线性探测路径都可达,而且是走得更远者优先。这里的 (d) 是当前携带键若放在当前槽的位移,不是插入操作累计循环次数。

五、为什么 Robin Hood 可以比遇到 EMPTY 更早宣布“查无此键”?(约 3 分钟)

考虑在上表 FIND(33),它的 home 也是 0。逐个检查:

槽 0:查询距离 0;存储 0 的位移 0 → 继续
槽 1:查询距离 1;存储 11 的位移 1 → 继续
槽 2:查询距离 2;存储 22 的位移 2 → 继续
槽 3:查询距离 3;存储 1 的位移 2 → 提前停止

为什么在槽 3 看到 (2<3),就能断定 33 不可能藏在后面?关键不变量是:

对任何已存键 (x),沿 home 到其实际槽位之前的每个占用槽 (j),该槽占用者的位移必须不小于 (x) 走到 (j) 时的距离。

否则,当 (x) 插入经过 (j) 时,按 Robin Hood 规则应当已经抢占这个槽;之后合法的新键插入只会通过同样规则交换,不能让一个本应抢位的键留在更后面。初始化空表显然成立,逐次抢位插入保持它(严格证明可对每次插入后的前缀关系归纳)。

因此,查询键走到距离 (d) 的槽,若占用者位移 (d_y<d),查询键若真的在后方就会违反不变量,可以提前结束。

RH_FIND(x):
    j = h(x); d = 0
    while d < m:
        if T[j] == EMPTY: return NOT_FOUND
        if T[j].key == x: return FOUND
        if displacement(T[j].key,j) < d: return NOT_FOUND
        j = (j+1) mod m; d += 1
    return NOT_FOUND

边界特别重要: 这条提前终止规则依赖没有墓碑且经过 Robin Hood 交换维护的布局。不能拿上节课普通线性探测加墓碑的表,直接启用此规则。若没有验证布局不变量,就只能使用普通的“直到 EMPTY 或扫满一圈”规则。

六、删除如何不破坏查找?Backward-Shift Deletion(约 2 分钟)

从刚才的表删除槽 2 的键 22。不能直接置 EMPTY:后面槽 3 的键 1,其 home=1,查询从槽1走到槽3时若在槽2见到 EMPTY,就会错误停止。

Robin Hood 的一种无墓碑删除方案是 backward-shift deletion(向前紧缩):把被删除的位置视作洞;检查紧接着的槽,若有键且其位移大于 0,就让它向前挪一格,并把洞向后移;直到遇到 EMPTY 或后继键位移为 0,再把洞置 EMPTY。

RH_ERASE(x):
    hole = RH_FIND_SLOT(x)
    if not found: return NOT_FOUND
    loop:
        next = (hole+1) mod m
        if T[next] == EMPTY or displacement(T[next].key,next) == 0:
            T[hole] = EMPTY
            return REMOVED
        T[hole] = T[next]
        hole = next

本例删除后的局部布局为:

删除前:槽0=0(d0), 1=11(d1), 2=22(d2), 3=1(d2), 4=12(d3), 5=EMPTY
删除后:槽0=0(d0), 1=11(d1), 2=1(d1),  3=12(d2), 4=EMPTY

每次后移操作实际是将一个键向 home 靠近一格,不会跨过它的 home;所以从该键 home 出发仍能遇到它,且不会在其前面制造 EMPTY。若下一键位移为 0,不能把它移到 home 前面,必须停止。这里要求初始表至少有一个 EMPTY,防止对满表作无界环绕。

七、复杂度与前提:两种优化不是魔法(约 2 分钟)

维度 Double Hashing Robin Hood Hashing
改变什么 每个键的探测步长 发生碰撞时的存放优先级
主要缓解 连续 primary clustering 不同键探测距离差异、长尾
仍需注意 同一 ((h_1,h_2)) 有 secondary clustering 交换可能增加插入搬运成本
查找/插入最坏时间 (O(m)) (O(m))
删除 墓碑或专门重建 无墓碑时可 backward shift
空间 (O(m)) (O(m))

两者都不能仅靠“完整周期”或“位移抢位”推出任意固定哈希函数、任意对抗键集下单次最坏 (O(1))。在明确的随机散列模型、合适负载因子、适当扩容/清理策略下,可以讨论期望查询成本及探测距离分布;Double Hashing 的实际探测序列也不是自动等价于全随机排列。Robin Hood 主要改善公平性与尾部表现,不保证每次插入、每种输入都比普通线性探测省 probes。

本节一句话: 双重哈希问“下一步走哪里”;Robin Hood 问“撞车以后谁先留下”。两者的正确性证明也不同:前者依赖探测周期与路径无 EMPTY,后者还依赖抢位产生的位移不变量。

下一课(2026-10-31,第 12 课): 哈希的动态性能与随机化失效场景:负载控制、重建的摊还成本、对抗输入与概率保证。11 月 1 日是第二周复习日(第 13 课)。

八、四级自测(共 100 分;首次只给题目与中立提示)

前 3 题可客观判分,第 4 题按证明要点评阅;首次课堂不显示任何标准答案。

Lv1|完整探测周期、Robin Hood 提前终止|15 分|预计 2 分钟|单选

关于 Double Hashing 与 Robin Hood Hashing,哪一项同时正确?

A. 双重哈希只要步长 s 不为 0,不论表长 m 是多少都一定访问全部 m 个槽。

B. 双重哈希满足 gcd(s,m)=1 才保证一个完整探测周期;无墓碑的正确 Robin Hood 表中,查找距离大于当前占用者的位移时可提前判定未找到。

C. Robin Hood Hashing 的核心是每次冲突重新随机选择一个哈希函数。

D. Robin Hood 的提前终止规则在任意墓碑删除策略下都无需修改地成立。

中立提示:分别检查模 m 的循环步长条件,以及提前终止所依赖的存储不变量。

Lv2|Robin Hood 插入、后移删除、探测计数|20 分|预计 4 分钟|数值

表长 m=7、h(x)=x mod 7。采用无墓碑 Robin Hood 线性探测(新键当前位移严格大于占用者位移才交换;相等不交换),依次插入 [0,1,7,14,8]。删除 14 并做 backward-shift deletion。随后依次 FIND(8) 与 FIND(21),启用 Robin Hood 提前终止;每访问一个槽计 1 probe,不计删除的探测。求两次 FIND 的 probe 总数。

中立提示:先标出每个键在其槽位上的 displacement;删除后按需把后续键左移,再分别记录两次 FIND 的访问序列。

Lv3|反例、概率前提、二次聚集|25 分|预计 4 分钟|多选

以下哪些判断成立?(多选,选出全部正确项)

A. 当 m=12、双重哈希步长 s=4 时,同一初始槽最多访问 3 个不同槽,即便其他槽为空也可能无法插入。

B. 只要每个双重哈希步长和表长互素,且活跃负载小于 0.8,就对任意固定输入和任意选出的哈希函数保证单次最坏 O(1) 查询。

C. 对无墓碑、由标准 Robin Hood 插入维护的表,查找某键时若当前占用者的 displacement 小于该键的当前探测距离,可以提前返回未找到。

D. 双重哈希中两个键若 h1、h2 都相同,其探测序列相同,仍可能发生 secondary clustering。

中立提示:全周期是数论条件;算法的确定性最坏时间与平均/期望时间不能混淆;想想什么时候两把键会沿完全相同的路径移动。

Lv4|模运算周期证明、插入/查询不变量、删除与复杂度|40 分|预计 10 分钟|开放推导

设计并分析两种开放寻址方案。(a)(10分)设双重哈希 p_i(x)=(h1(x)+i·h2(x)) mod m,证明它访问全部 m 个槽当且仅当 gcd(h2(x),m)=1,并给出 m 为合数时的失败反例。(b)(14分)在无墓碑且至少有一个 EMPTY 槽的 Robin Hood 线性探测表上,给出已确认不存在的新键的插入与 FIND 伪代码,明确位移 d=(位置-home+m) mod m、严格大于才交换的规则,陈述和证明支持“占用者位移<当前查询距离则停止”的不变量。(c)(9分)设计 backward-shift deletion,并解释为什么不能简单把被删槽设 EMPTY、什么时候停止后移。(d)(7分)比较双重哈希和 Robin Hood 在聚集、时间/空间复杂度方面的结论,明确完整周期和位移交换为何都不能自动推出任意输入下最坏 O(1)。

中立提示:(a) 研究模 m 的加法群中 s 的阶;(b) 想象被查键如果真的在后面,插入时是否会允许它跨过一个位移更小的占用者;(c) 考虑下一个键位移为0的情况。

九、提交与反馈

回复 Lv1:选项;Lv2:数值及关键槽位;Lv3:所有正确选项;Lv4:(a)–(d) 分步证明。按 15/20/25/40 分逐题批改:80–100 分按原计划继续,60–79 分追加针对巩固题,低于 60 分重点复习“探测周期”和“位移不变量”。补练不改变日期决定的课号。