Java：一种“素数”数字或“两个幂”作为HashMap大小？ [英] Java: A "prime" number or a "power of two" as HashMap size?

问题描述

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

有效地掩盖了哈希码的最高位。因此，在这种情况下，低质量的哈希函数可能表现得尤其糟糕。

Java的 HashMap 通过不信任对象的 hashCode（）实现和对其结果应用第二级哈希处理：

应用一个给定的哈希函数的补充哈希函数，该函数防止质量差的哈希函数。这是至关重要的，因为HashMap使用幂的二长度散列表，否则碰到散列码的冲突，这些散列码在较低位中没有差异。

如果你有一个好的散列函数，或者做类似于 HashMap 是的，不管你是否使用素数等作为表的大小。

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

Many books and tutorials say that the size of a hash table must be a prime to evenly distribute the keys in all the buckets. But Java's HashMap always uses a size that is a power of two. Shouldn't it be using a prime? What's better, a "prime" or a "power of two" as the hash table size?

解决方案

Using a power of two effectively masks out top bits of the hash code. Thus a poor-quality hash function might perform particularly badly in this scenario.

Java's HashMap mitigates this by mistrusting the object's hashCode() implementation and 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.

If you have a good hash function, or do something similar to what HashMap does, it does not matter whether you use prime numbers etc as the table size.

If, on the other hand, the hash function is of unknown or poor quality, then using a prime number would be a safer bet. It will, however, make dynamically-sized tables tricker to implement, since all of a sudden you need to be able to produce prime numbers instead of just multiplying the size by a constant factor.

这篇关于Java：一种“素数”数字或“两个幂”作为HashMap大小？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！