为什么这个具有初始容量的 hashmap 试图调整大小？

Question

为什么这段代码抛出异常？

public static void main(String[] args) {
    Map<Integer, Integer> map = new HashMap<>(Integer.MAX_VALUE);
    System.out.println("map size: "+map.size());
    map.put(1, 1);
    System.out.println("map size: "+map.size());
}

输出：

map size: 0
Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
    at java.util.HashMap.resize(HashMap.java:703)
    at java.util.HashMap.putVal(HashMap.java:628)
    at java.util.HashMap.put(HashMap.java:611)
    at com.fredcrs.codejam.NumberToBinary.main(NumberToBinary.java:24)

hashmap 是否应该只在它已满时调整到更大的大小？

编辑：它在初始化时也会抛出相同的异常：

Map<Integer, Integer> map = new HashMap<>(Integer.MAX_VALUE-3);

Answer 1

new HashMap<>(Integer.MAX_VALUE);

您要求初始数组大小为 2³¹-1 个元素，即 2,147,483,647。每个元素 8 个字节（引用为 64 位），即大约 16 GB 的内存。

除非您有 18GB 左右的可用空间，否则您将始终遇到 OOM 错误。

您要求 16GB 的阵列内存，除非该内存可用，否则它将失败。它是在实例化时失败还是在第一次插入时失败是实现细节。在过去的某个时刻，它会在实例化时失败。最近，代码更改为等待第一次插入。这种变化是可能的，因为分配数组的时间的细节不是任何外部契约的一部分——即它没有在 JavaDoc 中提到。

Answer 2

在 Oracle Java 8 JDK 中，在添加元素之前不会分配 HashMap 的存储。

如有疑问，只需检查实现 - 您甚至可以在调试器中单步执行它。

现代 JDK HashMap 实现在插入第一个元素之前不会实际分配基础数组，即使您指定了显式大小也是如此。比如我的版本JDK8，构造函数代码如下：

public HashMap(int initialCapacity, float loadFactor) {
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal initial capacity: " +
                                           initialCapacity);
    if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal load factor: " +
                                           loadFactor);
    this.loadFactor = loadFactor;
    this.threshold = tableSizeFor(initialCapacity);
}

注意没有分配数组。此外，您请求的大小大于我系统上的 MAXIMUM_CAPACITY，即 2³⁰，因此实际请求的大小（存储在 this.threshold 中为 ) 上限为 MAXIMUM_CAPACITY。

然后，当您实际去分配数组时，实现会尝试创建一个请求大小的数组。最终，在 HashMap.resize() 的深处，有一些逻辑可以检测到您已经达到 "maximum capacity" （因为您要求从最大容量的初始大小开始），并将基础数组的大小设置为 Integer.MAX_VALUE:

    if (newThr == 0) {
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }

这随后分配了一个包含 2³¹-1 int 个元素的数组，这需要至少 8G 的堆 space。这就是您获得 OOME 的原因。当我运行和 -Xmx9G 它成功完成输出：

map size: 0
map size: 1

为什么这个具有初始容量的 hashmap 试图调整大小？

Why is this hashmap with initial capacity trying to resize?

java

dictionary

initialization

hashtable

hashmap