data-structures - 使用素数作为 HashTable 的大小

Question

我一直在阅读有关 HashTables 的教科书，它说在重新散列时使用质数作为数组的大小，但它没有解释原因。我也用谷歌搜索了它，我发现的最佳答案是“出于技术原因”，这些为什么应该使用质数来表示 HashTable 的大小的原因是什么？

Answer 1

这取决于哈希函数。具体来说，为哈希表大小选择一个素数可以弥补所使用的哈希函数较差的事实，并且通常会为在执行期间自然一起出现的值返回全等哈希值。哈希表大小的质数提高了哈希函数可能具有的任何“周期”与哈希表大小相对质数的机会。

如果使用出色的散列函数，例如加密散列函数，您可以使用任何散列表大小而无需担心。2 的幂很便宜，因为除法变成了位掩码。

Answer 2

我读过在java中hashmap的大小是2的幂，那是因为它有助于元素在数组上的平均分布。我认为使用素数也是为了避免碰撞和平均分配元素。桶索引被决定为 hashcode%arraysize，现在，如果 size 是任何合数，那么碰撞的机会就更多。