作者assassin88 (AI)
看板Grad-ProbAsk
标题[理工] [DS]-台大93-资工所
时间Thu Dec 31 12:50:07 2009
Given a hash table of size 10(start index is 0), show how the folling data(in
the given order) would be stored in the table using double hashing:
h1(x) = x % 10 and h2(x) = 2 + (x % 7)
Data : 99 15 75 36 20 25 89 0 47 42
0 1 2 3 4 5 6 7 8 9
__________________________________________________
洪X书给的答案是： 20 25 75 89 0 15 36 47 42 99
蔡定X书给的答案是： 20 89 0 47 42 15 36 75 25 99
他们的差别是第二次collision(h1(x) & h2(x) 皆用过)时，
蔡采linear probing，洪是用double hashing方式，
虽然题目有规规定使用double hashing，不过没有给出来，
所以要自己使用 ( h1(x) + ih2(x) ) mod M 计算吗？
请解答..感谢
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 220.136.241.137
※ 编辑: assassin88 来自: 220.136.241.137 (12/31 12:52)
1F：推 killerjoe:double hashing的公式就是h(x,i)=(h1(x) + ih2(x))mod m 01/01 01:08
2F：→ killerjoe:所以我想应该是要使用这个公式 01/01 01:08
3F：推 flashsword:h(x)=[h1(x)+i*h2(x)] mod m 要mod bucket数 01/01 01:25