算法与数据结构 · 第 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 分重点复习“探测周期”和“位移不变量”。补练不改变日期决定的课号。