[理工] [資結]-請問當 hash table 的 handler …
感覺這應該是基本的問題, 可是我 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)
推
02/01 09:59, , 1F
02/01 09:59, 1F
→
02/01 10:00, , 2F
02/01 10:00, 2F
→
02/01 23:02, , 3F
02/01 23:02, 3F
→
02/01 23:23, , 4F
02/01 23:23, 4F
→
02/02 01:25, , 5F
02/02 01:25, 5F