Performance comparison of different ways to iterate over HashMap

We have already learned about how HashMap in java works internally. If my last similar post, I tried to compare different “for loop” flavors available in java. These studies usually help in setting up best practices for your next project.

I this post, I decided to compare traversal in hash map in java. HashMap is very frequently used class and most of the times we just fetch the value using get(Object key) method provided by class. But at times it is required to iterate over whole Map and fetch all key-value pairs stored in it. For example, analyzing all request parameters sent from client. If you are using this, the for every client you will be iterating whole map at least once in your code.

If you are using this type of iteration many places in code and there are large number of requests then you surely would like to optimize your iteration code to make best use of it. My below given analysis will help you to decide your next step.

Lets start with different ways to iterating over HashMap first:

1) Using enrtySet() in for each loop

for (Map.Entry<String,Integer> entry : testMap.entrySet()) {
    entry.getKey();
    entry.getValue();
}

2) Using keySet() in for each loop

for (String key : testMap.keySet()) {
    testMap.get(key);
}

3) Using enrtySet() and iterator

Iterator<Map.Entry<String,Integer>> itr1 = testMap.entrySet().iterator();
while(itr1.hasNext())
{
    Map.Entry<String,Integer> entry = itr1.next();
    entry.getKey();
    entry.getValue();
}

4) Using keySet() and iterator

Iterator itr2 = testMap.keySet().iterator();
while(itr2.hasNext())
{
    String key = itr2.next();
    testMap.get(key);
}

Now lets compare their performances for a common data set stored in map. I am storing 10 lacs key value pairs in map and will iterate over map in all four ways. I will also fetch key and value from map for all 10 lacs entries in best suitable way. Then i will capture the time taken by each way.

package com.howtodoinjava.performance;

import java.util.Calendar;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;

public class DifferentWaysToIterateOverHashMap {

	static HashMap<String,Integer> testMap = new HashMap<String,Integer>();

	static
	{
		for(int i=0; i< 10_00_000; i++)
		{
			testMap.put("key_" + i, i);
		}
	}

	public static void main(String[] args) {

		long startTime = Calendar.getInstance().getTimeInMillis();
		//First way using entrySet in for-each loop
		for (Map.Entry<String,Integer> entry : testMap.entrySet()) {
		    entry.getKey();
		    entry.getValue();
		}

		System.out.println("Using entrySet() in for-each loop : " + (Calendar.getInstance().getTimeInMillis() - startTime));

		startTime = Calendar.getInstance().getTimeInMillis();
		//Second way using keySet() in for-each loop
		for (String key : testMap.keySet()) {
			testMap.get(key);
		}

		System.out.println("Using keySet() in for-each loop : " + (Calendar.getInstance().getTimeInMillis() - startTime));

		startTime = Calendar.getInstance().getTimeInMillis();
		//Third way using Iterator on entrySet() in while loop
		Iterator<Map.Entry<String,Integer>> itr1 = testMap.entrySet().iterator();
		while(itr1.hasNext())
		{
			Map.Entry<String,Integer> entry = itr1.next();
			entry.getKey();
		    entry.getValue();
		}

		System.out.println("Using entrySet() and iterator : " + (Calendar.getInstance().getTimeInMillis() - startTime));

		startTime = Calendar.getInstance().getTimeInMillis();
		//Third way using Iterator on keySet() in while loop
		Iterator<String> itr2 = testMap.keySet().iterator();
		while(itr2.hasNext())
		{
			String key = itr2.next();
		    testMap.get(key);
		}

		System.out.println("Using keySet() and iterator : " + (Calendar.getInstance().getTimeInMillis() - startTime));
	}
}

Output of above program (in milliseconds) :

Using entrySet() in for-each loop : 50
Using keySet() in for-each loop : 76
Using entrySet() and iterator : 50
Using keySet() and iterator : 75

Observations:

10 lacs is very big number of most the application requirements. Even though the difference is not very substantial in milliseconds, as compare to it was very big in case of for loops. I believe most of us can live with such a minor difference.

But if you want to be very specifically make the conclusion, using entry set is more powerful and yields better performance as comparing to using key set for iteration. Result varies from 20% -- 50% when above program is executed multiple times.

Please do let me know of your thoughts about above analysis.

Happy Learning !!

12 thoughts on “Performance comparison of different ways to iterate over HashMap”

  1. Hi Lokesh,
    Firstly Brilliant article on HashMap working.
    QUERY:Will there be an issue if I create the Hashmap inside the static block itself?

    1. I don’t see any adverse effect on HashMap when you create HashMap inside static block. Only one thing concern me is that HashMap instance will also be static; so all the objects it refers from either keys OR values will not be garbage collected by GC for longer time. Usually static variables in application live longer than their non-static counterparts.

  2. Hi Lokesh,

    As per my Analysis, If you want to retrieve some value from Map based on “key” search then keySet would be faster(little bit) But if you want to parse the whole Map then entrySet would be faster 30 to 40 % based on data size. If required then I can post the code also.

  3. Hi Lokesh,

    I also tried to find the best way to parse a Map and found that results are better with keySet. Here I am posting the code that I used for my analysis. Kindly have a look…and please let me know if you find something valuable to share…Thanks in advance..

    —————————————————————————————————–

    package com.himanshu;

    import java.util.HashMap;
    import java.util.Map;
    import java.util.Map.Entry;

    public class Test
    {
    static Integer finalKey = 10000;

    public static void main(String[] args)
    {
    Map map = new HashMap();

    for(int i=1 ; i <= 1000000; i++)
    {
    map.put(i, "a");
    }

    long first = parseThroughEntrySet(map);

    long second = parseThroughKeySet(map);

    System.out.println("First :"+first);
    System.out.println("Second :"+second);

    }

    static long parseThroughEntrySet(Map map)
    {
    long startTime = System.currentTimeMillis();

    String value;

    for (Entry entry : map.entrySet())
    {
    Integer key = entry.getKey();

    if(key.equals(finalKey))
    {
    value = entry.getValue();
    }

    }

    long endTime = System.currentTimeMillis();

    long totalTime = endTime – startTime;

    return totalTime;
    }

    static long parseThroughKeySet(Map map)
    {
    long startTime = System.currentTimeMillis();

    String value;

    for(Integer key : map.keySet())
    {
    if(key.equals(finalKey))
    {
    value = map.get(key);
    System.out.println(“Done in parseThroughKeySet !!!” +value);
    }
    }

    long endTime = System.currentTimeMillis();

    long totalTime = endTime – startTime;

    return totalTime;
    }

    }

    ————————————————————————————————————————————–

  4. Hi ,

    I have tried this and come with different results everytime , however i find that results are better with key set , even i read somewhere that key set is more better than entry set .

    Regards,
    chandra

Note:- In comment box, please put your code inside [java] ... [/java] OR [xml] ... [/xml] tags otherwise it may not appear as intended.

Leave a Reply

Your email address will not be published. Required fields are marked *


+ two = 10

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>