你会通过双哈希算法和二次哈希算法获得相同的哈希映射吗?



假设对于双哈希算法,

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

以及对于二次散列算法

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

其中数组的大小相同(例如,对于两种算法都是29(。

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

如果你要从一个bucket数组中输出每个单独的键(以及它们各自的值(,这些键(来自两种算法(会在bucket数组的同一位置吗?或者按键的排序会有所不同?

如果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之间的值,所以答案是否定的。

最新更新