作者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