作者p52189 (千人斬小花)
看板Programming
標題[問題] 模數雜湊
時間Fri Dec 28 15:45:39 2012
問題很簡單
可是我一直找不到答案(可能真的是太簡單囧)
大家不要笑我喔...
我在書上讀到 Modulo-Division Method
就是 address = key % listSize
大家都說這個 listSize 要取質數
可是我不懂啊
譬如取73的話
mod 出來可能結果是 1~72
若是取74的話
mod 出來可能結果應該就是 1~73 ?
但74並不是質數
於是我想不通取不取質數到底有什麼關係?
看起來是單純數字越大越好?
這中間出了什麼問題?
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.44.3.61
1F：→ wsx02:取質數應該是要減少發生碰撞的機率吧? 114.42.99.9 12/28 19:19
2F：推 coconutman:應該是address = f(key) % listSize？ 114.36.49.48 12/28 21:00
3F：→ coconutman:然後如果 f(key) = key 的確沒差。 114.36.49.48 12/28 21:01
4F：→ coconutman:f(key) = a*key + b 的話，就有差。 114.36.49.48 12/28 21:01
5F：→ coconutman:基本上帶一下數字觀察a和listSize的關 114.36.49.48 12/28 21:03
6F：→ coconutman:係吧！ 114.36.49.48 12/28 21:03
7F：→ coconutman:你mod 出來應該是從 0起算吧xD 114.36.49.48 12/28 21:04
8F：→ coconutman:hash function也有其他種方式實作。 114.36.49.48 12/28 21:05
對耶@@
我書上確實是寫key而已
如果是f(key)的話不使用質數碰撞率就會大幅增加了
0的部分是我不小心，哈哈
感謝你們喔!
※ 編輯: p52189 來自: 114.44.3.61 (12/28 22:22)
9F：→ stimim:key 如果有 pattern 的話可能也會有差 36.226.35.39 12/29 12:02