作者QoiiwWe (台GO)
看板Grad-ProbAsk
標題[理工] [資結] hashing
時間Sun Jan 30 00:32:17 2011
T or F
1.The number of bucksts in a hash table must be a prime number.
2.It's possible to avoid collision and overflow without any overhead.
兩個都是T
為什麼呢?
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 59.126.44.104
推 boy5548:2.perfect hashing就可以避免了吧 01/30 10:13
推 boy5548:1.這是Knuth的一篇論文證出來的 證明似乎很複雜@@ 01/30 10:32
推 FRAXIS:應該沒有說一定要質數.. 如果你可以容忍很爛的Hash Table.. 01/30 10:53
→ FRAXIS:另外，如果輸入是已知的，當然可以用perfect hash 01/30 10:53
→ FRAXIS:但是如果是純動態的，要怎麼避免collision？ 01/30 10:54