[理工] 105交大 資結 Hash

[Kingsword (Shanboy)]

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

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.112.25.105
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1482487544.A.14E.html
※ 編輯: Kingsword (140.112.25.105), 12/23/2016 18:06:04
→ yupog2003: 題目沒有說要用linear probing，所以也許是想複雜了
→ yupog2003: 前面兩個擺好之後，第三個key要進來，只要第一次probin
→ yupog2003: 中了其中一個(機率為2/m)，就要下一次probing
→ yupog2003: 再中了剩下m-1個中的1個就要再一次，機率為1/(m-1)
→ yupog2003: 兩個乘起來應該就是答案
推 Transfat: 不一定是linear probing , 也可能是quadratic probing
推 Transfat: 32題，在Uniform hashing假設下，Expected hashing of
→ Transfat: probs 的cost等於是找到空位的cost, 因為有n/m被佔滿了
→ Transfat: 所以空位比例是1/(1-n/m) // 我是這樣想啦
→ Transfat: 33題，因為chaing遇到collision 還是會放到同一格，只是
→ Transfat: 會用link list連接，所以k1亂放還是可以放到任一bucket
→ Transfat: 裡，這是k2也來了剛好跟k1放在一起的機率就是1/m
→ yupog2003: 32題背後的推導應該是蠻複雜的，洪逸資料結構上面也只
→ yupog2003: 給了公式沒有證明，我節錄一下他的敘述
→ yupog2003: 搜尋一個不在表中之識別字的平均比較次數，對於
→ yupog2003: Rehashing、Random probing、Quadratic Probing為
→ yupog2003: 1/(1-a)，a為Loading density，在這題裡面就是n/m
→ yupog2003: 也許背後的想法就如T大所說的也有可能，只是書上沒給
→ yupog2003: 證明，有背到這題就會，沒背到也許就要用T大的想法了
原來是這樣！感謝T大跟Y大指教><!!
※ 編輯: Kingsword (140.112.25.105), 12/23/2016 19:50:55