31

许多书籍和教程都说哈希表的大小必须是一个素数，才能在所有桶中均匀分布密钥。但是 JavaHashMap总是使用 2 的幂的大小。不应该使用素数吗？哪个更好，“素数”或“2 的幂”作为哈希表大小？

4

5 回答 5

29

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

Java通过不信任对象的实现并对其结果应用第二级散列来HashMap缓解这种情况：hashCode()

对给定的 hashCode 应用补充散列函数，以防止质量差的散列函数。这很关键，因为 HashMap 使用长度为二的幂的哈希表，否则会遇到低位没有差异的 hashCode 的冲突。

如果你有一个好的散列函数，或者做一些类似的事情HashMap，你是否使用素数等作为表大小都没有关系。

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

于 2013-03-15T16:23:41.650 回答
6

标准的 HashMap 实现有一个hash方法可以重新散列对象的哈希码以避免这种陷阱。方法前的hash()注释如下：

/**
 * 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.
 */
于 2013-03-15T16:24:43.690 回答
5

了解素数和二次幂之间哪个更好的唯一方法是对其进行基准测试。

许多年前，在编写一个性能强烈依赖于符号表查找的汇编程序时，我使用大量生成的标识符对其进行了测试。即使使用简单的映射，我发现与预期的一样，与类似大小的素数桶相比，二次幂的分布更不均匀，链更长。由于位掩码的桶选择速度，它仍然运行得更快。

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

出于这个原因，我确信 rehash 和二次幂大小为典型的 Java 哈希映射提供了比质数桶更好的性能。

于 2013-03-15T16:36:30.757 回答
1

从性能/计算时间的角度来看，可以仅使用位掩码来计算二次方大小，这比否则需要的整数除法更快。

于 2013-03-15T16:27:47.247 回答
0

如果您使用二次探测来解决冲突，您可能应该使用素数大小的哈希表。如果您有一个素数大小的表，二次探测将命中一半的条目，如果不是素数则更少。因此，即使您的哈希表未满一半，您也可能找不到合适的位置来存储您的条目。由于 Java 哈希映射不使用二次探测，因此不需要使用素数作为大小。

于 2014-04-08T14:41:22.847 回答