java - 是具有预定义容量的 HashMap 更快

Question

我在网上遇到了一个算法 http://www.coderanch.com/t/201836/Performance/java/Hashtable-vs-Hashmap 并决定对其进行测试

public class MapTest{
    static int sizeOfTrial = 100000;
    static String[] keys = new String[sizeOfTrial];
    static String[] vals = new String[sizeOfTrial];

    public static void main(String[] args) {
        //init sizeOfTrial key/value pairs
        for (int i=0; i < sizeOfTrial; i++){
          String s1 = "key"+ i;
          String s2 = "val"+ i;
          keys[i] = s1;
          vals[i] = s2;
        }
        test(new TreeMap(), "TreeMap");
        test(new Hashtable(), "Hashtable");
        test(new HashMap(), "HashMap");
        test(new Hashtable(200000), "Hashtable presized");
        test(new HashMap(200000), "HashMap presized");
    }

  public static void test(Map tm, String name){
    long t1 = System.currentTimeMillis();
    for (int i=0; i < sizeOfTrial; i++){
      tm.put(keys[i],vals[i]);
    }
    for (int i=0; i < sizeOfTrial; i++){
      tm.get(keys[i]);
    }
    long t2 = System.currentTimeMillis();
    System.out.println("total time for " + name + ": " + (t2-t1));
  }
}

我得到了以下结果

total time for TreeMap: 1744
total time for Hashtable: 446
total time for HashMap: 234
total time for Hashtable presized: 209
total time for HashMap presized: 196

这个 JVM 是依赖的和任意的，还是它真的提供了更快的访问和存储时间？

Answer 1

预定义任何容器类型类的预期大小将提供更快的存储时间，因为存储不必经常在运行时动态重新分配。通常后备存储是某种阵列，当您超出可用容量时，必须将该阵列复制到一个新的更大的阵列中。这是一项代价高昂的操作，如果您将大量对象存储到一个以非常小的容量启动的容器中，则可能不得不多次执行此操作。

从 map 读取的性能应该不会受到任何影响。您可以通过将 tm.put 部分与 tm.get 部分分开计时来更好地证明这一点。

---

编辑:为了进一步说明这一点，我将代码修改为时间tm.put 与tm.get 分开。这是我机器上的结果:

total time for TreeMap tm.put: 159
total time for TreeMap tm.get: 74
total time for Hashtable tm.put: 20
total time for Hashtable tm.get: 10
total time for HashMap tm.put: 42
total time for HashMap tm.get: 5
total time for Hashtable presized tm.put: 11
total time for Hashtable presized tm.get: 9
total time for HashMap presized tm.put: 6
total time for HashMap presized tm.get: 4

请注意 Hashtable 常规和 tm.put 的预大小之间的差异是 ~2 的因数。类似地，对于 HashMap，常规和预置大小之间的差异是存储的 ~7 倍。然而，从读取方面来看，Hashtable 和 Hashmap 在这两种情况下对 tm.get 的时间大致相同(10 Hashtable ms vs 9 ms，HashMap 5 ms vs 4 ms )。另请注意，在预先确定的情况下，放置和获取所花费的总时间大致相同。