Hopscotch 哈希

搬键的目的，是让洞走回来 ​

普通线性探测让新键不断远离首页。Hopscotch为每个键规定最大距离，宁可先把别的键移到它们仍可接受的位置，让空洞一步步回到新键附近。移动方向是旧键向右、空洞向左；两者不能在图或代码里混成同一个方向。

位图避免了“遇空即停”的依赖。若首页槽是空的，但位图第2位为1，查询仍应到两步外去看。删除因此可以留洞，不会截断其它键的搜索证据。

两次搬移才轮到新键 ​

取m=8、H=3、$h(k)=kmod8$，先插入0、1、2、3、4，各在首页。插入8时，首个空槽在偏移5，离首页0太远。

1. 取旧首页3，将键3从槽3移到槽5。它的新距离为2，仍小于H；hop[3]从001改为100，洞回到3。
2. 取旧首页1，将键1从槽1移到槽3。hop[1]同样从001改为100，洞回到1。
3. 距离1已在新键邻域，把8放到槽1；hop[0]变成011，表示槽0和槽1都属于首页0。

最终槽0至5的键是0、8、2、1、4、3。查键1时，读取首页1的位图100，直接比较槽3；并不是因为槽1当前存着键8，就去使用键8的首页信息。

还有五个空槽，也可能放不进去 ​

仍取m=8、H=3，键0、8、16都以0为首页，已经占满槽0、1、2。第四个同首页键24只有这三个候选槽，故不可能插入，尽管槽3至7全空。整体负载因子不能代替每个局部邻域的容量条件。

更一般地，本文确定的贪心搬移遇阻只报告“本轮未能构建”，不能自动给出所有可能重排都失败的证明。例如m=4、H=3的合法物理布局为 [空,7,4,5]，各旧键距首页都是2。插入首页为1的键1时，首个洞在槽0、偏移3；候选首页2没有记录，首页3的旧记录在偏移2而不是本轮允许搬移的位置，所以算法受阻。但把键4、1、5、7分别放入槽0、1、2、3便是一个合法满表。换更大H、扩容重哈希或改用其它候选规则，都要作为新一轮构造处理；不能把尚未存入的键当成已有成员。

H=1退化为每键只能放首页，碰撞立即受阻；H=m时任意槽都在邻域，首个空槽直接可用，不需搬移。固定的小H保证查询范围小，但不保证任何键集都能成功插入。

顺序算法的正确性和成本 ​

位图与物理记录的一一对应是主不变量。插入的一次搬移只改变某首页的两位，并把同一键值从旧槽移至新槽；其他首页的位图保持不变。严格下降的j证明过程终止，最后新键进入自己的邻域。删除反向清掉唯一对应位，故查询完整且没有假阳性；这里的“失败”是插入失败，不是近似成员误报。

以下先把位图的单个位访问、更新，以及哈希和键比较按常数操作计；可用可寻址位数组，或让H位图装入一个机器字。查询和删除最多比较H个候选，最坏O(H)。查空槽O(m)，最多m次搬移；朴素版本每次扫描至多H个候选首页及H个位，故插入保守最坏 $O(m{H}^2)$。若整个位图装进一个机器字且支持常数时间找置位，可以减少内层位枚举，但仍需说明选洞和选首页的成本。表使用O(m)键值槽和mH位邻域信息。下载器以Python整数存位图，若H跨多个机器字，移位和按位运算还须按实际字数计，不能继续当作单字操作。

原论文还有并发与分段结构。本文没有锁、原子发布或读写交错模型，不能把顺序位图证明扩展成并发安全结论；原论文的实验吞吐也不是本页最坏插入界。[1, §§2–3]

终点任务除两次搬移外，还要求删除某键的首页记录，留下该首页另一个键在偏移2处。证明此时不能见空即停，并检查位图到底归谁。下载实现与独立映射逐操作对照，插入失败前已有合法搬移的历史也保留核验。