hash - 哈希表大小和密钥的有效位

Question

我有一个关于哈希表大小和模块化哈希的问题。我指的散列算法如下： hash_key % table_size = array_index. 我正在阅读一本算法教科书，其中给出了以下建议：

如果表大小不是素数，则可能是键的所有位在确定 array_index 时都不起作用。

谁能用一个例子来解释这到底意味着什么？

Answer 1

你要避免的是共同因素。有一个定理指出，每个数都可以表示为素数的乘积。

因此，如果您有一个素数作为 mod。您将不会分享该部门中的任何因素。

比如说 A % 30，所以 2、3 和 5 的任何倍数都将共享除法中的因子，而该因子在除法中将无用。

250/30 = 50 / 6 = 25 / 3

你想尽量减少无用的因素。