作者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