问题标签 [hopscotch-hashing]

相关链接：http ://en.wikipedia.org/wiki/Hopscotch_hashing

Hopscotch 哈希表看起来很棒，但我在文献中没有找到这个问题的答案：如果我的邻域大小为 N 并且（由于渎职或非常倒霉）我插入 N+1 个元素，所有这些元素都散列到相同的确切值？

我正在阅读关于hopscotch hashing
该算法说当我们在插入过程中遇到碰撞时：

我不确定这是如何工作的。
例子。假设 H = 3 并且 a,b,c 都映射到 0 并且 d,e 映射到 1
我们有：

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 个位置。
所以我们可以交换并拥有：

所以现在空槽是 3，我们可以插入 e，因为它离 i 有 2 个位置。
但是现在哈希值映射到 1 的 d 从 1 开始超过 2 个位置，再也找不到了。

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