哈希表：为什么大小应该是质数？

Question

可能是重复问题：
为什么哈希函数要使用质数模数？

哈希表（数据结构）的大小必须是质数，这是为什么呢？

据我所知，这可以确保更均匀的分布，但还有其他原因吗？

- Olivier Lalonde

---

这是为什么哈希函数应该使用质数模数？的一个副本 - 侧边栏中“相关”部分的第一个链接 - 我认为被采纳的答案非常好。 - Matthew Slattery

你应该接受一个答案。 - jds

我刚刚注意到这个被标记为重复了。这很不幸。这两个问题是相关但不同的问题。这个特定的问题是关于在哈希表容量中使用质数的用法。另一个问题是关于在计算适当的哈希值时使用质数的用法。它们彼此相关，但并不重复。 - Samuel Neff

Answer 1

唯一的原因是为了避免值聚集到少量桶中（是的，分布）。分布更均匀的哈希表会表现得更加一致。来自http://srinvis.blogspot.com/2006/07/hash-table-lengths-and-prime-numbers.html 如果假设您的hashCode函数在其他hashCode之间产生以下hashCode {x, 2x, 3x, 4x, 5x, 6x...}，那么所有这些都将聚集在仅m个桶中，其中m = table_length/GreatestCommonFactor(table_length, x)。（可以验证/推导出这一点）。现在你可以做以下任一操作以避免聚集：

1. 确保不要生成太多的hashCode是另一个hashCode的倍数，如{x, 2x, 3x, 4x, 5x, 6x...}。但是，如果您的哈希表应该有数百万个条目，则可能会有些困难。

2. 或者通过使GreatestCommonFactor(table_length, x)等于1，即通过使table_length与x互质，使m等于table_length。如果x可以是任何数字，那么请确保table_length是质数。

更新：（来自原答案作者）

这个答案对于哈希表的常见实现是正确的，包括Java实现的原始Hashtable以及.NET的当前Dictionary实现。

但是，关于Java的HashMap，容量应该是质数的答案和假设都是不准确的。实现HashMap的方式非常不同，它利用大小为2的幂的表来存储桶，并使用n-1& hash来计算要使用哪个桶，而不是传统的hash％n公式。

Java的HashMap会强制将实际使用的容量设置为请求容量上面最接近的下一个大于等于2的幂。

对比Hashtable：

int index = (hash & 0x7FFFFFFF) % tab.length

https://github.com/openjdk/jdk/blob/jdk8-b120/jdk/src/share/classes/java/util/Hashtable.java#L364

转换为 HashMap：

first = tab[(n - 1) & hash]

https://github.com/openjdk/jdk/blob/jdk8-b120/jdk/src/share/classes/java/util/HashMap.java#L569

- Samuel Neff

---

那我猜我的理解是正确的：避免聚类 <=> 获得更好的分布。对吗？感谢提供参考。 - Olivier Lalonde

@Olivier Lalonde，如果这个回答解决了你的问题，请标记它为答案。 - Samuel Neff

那么所有这些将只被聚集在m个桶中，其中m = table_length / GreatestCommonFactor(table_length, x)。 （这很容易验证/推导出来）。如何验证/推导呢？ - tonix

@tonix 这是一句引用，但我认为你可以通过创建一个表示桶的整数数组，循环遍历大量项目，并将每个项目添加到相应的数组元素中来模拟向哈希表中添加大量项目。如上所述，一个分布良好的哈希表在每个数组元素中都会有类似的数字。而像第一个示例中使用非质数的情况下，分布不良的哈希表将在某些索引处显示出峰值。 - Samuel Neff

@SamuelNeff 谢谢你的回复，但我正在寻找一种证明它的方法。 - tonix