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

Question

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

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

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

Answer 1

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

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

假设 A % 30，因此 2、3 和 5 的任何倍数都将共享除法中的因子，而该因子在除法中将无用。

250/30 = 50 / 6 = 25 / 3

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