http://i.imgur.com/co4OIps.jpg
關於這一題
網路上的答案是寫O(n/(m)^2)
但是我算出來的是O(n/m)
我對題意的理解是
假如collision的話就會開新的table H'去存
所以平均上會有n/m個table
所以在每個table找到的機率是1/(n/m)
再假設在第k個table找到element的時間是k
算式如下
http://i.imgur.com/qOQWubO.jpg

https://i.imgur.com/4zH41be.jpg個人淺見...我的想法算出來是o(long)，不知道這樣有錯的話錯在哪個人淺見...我的想法算出來是o(long)，不知道這樣有錯的話錯在哪

我認為 誠如樓主所說 總共會有n/m個table 而每個H中的slot 平均會有(n/m)/m個table 所以在找的時候只要考慮該slot跟以後的table 即(n/m)/m個table即可

#1SNlwdIZ (Grad-ProbAsk)這才是對的吧，裡面有小證明

但樓主問的是第一題的第二小題QQ

為什麼每個H的slot中還會有table 如果碰撞時不是應該會去找下一個H'嗎？至於一樓的問題大概是出在結構上因為我理解的結構是平行生長而不是樹狀生長的例如假如有一個element塞在第5個slot假如H的slot5 collision就會直接去塞在H'的slot5假如H'還是collision會塞到H''的slot5而且因為element是通過hash function決定要塞在那個slot所以在每一個hash table search的時間會是O(1) (我的算法是直接假設為1)