哈希表大小和重要的密钥位

Question

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

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

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

Answer 1

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

因此，如果您有一个质数作为模组，则会导致结果。您不会在部门中分享任何因素。

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

250/30 = 50/6 = 25/3

您希望尽量减少无用的因素。