# why is Array access by index an order of magnitude faster than Map access by key?

• 05-01-2013, 04:06 PM
bendcotrton
why is Array access by index an order of magnitude faster than Map access by key?
theoretically, both are O(1) time complexity operations. But, the following code demonstrates that array access by index is 10x faster that map access by key. Is it simply (and exclusively) due to the overhead of computing the hashCode()?
Code:

```import java.util.HashMap; import java.util.Random; public class PerfTest {         static HashMap<String, Double> map;         //static double[] array;         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 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));                                 //array = new double[]{1,2,3,4,5,6,7,8,9,10};                        }         public static void main(String[] args){                                 String asdf = "asdf" + null;                                 StringBuffer sb = new StringBuffer();                 sb.append("asdf" + null);                 //System.out.println("asdf " + null);                                 PerfTest tester = new PerfTest();                 long timeInMap        = tester.testHashMap();                 long timeInArray        = tester.testArray();                                 Random rnd = new Random();                 long startTime = System.nanoTime();                 double sum = 0;                 for (int i=0; i <nTimes; i++){                         for (int j =1; j<=map.size(); j++){                                 sum += rnd.nextDouble();                         }                 }                                                        long elapsedTime = System.nanoTime() - startTime;                                 //System.out.println("Base nextDouble time: " + elapsedTime/1000000000.0);                 //System.out.println("Time elapsed in map(in seconds): "                + timeInMap/1000000000.0);                 //System.out.println("Time elapsed in array(in seconds): "        + timeInArray/1000000000.0);                                 System.out.println("Corrected time elapsed in map(in seconds): "                + (timeInMap-elapsedTime)/1000000000.0);                 System.out.println("Corrected time elapsed in array(in seconds): "        + (timeInArray-elapsedTime)/1000000000.0);         }                 private long testHashMap(){                 long startTime = System.nanoTime();                                 String str = "1";                 Random rnd = new Random();                                 for (int i=0; i <nTimes; i++){                         double sum = 0;                                                for (int j =1; j<=map.size(); j++){                                 //sum += map.get(String.valueOf(j));                                 //sum += map.get(String.valueOf(j)) + rnd.nextDouble();                                 sum += map.get(str) + rnd.nextDouble();                                                                                        }                 }                 long elapsedTime = System.nanoTime() - startTime;                                 return elapsedTime;         }                 private long testArray(){                 long startTime = System.nanoTime();                                                 Random rnd = new Random();                                 for (int i=0; i <nTimes; i++){                         double sum = 0;                         for (int j=0; j< array.length; j++) {                                                sum += array[j] +rnd.nextDouble();                         }                 }                 long elapsedTime = System.nanoTime() - startTime;                                 return elapsedTime;         } }```
• 05-01-2013, 04:23 PM
Tolls
Re: why is Array access by index an order of magnitude faster than Map access by key?
There's any number of things going on there.
O(1) does not mean "everything that's O(1) takes the same time"...it means that "accessing item A in this thing takes the same time as accessing item Z".

As for the difference in time:
For starters, a map needs to get the hash value for the key, get the bucket for that hash, then check fro equality...compared to just accessing an index.
Then you have the calculation using a random number.
For the array that's easy as it is an array of double primitives.
For the map the compiler has had to write code to unbox the Double object into a coulbe and then do the calculation.
So the above code compare access times anyway.
• 05-01-2013, 08:22 PM
JosAH
Re: why is Array access by index an order of magnitude faster than Map access by key?
Quote:

Originally Posted by Tolls
For the map the compiler has had to write code to unbox the Double object into a coulbe and then do the calculation.

A 'coulbe'? Erm, yes coulbes are notably slow because they're made of sticky bits and those bits don't want flip their values. They wanted to be eeprom bits but never made it that far; nasty bits ...

kindest regards,

Jos ;-)
• 05-02-2013, 09:44 AM
Tolls
Re: why is Array access by index an order of magnitude faster than Map access by key?
What can I say?
It's a technical term.
Not my fault you're such a hack you don't understand it...

Or, put another way, *thrrrrrrrrrp*