0

考虑使用带有散列函数的开放寻址将键 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 放入哈希表中。在这种情况下我该怎么办。

4

2 回答 2

3

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

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)
于 2012-05-11T04:41:01.333 回答
0

最后我可以使用维基解释找到答案。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

于 2012-05-11T06:13:25.777 回答