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)