为什么创建HashMap比创建Object[]更快？

Question

我尝试构建自己的地图以提高特定环境下的性能，并且发现了一些有趣的事情：创建一个 new Hashmap<Integer,String>(2000) 比 new Object[2000] 快—无论我以什么顺序执行这些命令。这对我来说非常令人困惑，特别是因为 Hashmap 构造函数包含一个 table = new Entry[capacity]，根据这里。我的测试台有什么问题吗？

public static void test(int amm){ //amm=1_000_000
    Map<Integer,String> m1 = null;
    Object[] arr = null;

    long time = System.nanoTime();
    for(int i = 0; i < amm; i++){
        m1 = new HashMap<Integer, String>(2000);
    }
    System.out.println("m1: " + (System.nanoTime() - time)); //m1: 70_455_065

    time = System.nanoTime();
    for(int i = 0; i < amm; i++){
        arr = new Object[2000];
    }
    System.out.println("arr: " + (System.nanoTime() - time)); //arr: 1_322_473_803
}

我希望能在另一台电脑上看到测试结果。我不知道为什么创建一个HashMap比创建一个Object[]快10倍。

- alex berne

---

这取决于JDK的实现。您使用哪个JDK版本来执行此测试？ - BladeCoder

@BladeCoder，根据java.version，我正在使用1.7.0_79（IceTea 2.5.5）（7u79-2.5.5-0ubuntu0.14.04.2）。 - alex berne

在一个接近于OpenJDK 1.7的版本中，HashMap的构造函数中没有初始化任何数组（这是在第一次插入时完成的），这解释了速度差距。参考链接为:http://grepcode.com/file_/repository.grepcode.com/java/root/jdk/openjdk/7u40-b43/java/util/HashMap.java/?v=source - BladeCoder

Answer 1

如果您查看 HashMap 的实现，构造函数如下：

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;
    threshold = initialCapacity;
    init();
}

init() 的样子如下：

/**
 * Initialization hook for subclasses. This method is called
 * in all constructors and pseudo-constructors (clone, readObject)
 * after HashMap has been initialized but before any entries have
 * been inserted.  (In the absence of this method, readObject would
 * require explicit knowledge of subclasses.)
 */
void init() {
}

所以，initialCapacity 实际上并未用于创建数组。它在哪里被使用呢？看一下 put() 方法即可。

public V put(K key, V value) {
    if (table == EMPTY_TABLE) {
        inflateTable(threshold);
    }
    // hidden
} 

进行PUT操作时，实际上是创建了一个数组。我没有展示inflateTable()函数，但它执行一些数学运算并初始化数组。

- Amir Raminfar

---

你的源代码从哪儿来的？我在http://www.docjar.com/html/api/java/util/HashMap.java.html找到了一些东西，但似乎有所不同。虽然如此，我还是会去尝试一下 :) 编辑：你是对的，加上put（5，“Hello”）可以解决问题。很有趣，谢谢。 - alex berne

@alexberne 我使用了IntelliJ的查看源代码功能，它是在MacOS上使用的JDK_1.7.0_51版本。 - Amir Raminfar

有趣...所以如果您有一个程序在加载时初始化一个大的HashMap并在用户单击按钮时放置元素，那么OpenJDK实现将显示不同的性能。--在OpenJDK上，应用程序将需要很长时间才能加载，并且在用户交互方面速度很快。而在OracleJDK上，应用程序将快速加载，并在第一次单击按钮时需要很长时间。-- OracleJDK解决方案的好处显然是能够创建许多未使用的HashMap而不会占用太多内存空间。 - Falco

@Falco，不是的，这段代码来自OpenJDK，而不是一些Oracle专有的补丁。Oracle Java非常接近OpenJDK，只是并没有开放所有组件（WebStart、JMC、HotSpot for ARM等）。 - alexkasko

@alexkasko，那么DocJar上的代码似乎是错误的，在他们的OpenJDK-7源代码版本中看起来不同...奇怪。 - Falco

Answer 2

一个空的HashMap对象比一个长度为2000的Object引用数组要小得多。即使你将参数initialCapacity设置为2000来构造HashMap对象，它实际上并没有立即创建2000个对象空间。

- Greg Hewgill