[理工] hashing 交大台大

[kaidi620 (萬能史哥)]

想請問大神們 這幾題關於hashing的問題


交大考題
https://imgur.com/wqL7RFY.jpg
關於第一題第二題有爬文看到大神的推演，那我想問的是(33)
關於這種hashing小弟真的是一個頭兩個大，請大神幫幫忙感謝！

https://imgur.com/iUNUcbX.jpg
還有關於第11題，可以請大神幫忙一下嗎 感恩！

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 27.246.37.206
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1549427822.A.E9D.html
→ DLHZ: 33是說分配到每個都是相同的機率 所以1/m?
→ leekevinming: 第11題是B嗎？
→ jasonx12x: k1:m個bucket選一個insert k2直接進k1選的bucket=>1/m
→ jasonx12x: 有錯請指正
→ ghost1025: 33用chain來處理 他們都會進到同一個slot所以選一個就
→ ghost1025: 好，1/m
→ ghost1025: 11.因為平均每個list會被分配到13/5個item，再加上選
→ ghost1025: bucket的次數1應該是3.6
推 b10007034: 好奇為啥給的keys跟method沒辦法使得uniform distribu
→ b10007034: tion還可以這樣算
→ GeniusPuddin: g大的那個"選bucket的次數1"算是key comparison嗎