data-structures - 如果双哈希函数也失败了怎么办

Question

考虑使用带有散列函数的开放寻址将键 10、22、31、9、15、28、62、88 插入到长度为 m = 11 的散列表中h(k) = k mod m。说明使用 h2(k) = 1 + (k mod(m-1)) 的双重散列插入这些键的结果。

以下是我的方法。

0 -> 22 , Since 22 mod 11 = 0
1 ->
2 ->
3 ->
4 ->
5 ->
6 ->
7 ->
8 ->
9 -> 31 , Since 31 mod 11 = 9
10 -> 10 , Since 10 mod 11 = 10

好的，当尝试将密钥 9 放入哈希表时，问题就来了。

h(9) = 9 mod 11，即 9。我不能放 9，因为 9 已经消失了。然后我尝试给定 h2(9) = 1 + (9 mod (11-1)) 的双哈希函数，它是 10，它又消失了。所以我仍然不能将 9 放入哈希表中。在这种情况下我该怎么办。

score 3 · Accepted Answer

像这样使用两个哈希函数：

hi=(h(key)+i*h1(key))％m 0≤i≤m-1

换句话说：您每次都增加第二个哈希函数的值，并h1根据需要进行环绕。

因此，您要查找密钥的地址列表如下：

h(key), h(key)+h1(key), h(key)+2*h1(key), ... , h(key)+n*h1(key)

score 0 · Accepted Answer

最后我可以使用维基解释找到答案。http://en.wikipedia.org/wiki/Double_hashing

h(9) = 9 mod 11，即 9。

h2(9) = 1 + (9 mod (11-1)) 即 10。

所以密钥应该是 (9 + 10) mod 11，即 8。

然后

8 -> 9

2 回答 2