Java：作为HashMap大小的“主要”编号或“两个幂”？

Question

许多书籍和教程都指出，散列表的大小必须是在所有桶中均匀分配密钥的首要条件。但是Java的HashMap总是使用2的幂的大小。它不应该使用素数？有什么更好的，作为散列表大小的“主要”或“两个幂”？

Answer 1

使用2的幂有效地掩盖了哈希码的最高位。因此，在这种情况下，质量很差的散列函数可能表现得尤为糟糕。

Java的HashMap减轻这种由不信任对象的hashCode()实施和applying a second level of hashing to its result：

适用的补充哈希函数在给定的hashCode，其抵御质量差的散列函数。这是至关重要的，因为HashMap使用幂的二长度哈希表，否则碰到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

从幂的两种尺寸可以只用位屏蔽，比这将被另外要求整数除法更快来计算的视性能/计算时间点。

Answer 4

要想知道哪个更好，哪个更好，哪个更好，只需要对它进行基准测试。很多年前，当编写一个汇编程序，其性能强烈依赖于符号talbe查找时，我使用大量生成的标识符对其进行了测试。即使有一个天真的映射，我发现如预期的那样，两次幂分布的分布均匀性和链长比类似大小的素数桶更少。由于通过位掩码选择存储区的速度，它仍然跑得更快。

我强烈怀疑java.util开发人员不会使用额外的哈希和两次幂的方法，而无需使用质数的存储桶进行基准测试。在设计散列数据结构时，这是一件非常明显的事情。

由于这个原因，我确定重新哈希和二次幂的大小会为典型的Java哈希映射提供比质数的桶更好的性能。

Answer 5

如果您使用quadratic probing进行冲突解决，您可能应该使用素数大小的散列表。如果你有一个主要大小的表格，二次探测将达到一半的条目，如果它不是素数的话，则会减少。所以即使你的哈希表少于半满，你也可能找不到合适的地方存储你的条目。由于Java哈希映射不使用二次探测，所以不需要使用素数作为大小。