我有一个关于哈希表大小和模块化哈希的问题。我指的哈希算法如下: hash_key % 表大小 = 数组索引。 我正在阅读一本算法教科书，其中给出了以下建议:
如果表大小不是素数，则可能会出现键的所有位在确定 array_index 时不起作用的情况。
谁能用一个例子解释一下这到底意味着什么？
最佳答案
您要避免的是常见因素。有一个定理指出每个数字都可以表示为素数的乘积。
因此，如果你有一个素数作为 mod。您不会分享该部门的任何因素。
假设 A % 30，那么 2、3 和 5 的任何倍数都将共享除法中的因数，并且该因数在除法中将毫无用处。
250/30 = 50/6 = 25/3
您希望尽量减少无用因素。
关于哈希表大小和键的有效位，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/10358712/