algorithm - 跳房子哈希实际上是如何工作的？

Question

我正在阅读 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 在表的位置 1,2 中距离它们的位置 (0) H - 1 (2) 个位置内，d 在其位置 1 的 2 个位置内。
如果我尝试插入也映射到 1 的 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 个位置。
但是现在hash值映射到1的d距离1多了2个位置，已经找不到了。

那么这个算法是如何工作的呢？
注意:我的假设和理解是，跳跃值只是一种优化技巧，用于不必对属于存储桶的所有 H 元素运行相等性，并且与核心算法本身无关。 p>

Answer 1

它表示找到一个项目，其哈希值 介于 i 和 j 之间，但在 j 的 H-1 范围内。它并没有说找到当前位置位于 i 和 j 之间，而是位于 j 的 H-1 范围内的项目。索引 3 处的 d 的哈希值为 1，它不在 4 的 2 个位置内。

在你的例子中，没有合适的槽，所以下面这句话生效，应该调整表的大小并重新散列。