HashMap的大小是“质数”还是“2的幂”？

Question

许多书籍和教程都说哈希表的大小必须是质数，才能在所有存储桶中均匀地分配密钥。但是Java的HashMap总是使用2的幂的大小。它不应该使用质数吗？哈希表的大小是“质数”还是“2的幂”，哪个更好？

Answer 1

对给定的hashCode应用补充性哈希函数，以抵御劣质哈希函数。这一点很关键，因为HashMap使用2次方长度的哈希表，否则会遇到低位不同的hashCodes冲突。

如果你有一个很好的散列函数，或者做一些类似于HashMap做的事情，那么你是否使用质数等作为表大小并不重要。

另一方面，如果哈希函数是未知的或质量很差的，那么使用质数将是更安全的选择。然而，它将使动态调整大小的表更难实现，因为突然之间，您需要能够生成质数，而不仅仅是将大小乘以一个常数因子。

Answer 2

标准的HashMap实现有一个hash方法，它可以重新散列对象的散列代码以避免这种缺陷。the hash() method之前的注释是：

/**
 * Retrieve object hash code and applies a supplemental hash function to the
 * result hash, which defends against poor quality hash functions.  This is
 * critical because HashMap uses power-of-two length hash tables, that
 * otherwise encounter collisions for hashCodes that do not differ
 * in lower bits. Note: Null keys always map to hash 0, thus index 0.
 */

Answer 3

要知道质数和2次方中哪一个更好，唯一的方法是对其进行基准测试。

许多年前，当我编写一个汇编器，它的性能很大程度上依赖于符号表查找时，我使用一大块生成的标识符来测试这一点。即使有了一个天真的映射，我也发现2的幂，正如预期的那样，与类似大小的质数桶相比，分布不均匀，链也更长。它仍然运行得更快，因为通过位掩码选择存储桶的速度更快。

我强烈怀疑java.util开发人员不会求助于额外的散列和2的幂，而不是将其与使用质数的存储桶进行基准测试。在设计散列数据结构时，这是一件非常明显的事情。

出于这个原因，我确信对于典型的Java散列映射，rehash和2的幂大小比质数的存储桶具有更好的性能。