我的字符串哈希码函数如下
hashVal=(127*hashVal+key.charAt(i))%16908799
我正在网上跟踪cs61 b讲座,当乔纳森教授关于会发生什么情况时,如果不是1690877,我们会使用一个与127不相对素数的值.我理解他使用127而不是16908799的简单情况.如果它是127的简单倍数怎么办？它如何" 偏向 "哈希值？偏差如何取决于公因子"x"？谁有人建议我的原因？
使用较小的数字并考虑出来.假设你在模数10空间(而不是16908799)工作.hashVal那么你的数字只能包含数字0-9.
例如,如果你乘以7,你应该看到你可以得到0-9的所有数字:
(7*0)%10 = 0
(7*1)%10 = 7
(7*2)%10 = 4
(7*3)%10 = 1
(7*4)%10 = 8
(7*5)%10 = 5
(7*6)%10 = 2
(7*7)%10 = 9
(7*8)%10 = 6
(7*9)%10 = 3
但是,如果你乘以6(因为它们具有公因子2而不是相对于10的素数),那么你将不会得到所有数字0-9,因此存在偏差:
(6*0)%10 = 0
(6*1)%10 = 6
(6*2)%10 = 2
(6*3)%10 = 8
(6*4)%10 = 4
(6*5)%10 = 0
(6*6)%10 = 6
(6*7)%10 = 2
(6*8)%10 = 8
(6*9)%10 = 4
| 归档时间： |
|
| 查看次数： |
668 次 |
| 最近记录： |