编程面试：如何实现 Robin Hood Hashing？
题干与适用场景
实现一个固定容量的开放寻址哈希表，槽位数组长度为 m，每个槽最多存放一个键值对。要求支持 insert(key,value)、contains(key) 和 remove(key)；冲突处理使用 Robin Hood Hashing，不使用链表，也不使用 tombstone。为了聚焦核心算法，本题先假设容量不足时返回失败，不负责扩容。
这是一道通用编程面试题，核心考察数据结构、不变量、边界测试和复杂度推导。Stanford CS106B 的公开作业要求学生实现 Robin Hood 表，并明确包含“按探测距离交换”“提前结束查找”和“向后移动删除”三个差异点。当前软件工程面试指南也把数据结构选择、正确性、复杂度和边界处理列为编码轮评价信号。
面试官考察点
- 能否把每个元素的 home bucket 与 PSL（probe sequence length，探测序列长度）存进槽位。
- 能否说明插入时“更穷者优先”：当前元素 PSL 更大时，与较近 home 的驻留元素交换。
- 能否用 PSL 单调性提前结束失败查找，而不是无条件扫描整个数组。
- 能否不用 tombstone 删除，同时保持同一探测簇中的查找可达。
- 能否给出平均、最坏复杂度，并说明高负载时延迟和失败策略。
普通回答会写出线性探测，却遗漏删除后空洞会截断查找；强回答会把“槽位为空”与“槽位 PSL 小于待查元素 PSL”都变成可证明的停止条件。
回答前需要澄清的问题
- 容量是否固定？固定容量时插入失败必须是显式结果；允许扩容则需要在负载因子阈值触发重建。
- 是否允许重复键？本题假设重复键更新 value，不新增槽位；如果要多值映射，应改变 API 和删除语义。
- 哈希函数是否稳定、键是否可复制？哈希结果必须在一次操作中稳定；若哈希昂贵，可以缓存 home bucket，但缓存会增加槽位内存。
- 是否要求迭代器或引用稳定？向后移动会搬迁元素，因此不能承诺地址稳定；如果需要稳定引用，应使用间接存储或链式结构。
- 并发是否在范围内？本题是单线程；并发版本需要锁、分段或无锁协议，不能把普通实现直接宣称线程安全。
30 秒回答框架
“我会在每个槽位保存 key、value、home bucket 和 PSL。插入从 home bucket 线性探测；如果当前元素的 PSL 大于槽内元素，就交换两者，让探测更远的元素先占据位置，然后继续安置被换出的元素。查找遇到空槽，或遇到槽内 PSL 小于目标 PSL 时可以提前失败，因为后续元素不可能跳回更近的位置。删除后从下一个槽开始向后搬移，直到遇到空槽或 PSL 为零的元素，逐个把 PSL 减一，避免留下会截断探测链的空洞。平均操作接近 O(1)，最坏仍是 O(m)，空间 O(m)。”
分步骤深入解答
1. 槽位模型与不变量
每个非空槽保存 (key, value, home, psl)。在容量为 m 的环形数组中，psl = (index - home + m) % m。必须维护三个不变量：
home是该键哈希后的固定起点。- 从
home沿环向前走psl步正好到达当前 index。 - 同一连续探测簇内，非空槽的 PSL 不递减；空槽会结束该簇。
第三条不变量来自插入时的“更大 PSL 优先”交换。它让查找可以比较目标 PSL 与当前槽 PSL，而不必检查后面的所有槽。
2. 线性探测插入的瓶颈
最简单的线性探测会从 home 向后找空槽。高负载时，早到的元素可能占据离 home 很近的位置，晚到且已探测很远的元素被迫继续走很长距离；探测长度的方差会拉高尾延迟。Robin Hood 策略不改变开放寻址的基本数组布局，只在冲突时把更远的元素“优先”安置。
3. Robin Hood 插入
伪代码如下：
insert(key, value):
item = (key, value, home=hash(key), psl=0)
for step in 0 .. m-1:
i = (item.home + item.psl) mod m
if table[i] is empty:
table[i] = item
return success
if table[i].key == key:
table[i].value = value
return updated
if table[i].psl < item.psl:
swap(table[i], item)
item.psl += 1
return full交换后继续循环时，item 是被赶出的元素；它的 PSL 已经对应当前探测位置，下一轮再加一。实现中要避免把“空槽”当成 PSL 为零的元素，否则首次插入和删除边界会混淆。
4. 查找与提前终止
查找从目标 home 开始，维护目标 PSL：
contains(key):
home = hash(key)
for psl in 0 .. m-1:
i = (home + psl) mod m
if table[i] is empty:
return false
if table[i].psl < psl:
return false
if table[i].key == key:
return true
return false如果当前槽为空，探测簇已经结束；如果当前槽 PSL 小于目标 PSL，后续槽位的 PSL 不会下降到能容纳目标的位置，因此目标不存在。Stanford 作业把这个提前结束条件作为 Robin Hood 与普通线性探测的核心差异之一。
5. 向后移动删除
不能直接把槽清空：后面的键可能是跨过该槽冲突后放入的，查找会在空洞处错误返回 false。也不能使用 tombstone，因为题目明确禁止，且长期 tombstone 会拉长探测。
remove(key):
i = find_index_or_not_found(key)
if i is not found:
return false
j = (i + 1) mod m
while table[j] is not empty and table[j].psl > 0:
table[i] = table[j]
table[i].psl -= 1
i = j
j = (j + 1) mod m
table[i] = empty
return true遇到空槽或 PSL 为零的元素就停止：前者代表簇结束，后者说明该元素就在自己的 home，删除前面的空位不会截断它的查找路径。每次搬移都把 PSL 减一，恢复“当前位置距离 home 一步变短”的不变量。
6. 复杂度与高负载决策
在均匀哈希和负载因子 α 远低于 1 时，插入、查找和删除的期望探测次数为常数级；单次操作最坏可能扫描全部 m 个槽，因此最坏时间是 O(m)，空间是 O(m)。Robin Hood 主要改善探测长度的分布和方差，不改变开放寻址的最坏上界。论文分析了高负载下搜索成本方差仍可保持有界的情形，但工程实现仍应设负载阈值。
当 α 接近阈值时，优先扩容重建，而不是继续依赖平均 O(1)。如果必须固定容量，应把 full 作为正常业务结果，并对失败率、平均 PSL、P99 探测次数和删除搬移长度做监控。
7. 反例与测试
- 空表插入和查找：确认 home 槽直接放入，查找不存在键遇到空槽立即失败。
- 重复键：插入同一 key 只更新 value，元素数量不增加。
- 环形回绕：让 home 接近数组尾部，验证
(index - home + m) % m正确。 - 交换链：构造多个碰撞键，确认一次插入可连续交换并最终放置所有元素。
- 删除簇头、中间和尾部：每次删除后检查原簇中所有剩余键仍可找到。
- 删除 home 元素：后继 PSL 为零时停止搬移，避免把另一簇错误搬进来。
- 满表：插入第
m+1个不同键必须返回失败，不能无限循环。 - 对抗哈希：让大量键映射同一 home，确认结果仍正确，且监控能暴露 O(m) 探测。
高质量示范回答
“我会使用固定容量的 Robin Hood 开放寻址表，每个非空槽保存键值和 PSL。插入时从 home 开始线性探测；当前元素如果比槽内元素离 home 更远，就交换两者，继续安置被换出的元素。这样一个探测簇里的 PSL 保持不递减。
“查找可以利用这个不变量：遇到空槽直接失败，遇到槽内 PSL 小于目标 PSL 也失败，因为后续不会回到更近的距离。删除不能留下空洞，所以我从删除点向后搬移 PSL 大于零的元素，并将其 PSL 减一；遇到空槽或 PSL 为零就停止。平均时间接近 O(1)，但最坏是 O(m)，所以我会用负载因子、P99 探测和搬移长度决定扩容或拒绝插入。向后移动会改变元素地址，因此我不会承诺稳定迭代器或引用。”
常见错误
- 错误表现 → 冲突时永远让先到元素留下 → 后到元素探测距离无限拉长 → 当新元素 PSL 更大时交换。
- 错误表现 → 查找只在空槽时失败 → 失去 PSL 单调性的优化 → 当前槽 PSL 小于目标时也应停止。
- 错误表现 → 删除后直接清空槽位 → 空洞截断后继键的探测路径 → 使用向后移动并逐步减小 PSL。
- 错误表现 → 删除搬到遇到任意元素就停 → 可能留下无法到达的键或跨簇搬移 → 只搬移连续簇中 PSL 大于零的元素。
- 错误表现 → 把平均 O(1) 写成最坏 O(1) → 高负载或坏哈希时结论失真 → 明确最坏 O(m)，并设置负载阈值。
- 错误表现 → 承诺引用地址稳定 → 交换和删除会搬迁元素 → 返回句柄、间接指针或放弃地址稳定承诺。
追问及应对
如果要求动态扩容，什么时候触发重建？
按负载因子和探测尾延迟共同触发，例如达到预设 α 或 P99 探测超过预算时扩容到更大的数组。重建时重新计算所有 home 和 PSL，不能直接复制槽位，因为数组模数改变。扩容期间可用写锁、双表迁移或后台重建，但要先说明一致性和暂停写入策略。
为什么不用 tombstone，向后移动的成本会不会太高？
tombstone 让删除 O(1)，但会永久增加查找路径，除非定期重建；向后移动把成本集中在删除操作，并保持簇内结构紧凑。删除频率极高、读很少时 tombstone 加周期性重建可能更合适；读延迟敏感时优先向后移动，并监控单次搬移长度。
并发读写怎样处理？
这份实现是单线程。最简单的并发方案是读写锁，但写入交换和删除搬移必须在一个写临界区内完成，读者不能看到半完成簇。更高吞吐可以分段加锁或使用不可变快照；无锁版本需要版本字、内存序和回收协议，不能只给槽位加原子指针就声称正确。
Robin Hood 会让平均查找次数变成常数吗？
在常见均匀哈希模型下，开放寻址的期望探测成本与负载因子有关，Robin Hood 的主要收益是降低探测长度方差和尾部波动。高负载时平均成本仍会上升，最坏仍可能扫描整个表；因此不能用“方差更小”替代负载控制和实测基准。