湊碼功能

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