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

bguiz picture bguiz · Apr 29, 2011 · Viewed 74.3k times · Source

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

Amol Katdare picture Amol Katdare · Apr 29, 2011

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