Java : Iteration through a HashMap, which is more efficient?

Question

Given the following code, with two alternative ways to iterate through it,
is there any performance difference between these two methods?

        Map<String, Integer> map = new HashMap<String, Integer>();         //populate map          //alt. #1         for (String key : map.keySet())         {             Integer value = map.get(key);             //use key and value         }          //alt. #2         for (Map.Entry<String, Integer> entry : map.entrySet())         {             String key = entry.getKey();             Integer value = entry.getValue();             //use key and value         } 

I am inclined to think that alt. #2 is the more efficient means of iterating through the entire map (but I could be wrong)

Answer 1

Your second options is definitely more efficient since you are doing a lookup only once compared to n number of times in the first option.

But, nothing sticks better than trying it out when you can. So here goes -

(Not perfect but good enough to verify assumptions and on my machine anyway)

public static void main(String args[]) {      Map<String, Integer> map = new HashMap<String, Integer>();     // populate map      int mapSize = 500000;     int strLength = 5;     for(int i=0;i<mapSize;i++)         map.put(RandomStringUtils.random(strLength), RandomUtils.nextInt());      long start = System.currentTimeMillis();     // alt. #1     for (String key : map.keySet()) {         Integer value = map.get(key);         // use key and value     }     System.out.println("Alt #1 took "+(System.currentTimeMillis()-start)+" ms");      start = System.currentTimeMillis();     // alt. #2     for (Map.Entry<String, Integer> entry : map.entrySet()) {         String key = entry.getKey();         Integer value = entry.getValue();         // use key and value     }     System.out.println("Alt #2 took "+(System.currentTimeMillis()-start)+" ms"); } 

RESULTS (Some interesting ones)

With int mapSize = 5000; int strLength = 5;
Alt #1 took 26 ms
Alt #2 took 20 ms

With int mapSize = 50000; int strLength = 5;
Alt #1 took 32 ms
Alt #2 took 20 ms

With int mapSize = 50000; int strLength = 50;
Alt #1 took 22 ms
Alt #2 took 21 ms

With int mapSize = 50000; int strLength = 500;
Alt #1 took 28 ms
Alt #2 took 23 ms

With int mapSize = 500000; int strLength = 5;
Alt #1 took 92 ms
Alt #2 took 57 ms

...and so on

Answer 2

The second snippet will be slightly faster, since it doesn't need to re-look-up the keys.

All HashMap iterators call the nextEntry method, which returns an Entry<K,V>.

Your first snippet discards the value from the entry (in KeyIterator), then looks it up again in the dictionary.

Your second snippet uses the key and value directly (from EntryIterator)

(Both keySet() and entrySet() are cheap calls)