[理工] 101 交大 DS

[fbukevin (Veck)]

想請問 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
→ ab170926:就只是叫你找看看 不用插入
推 gnuhcoay:是要搜尋24和25但是找不到的搜尋次數，不是把他們加進去
→ fbukevin:但這樣不就要把hash table整個都找一遍嗎?
→ fbukevin:因為根本不在表中，所以算出位置後會一直往後找吧?
→ ab170926:如果找到一格空的 就不用往下找了
→ fbukevin:對吼!!!! 謝謝兩位大大!!!!
推 sadkiller:找24是8次喔!