跳房子哈希实际上是如何工作的？
How does hopscotch hashing actually work?
我正在阅读 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 在 table 的位置 1,2 中距离它们的位置 (0) H - 1 (2) 个位置以内并且 d 在其位置 1.[=25 的位置 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 元素的相等性核心算法本身。
它说找到一个 哈希值 介于 i 和 j 之间，但在 j 的 H-1 范围内的项目。它没有说找到 当前位置 位于 i 和 j 之间，但在 j 的 H-1 范围内的项目。索引 3 处的 d 的哈希值为 1，它不在 4 的 2 个位置内。
在你的示例中，没有 suitable 槽，所以下面这句话生效，table 应该重新调整大小并重新哈希。
我正在阅读 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 在 table 的位置 1,2 中距离它们的位置 (0) H - 1 (2) 个位置以内并且 d 在其位置 1.[=25 的位置 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 元素的相等性核心算法本身。
它说找到一个 哈希值 介于 i 和 j 之间，但在 j 的 H-1 范围内的项目。它没有说找到 当前位置 位于 i 和 j 之间，但在 j 的 H-1 范围内的项目。索引 3 处的 d 的哈希值为 1，它不在 4 的 2 个位置内。
在你的示例中，没有 suitable 槽，所以下面这句话生效，table 应该重新调整大小并重新哈希。