[問題] 模數雜湊

[p52189 (千人斬小花)]

問題很簡單

可是我一直找不到答案(可能真的是太簡單囧)

大家不要笑我喔...



我在書上讀到 Modulo-Division Method

就是 address = key % listSize

大家都說這個 listSize 要取質數

可是我不懂啊

譬如取73的話

mod 出來可能結果是 1~72

若是取74的話

mod 出來可能結果應該就是 1~73 ?

但74並不是質數


於是我想不通取不取質數到底有什麼關係?

看起來是單純數字越大越好?

這中間出了什麼問題?



--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.44.3.61
→ wsx02:取質數應該是要減少發生碰撞的機率吧?
推 coconutman:應該是address = f(key) % listSize？
→ coconutman:然後如果 f(key) = key 的確沒差。
→ coconutman:f(key) = a*key + b 的話，就有差。
→ coconutman:基本上帶一下數字觀察a和listSize的關
→ coconutman:係吧！
→ coconutman:你mod 出來應該是從 0起算吧xD
→ coconutman:hash function也有其他種方式實作。
對耶@@
我書上確實是寫key而已
如果是f(key)的話不使用質數碰撞率就會大幅增加了
0的部分是我不小心，哈哈
感謝你們喔!
※ 編輯: p52189          來自: 114.44.3.61          (12/28 22:22)
→ stimim:key 如果有 pattern 的話可能也會有差