哈希表大小和 key 的有效位

Question

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

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

任何人都可以用一个例子来解释这到底是什么意思吗？

Answer 1

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

因此，如果您有素数作为模数。您不会在分部中分享任何因素。

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

250/30 = 50/6 = 25/3

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