凑码功能

Question

我的字符串哈希码功能如下

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

我在网上下CS61 b讲课，我不知道情况时Prof.Jonathan上如果不是1690877，我们会用一个值会发生什么与127不相等。我理解他使用127而不是16908799的简单情况，但如果它是127的简单倍数呢？它将如何“偏差”散列值？偏见如何取决于共同因素“x”？任何人都可以向我推荐理由吗？

Answer 1

使用较小的数字并认为它。假设你在模数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（这与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