algorithm - 你会通过双散列算法和二次散列算法得到相同的散列图吗？

Question

假设一个双重哈希算法，

 h(k) = k mod 29  & h'(k) = 13 - k mod 13

对于二次散列算法

 h(k) = k mod 29  & h'(k) = h(k) + (j * j)

数组大小相同的地方（例如，两种算法都是 29）。

你能分别使用这两种算法构建相同的哈希表吗？

如果您要从桶数组中输出每个单独的键（及其各自的值），那么键（来自两种算法）会在桶数组中的同一位置吗？还是键的排序方式不同？

Answer 1

如果j是常数，则不是。j不存在满足等式的常数：

13 - k mod 13 == (k mod 29 + (j * j)) mod 29

对于 的所有值k。

顺便说一句，13 - (k mod 13)是一个可怕的二级散列函数。这将您的辅助哈希限制在 0 到 12 的范围内。您最终会在前 13 个存储桶中获得比第 13 到 28 个存储桶中更多的键。

想一想，因为13 - (k mod 13)将结果限制为 0 到 12 的值，并且(k mod 29 + (j * j)) mod 29可以生成 0 到 28 范围内的值，所以答案是否定的。