Java:为什么 Array (w index) *数量级*比 Map (key) 访问快？

Question

我们运行了附加的测试。结果一致表明，通过 Array by index 访问比通过 Map by key 访问快 10 倍。这种数量级的差异让我们感到惊讶。

我们的 Map 键是 java.lang.String ...计算 Map 键的 java.lang.String.hashcode() 实现的成本是唯一的原因吗？在附带的代码中，我只使用一个键进行了练习

java.lang.String key = 1; 

在这种情况下，编译器/运行时缓存不存在吗？还是在每次调用时重新计算？

感谢任何见解。

public class PerfTest {
static java.util.HashMap<String, Double> map;
static Double[] array = {1.0,2.0,3.0,4.0,5.0,6.0,7.0,8.0,9.0,10.0};

static long nTimes = 1000000;

static{
    map = new java.util.HashMap<String, Double>();
    map.put("1",    new Double(1));
    map.put("2",    new Double(2));
    map.put("3",    new Double(3));
    map.put("4",    new Double(4));
    map.put("5",    new Double(5));
    map.put("6",    new Double(6));
    map.put("7",    new Double(7));
    map.put("8",    new Double(8));
    map.put("9",    new Double(9));
    map.put("10",   new Double(10));        
}

public static void main(String[] args){

    PerfTest tester = new PerfTest();
    long timeInMap  = tester.testHashMap();
    long timeInArray    = tester.testArray();

    System.out.println("Corrected time elapsed in map(in seconds): "        
            + (timeInMap)/1000000000.0);
    System.out.println("Corrected time elapsed in array(in seconds): " 
            + (timeInArray)/1000000000.0);
}

private long testHashMap(){
    int sz = map.size();
    long startTime = System.nanoTime();

    String key = "1";   

    for (int i=0; i <nTimes; i++){
        double sum = 0; 

        for (int j =1; j<=sz; j++){
            sum += map.get(key);                            
        }
    }
    return (System.nanoTime() - startTime);
}

private long testArray(){
    long startTime = System.nanoTime();

    for (int i=0; i <nTimes; i++){
        double sum = 0;

        for (int j=0; j< array.length; j++) {       
            sum += array[j];
        }
    }   
    return (System.nanoTime() - startTime);
   }
 }

Answer 1

使用 Java 的系统时间并不是获得真正基准的好方法。我重构了您的代码以使用 Google Caliper (它预热了 JVM，等等)......并发现了与您相似的结果。评论者正确地指出我的原始版本不好，大部分时间都在调用 System.out.println。

就像我说的，编写基准很难。下面更新的是新的正确版本。

结果:

 0% Scenario{vm=java, trial=0, benchmark=HashMap} 51.04 ns; σ=0.22 ns @ 3 trials
50% Scenario{vm=java, trial=0, benchmark=Array} 4.05 ns; σ=0.01 ns @ 3 trials

benchmark    ns linear runtime
  HashMap 51.04 ==============================
    Array  4.05 ==

代码:

import com.google.caliper.Runner;
import com.google.caliper.SimpleBenchmark;

public class PerfTest {
    public static double hashNum = 0;
    public static double arrayNum = 0;

    public static class PerfBenchmark extends SimpleBenchmark {
        static java.util.HashMap<String, Double> map;
        static Double[] array = {1.0,2.0,3.0,4.0,5.0,6.0,7.0,8.0,9.0,10.0};

        static{
            map = new java.util.HashMap<String, Double>();
            map.put("1",    new Double(1));
            map.put("2",    new Double(2));
            map.put("3",    new Double(3));
            map.put("4",    new Double(4));
            map.put("5",    new Double(5));
            map.put("6",    new Double(6));
            map.put("7",    new Double(7));
            map.put("8",    new Double(8));
            map.put("9",    new Double(9));
            map.put("10",   new Double(10));        
        }

        public void timeHashMap(int nTimes){
            int sz = map.size();

            String key = "1";   

            for (int i=0; i <nTimes; i++){
                double sum = 0; 

                for (int j =1; j<=sz; j++){
                    sum += map.get(key);                            
                }

                hashNum += sum;
            }
        }

        public void timeArray(int nTimes){
            for (int i=0; i <nTimes; i++){
                double sum = 0;

                for (int j=0; j< array.length; j++) {       
                    sum += array[j];
                }

                arrayNum += sum;
            }
        }
    }

    public static void main(String[] args){
        Runner.main(PerfBenchmark.class, new String[0]);

        System.out.println(hashNum);
        System.out.println(arrayNum);
    }
}