[理工] 資結 hash table

[hopward (hopward)]

http://i.imgur.com/SWdyrpb.jpg

每次hash table的問題都不太懂
想請問一下100台大資結這題hash table的b小題，題目說此為uniform hash function，所以每個bucket裡面的element數應該是一樣的，又因為loading factor=n/(B*S)=a，做個移向會得到
n/B=aS(S為bucket size)為每個Bucket內的element個數為aS，所以用紅黑樹處理失敗搜尋及插入的複雜度是O(log(aS))嗎??

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 39.10.40.195
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1483764928.A.445.html
→ ken52011219: 我會寫 O(m*log(n/m)) @@~
→ ken52011219: 阿阿 O(log a) 而已 每次都死在同個觀念
→ aa06697: 我的想法同原po
→ ken52011219: chaining search 和 insert 都為O(1) , 剩下的就是
→ ken52011219: 如何在 RB樹中 insert or search
→ ken52011219: 想了一下，感覺原PO的答案比較完整
→ yupog2003: 我第一個反應會想寫O(log a)，因為課本在解釋chaining
→ yupog2003: 時都把bucket size當作1在考慮，不過原PO應該比較完整
→ hopward: 感謝樓上各位 不然實在是很不確定 哈哈