哈希表:为什么大小应该是素数？

Question

可能重复:
为什么散列函数应使用素数模数？

为什么哈希表(数据结构)大小必须是素数？

据我所知,它确保了更均匀的分布,但还有其他原因吗？

Answer 1

唯一的原因是避免将值聚集到少量桶中(是的,分发).更均匀的分布式哈希表将更加一致地执行.

来自http://srinvis.blogspot.com/2006/07/hash-table-lengths-and-prime-numbers.html

如果假设你的hashCode函数导致以下hashCodes {x,2x,3x,4x,5x,6x ...},那么所有这些将集中在m个桶中,其中m = table_length/GreatestCommonFactor (table_length,x).(验证/得出这个是微不足道的).现在,您可以执行以下操作之一以避免群集

1. 确保你没有像{x,2x,3x,4x,5x,6x ......}那样生成太多另一个hashCode的hashCodes.但是如果你的hashTable应该有这个可能有点困难数百万条目.

2. 或者通过使GreatestCommonFactor(table_length,x)等于1来简单地使m等于table_length,即通过使table_length与x进行互操作.如果x可以是任何数字,那么请确保table_length是素数.