假设对于双哈希算法,
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之间的值,所以答案是否定的。