Java: "prime"数字或 "power of two"作为 HashMap 大小？

Question

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

Answer 1

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

Java 的 HashMap 通过不信任对象的 hashCode() 实现和 applying a second level of hashing to its result 来缓解这种情况。 :

Applies a supplemental hash function to a given hashCode, 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.

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

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