logo标签列表

哈希码函数

hashcode
3

我字符串的哈希码函数如下所示

hashVal=(127*hashVal+key.charAt(i))%16908799

我正在在线跟进cs61 b课程，但是当Jonathan教授讲述如果我们使用一个不与127互质的值，而不是1690877时，我不太理解。我理解他用127代替16908799的简单情况，但如果它是127的一个简单倍数呢？这会如何“偏向”哈希值？这种偏差如何取决于公因数“x”？有人能给我提供原因吗？

1个回答
6

使用更小的数字并仔细思考。比如你可以在模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（6不是与10互质，因为它们有公共因子2），那么你将不能得到所有的数字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
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接