http://imgur.com/a/rsJdm
想問(31)~(33)
不太懂這題的Under the uniform hashing assumption是什麼意思
是指用Linear Probing的方式解決conflict嗎？
(31)我的想法是：
因為第3個key需要探測3次，表示前兩個key必須連續排，然後第3個key在命中連續key的
最上方的key
所以
1 key:隨意擺在m個格子的其中一格
2 key:兩種可能(1)命中跟1key一樣的格子1/m(2)命中1key的上一個or下一個2/m-1
3 key:命中前述的頭一個key格子1/m
這樣的話是(1/m+2/m-1)*1/m 但沒有這個答案
所以我在想是hashing assumption有特別的什麼假設嗎？
交大給的答案 C B B
32題背後的推導應該是蠻複雜的，洪逸資料結構上面也只給了公式沒有證明，我節錄一下他的敘述搜尋一個不在表中之識別字的平均比較次數，對於Rehashing、Random probing、Quadratic Probing為1/(1-a)，a為Loading density，在這題裡面就是n/m也許背後的想法就如T大所說的也有可能，只是書上沒給證明，有背到這題就會，沒背到也許就要用T大的想法了
作者:
Transfat (Transfat)
2016-12-23 18:18:00不一定是linear probing , 也可能是quadratic probing32題，在Uniform hashing假設下，Expected hashing ofprobs 的cost等於是找到空位的cost, 因為有n/m被佔滿了所以空位比例是1/(1-n/m) // 我是這樣想啦33題，因為chaing遇到collision 還是會放到同一格，只是會用link list連接，所以k1亂放還是可以放到任一bucket裡，這是k2也來了剛好跟k1放在一起的機率就是1/m
題目沒有說要用linear probing，所以也許是想複雜了前面兩個擺好之後，第三個key要進來，只要第一次probin中了其中一個(機率為2/m)，就要下一次probing再中了剩下m-1個中的1個就要再一次，機率為1/(m-1)兩個乘起來應該就是答案