[理工] 101 交大 DS
想請問 8 hash table 這一大題的 identifier comparisons
是指 對每一個index的 key 做比較 嗎?
依據(22)題目我建出來的 Table 是
0 1 2 3 4 5 6 7 8 9 10
---------------------------------------------------
| 11 | | 13 | 14 | 2 | 3 | 36 | 18 | 28 | | 21 |
---------------------------------------------------
↑ ↑ ↑
collision h(2) h(3) h(28)
h(36)
(22)題我想說應該是指每一個key都搜尋一次的情況
所以:
11 13 14 18 21 => 因為沒碰撞，用h(x) 可以馬上找到，各比1次，共5次
2 3 28 => 因為有碰撞，線性向後找兩個可以找到，各比3次，共9次
36 => 因為有碰撞，線性向後找三個可以找到，共比4次
Total in 5 + 9 + 4 = 18
但是這樣一來第(23)題我就不知道怎麼辦了?
我想說 25 and 24 are searched，又是 as the Hash Table in Step (22)
是不是說(22)完成以後還可以再找的到 25 和 24 ?
但是 Hash Table 中沒有這兩個數
因此要再加入這兩個數的意思嗎???
if so, 先加入25，會碰撞，所以找到 bucket No. 9
接著加入 24，也會碰撞，所以在線性往後找，到了 No. 10 都沒空位所以從頭找起
最後放在 No. 1
這樣子的話，當我要找 25，就會比較 7 次 (h(25) = 3，3~9共7次)
要找 24，就會比較 11次 (h(24) = 2，2~10 + 0~1共11次)
就變成 7 + 11 = 18 次了!?
但是答案給 C 15 次，是為什麼呢???
==============================================================================
剩下兩周，大家加油!!!!!!!!!!!!!!!!!
------------------------------------------------------------------------------
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.46.83.156
→
01/17 20:11, , 1F
01/17 20:11, 1F
推
01/17 20:13, , 2F
01/17 20:13, 2F
→
01/17 20:17, , 3F
01/17 20:17, 3F
→
01/17 20:18, , 4F
01/17 20:18, 4F
→
01/17 20:21, , 5F
01/17 20:21, 5F
→
01/17 20:23, , 6F
01/17 20:23, 6F
推
01/17 23:43, , 7F
01/17 23:43, 7F