Robin Hood 哈希

让已经走远的键少等一点 ​

两个键争一个槽时，刚从首页出发的键还有较短的旅程，已经绕过许多槽的键则承担了更多冲突。Robin Hood把当前槽给后者。这个规则改变的是冲突分配方式；键相等仍须实际比较，首页相同并不表示是同一键。

更重要的是，距离字段成了负查询证据。沿x的探测路线走到t步时，如果某住户连t步都没走过，x若曾到达这里就会抢占它，因此x不会安稳地留在更后面。这个解释对应路径证书，而不是未经证明的“整张表越来越有序”。

插入与后移删除的完整轨迹 ​

取m=8、$h(k)=kmod8$，依次插入0、1、8、16。值分别为键乘10。只列已占前缀，括号是距离：

8在槽1以距离1抢占距离0的键1；16在槽2以距离2抢占距离1的键1。再插入2，它经过槽2、3，最终在槽4以距离2落下。

删除8后，不能直接留下槽1为空：16的查找会在那里提前停止。依次把16从2移到1，把1从3移到2，把2从4移到3，距离各减1，最后清空槽4。结果是0(0)、16(1)、1(1)、2(1)。

后移到哪里停止，为什么安全 ​

删除命中项后把其槽视为洞。只要下一槽非空且距离大于0，就把下一记录移入洞、距离减1，洞随之右移；遇空槽或距离0的记录便停止，清空当前洞。

移动键原有路径的最后一步被删去，且被一起前移的路径位置，其要求距离和住户距离都减1；跨到未移动前缀时保留原有较强下界。因此移动项仍满足路径证书。若停止处的下一项距离为0，任何更后键若还需要跨过洞，其路线在该下一槽的步数应为正，但住户距离为0，违反删除前证书；故无需再搬它们。空槽情形同理由旧表没有跨空槽的路径保证。

键正好在首页时不能向前搬，否则其循环距离会从0变成m−1；“一直挪到下一个空槽”是错误删除规则。环绕时仍按循环距离判断，不能用普通整数槽差代替。

距离并不全局单调 ​

另从空表按0、8、16、2插入，槽0至3的距离是0、1、2、1。最后一项回落到1，表却完全合法。查不存在的24时，在槽3已走3步而住户只走1步，正好可以提前失败。

最坏情况仍可有m−1个键共享首页，成功查询或删除需线性工作。历史Robin Hood论文的随机探测方差分析，不是对任意固定线性哈希函数的最坏常数保证。墓碑版本也需重新维护查询证据；本文只证明无墓碑的后移版本。

成本和测试必须对应同一接口 ​

按常数字长键、常数哈希求值与相等比较计，固定表的查询、插入和删除各最坏O(m)，表空间O(m)记录。一次插入携带项向前走、不回头，交换次数不超过访问槽数；后移删除同样最多绕一圈。扩容、随机种子选择与摊还界另行分析，不能从抢占规则直接推出来。

距离也可由槽位和完整键重算，或存入足以表示0至m−1的字段；若工程实现把它压成小整数，溢出必须触发重建或拒绝，不能静默回绕，否则提前失败会制造假阴性。

终点任务逐操作与独立映射比较，同时检查物理键唯一性和每个路径不等式。迁移时把同首页碰撞簇移到槽7，使其跨越表尾；再删除其中间项，列出实际槽和循环距离。若实现只在不环绕的示例正确，这个检查会立即暴露差异。