作者freak2 (无梗人)
看板Grad-ProbAsk
标题[理工] [资结] 请问当 hash table 的 handler 为 quotient-offset 时的碰撞
时间Sun Jan 31 22:23:25 2010
感觉这应该是基本的问题, 可是我 google 很久了,
虽然有找到书上的练习题目, 但却没找到答案..Orz
补习班提供的答案看起来都是 linear 的 handler.
所以我就算觉得自己想法应该没错, 却也不能验证, 只好在此向大家请教..
题目就是一个 open hashing, 使用 quotient-offset collision handler.
照以下顺序 insert 到 size 为 11 的 table:20,33,49,22,26,202,140
请问最後位置各是多少?
我的算法如下:
X Xmod11 X/11
20 9 1
33 0 3
49 5 4
22 0 2
26 4 2
202 4 18
140 8 12
quotient-offset handler 排列的时候
0 1 2 3 4 5 6 7 8 9 10
step1 20
step2 33 20
step3 33 49 20
step4 33 22 49 20
step5 33 22 26 49 20
step6 33 22 202 26 49 20
step7 33 22 202 26 49 140 20
==================================================
final 33 22 202 26 49 140 20
冲突包括 33,22 与 26,202.
0 的位置被 33 占走, 所以 22 放到 0+2 的位置即可.
其中最特别的就是 202 的位置.
我的算法是因为 202 / 11 = 18...4 所以应该放 4 的位置
但位置 4 已经有人放了所以我就去算 4+18=22, 但这是超过 size 的.
所以再算 22/11=2...0 结果 0 和 2 都有人放了.
所以再算 2/11=0...2 结果还是回到2, 这时候需要 0+2,
可是商数为0的时候要加1, 所以我就放在 3 的位置.
这样算对吗?
另外以下是我理解的 linear handler, 也是补习班的解答.
0 1 2 3 4 5 6 7 8 9 10
step1 20
step2 33 20
step3 33 49 20
step4 33 22 49 20
step5 33 22 26 49 20
step6 33 22 26 49 202 20
step7 33 22 26 49 202 140 20
============================================================
final 33 22 26 49 202 140 20
是我对 linear 与 quotient-offset 的误解吗? 还是我的答案是正确的呢?
希望有会这题目的人给点提示, 感谢!!
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 220.134.1.148
※ 编辑: freak2 来自: 220.134.1.148 (01/31 22:55)
1F：推 supergud:题目说的quotient-offset应该是指hash function要用mod11 02/01 09:59
2F：→ supergud:发生冲突应该还是用linear handler来算 02/01 10:00
3F：→ freak2:原来如此!! 谢谢! 02/01 23:02
4F：→ freak2:可是..我上网查到的资料都是Xmod11+x/11来处理冲突的耶?? 02/01 23:23
5F：→ freak2:原来 google 的关键字要用 double hashing 02/02 01:25