java - Java 哈希码和桶大小 - 关系

Question

Java hashcode 是一个整数（大小 2 pow 32）

当我们创建哈希表/哈希图时，它会创建大小等于地图初始容量的桶。换句话说，它创建了一个大小为“初始容量”的数组

问题1、如何将key（java对象）的hashcode映射到bucket index？2.既然hashmap的大小可以增长，那么hashmap的大小可以等于2 pow 32吗？如果答案是肯定的，那么拥有一个大小为 2 pow 32 的数组是否明智？

Answer 1

Java 数组的大小实际上仅限于 Integer.MAX_VALUE 元素，2^31-1。

HashMap 使用两个数组大小的幂，所以它可以使用的最大可能是 2^31。您将需要一个大的物理内存才能使其合理。

HashMap 在进行简单的按位与获取桶索引之前，会进行一系列移位和异或操作以减少一些冲突源。

Answer 2

这是当前源代码的链接：http: //www.docjar.com/html/api/java/util/HashMap.java.html

您的问题的答案（部分）是特定于实施的。

1）查看代码。请注意，您对如何initialCapacity实现的假设是不正确的……至少对于 Oracle Java 6 和 7。具体来说，initialCapacity不一定是hashmap的数组大小。

2）a的大小HashMap是条目的数量，可以超过2^32！我假设您实际上是在谈论容量。HashMap 的数组的大小理论上限制为2^31 - 1（Java 数组的最大大小）。对于当前的实现，MAX_CAPACITY实际上是2^30; 看代码。

3）“......明智的做法是有一个大小数组2^32？” 使用当前定义的 Java 是不可能的，尝试做一些不可能的事情是不明智的。

如果您真的在询问 Java 中哈希表数据结构的设计，那么在正常大小的哈希表的效率和巨大的哈希表之间需要权衡；即具有显着多于2^30元素的地图。这些HashMap实现被调整为最适合正常大小的地图。如果您经常需要处理 HUGE 地图，并且性能至关重要，那么您应该寻求实现一个自定义地图类，该类已针对您的特定要求进行了调整。