PTT數位生活區 / Programming

[問題] 模數雜湊

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