我正在阅读关于hopscotch hashing
该算法说当我们在插入过程中遇到碰撞时：
Otherwise, j is too far from i. To create an empty entry closer to i, find an
item y whose hash value lies between i and j, but within H − 1 of j, and
whose entry lies below j. Displacing y to j creates a new empty slot closer
to i. Repeat. If no such item exists, or if the bucket already i contains H
items, resize and rehash the table.
我不确定这是如何工作的。
例子。假设 H = 3 并且 a,b,c 都映射到 0 并且 d,e 映射到 1
我们有：
0 1 2 3 4 5
[a, b, c, d, , ] the table with 2 slots empty
i j
b,c 在 H - 1 (2) 位置内远离它们的位置 (0) 在表的位置 1,2 并且 d 在距离其位置 1 的 2 个位置内。
如果我尝试插入也映射到 1 I 的 e将从索引 4（通过线性探测找到的空槽）开始，并将向后工作到 1。
根据算法，索引 3（现在具有 d）在 i 和 j（分别为 1 和 4）之间并且在 H 内 - 1 即 j 的 2 个位置。
所以我们可以交换并拥有：
0 1 2 3 4 5
[a, b, c, , d , ] the table with 2 slots empty
i j
所以现在空槽是 3，我们可以插入 e，因为它离 i 有 2 个位置。
但是现在哈希值映射到 1 的 d 从 1 开始超过 2 个位置，再也找不到了。
那么这个算法是如何工作的呢？
注意：我的假设和理解是，跃点值只是一种优化技巧，它不必对属于桶的所有 H 元素运行相等且与核心算法本身无关。