hash - 探测每个 R'th 位置以进行散列

Question

我在讲座中好奇的一些事情：

假设我们要探测函数 x mod 10 和 R = 2 的每个 Rth 位置。现在散列 4、14、114、1114 和 11114：

• 4 将进入插槽 4。
• 14 会首先尝试进入插槽 4，但看到它已满，它将进入插槽 6，然后 (+R)。
• 114 会发现插槽 4 已满，进入插槽 6 (+R)，但由于已满，它将进入插槽 0 (+2R)。

但是对于 1114 来说，它似乎永远在继续——无论它去哪里，它总是会遇到一个完整的插槽。在这种情况下会发生什么？

Answer 1

对于开放寻址哈希表上不可解决的哈希冲突，有三种替代方案：

1. 用不同的散列函数重新散列整个表，并希望不会发生新的无法解决的散列冲突。
2. 调整表的大小（以及这可能导致的所有操作），以保证更多可能的插槽。
3. 为无法解决的哈希冲突保留一个单独的列表。

这些选项都不好。

您应该做的是结合哈希表大小仔细选择您的探测方法。如果您的表大小是奇数，并且具有相同的恒定步长，那么当表中仍有空间时，您将不会遇到此问题。

流行的组合包括使用素数大小的哈希表进行二次探测，如果表小于半满则保证插入成功，以及使用三角形数和 2 哈希表的幂进行二次探测，如果表不满则保证插入. 2 大小哈希表的力量有很多优点，唯一的缺点是它们对哈希算法的质量无情。