哈希码函数
我的字符串哈希码函数如下
hashVal=(127*hashVal+key.charAt(i))%16908799
我正在在线关注 cs61 b 讲座，当 Jonathan 教授讲述如果我们使用一个与 127 不互素的值代替 1690877 会发生什么时，我不太明白。我理解这个简单的情况他使用 127 而不是 16908799 但如果它是 127 的简单倍数呢？它如何“偏差”哈希值？偏差如何取决于公因数“x”？谁能告诉我原因吗？
My hashcode function for string is as follows
hashVal=(127*hashVal+key.charAt(i))%16908799
I am following cs61 b lectures online and I dont quite follow when Prof.Jonathan on what would happen if instead of 1690877 we would use a value that is no relatively prime with 127. I understand the simple case where he uses 127 instead of 16908799 but what if it was a simple multiple of 127 ? How would it "bias" the hashvalue ? How does the bias depend on the common factor "x" ? Can anyone suggest me the reason ?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
使用较小的数字并思考一下。假设您正在模数 10 的空间（而不是 16908799）中工作。您的
hashVal只能包含数字 0-9。例如，如果你乘以 7，你应该会看到你可以得到所有数字 0-9：
但是，如果你乘以 6（它与 10 不互质，因为它们有公因数 2），那么你不会取出所有数字 0-9，因此存在偏差：
Use smaller numbers and think it out. Say you're working in a modulus 10 space (instead of 16908799). Your
hashValcan then only contain the numbers 0-9.If you multiply by 7, for instance, you should see that you can get out all numbers 0-9:
However if you multiply by 6 (which is not relatively prime with 10 because they have the common factor 2), then you will not get all numbers 0-9 out, thus there is bias: