Iterate over a HashMap: Performance Comparison

This Java tutorial discusses the different ways to iterate over a HashMap and compare the performance of each technique so we can make an informed decision.

It is recommended to learn how HashMap works internally to know how the data is stored in a HashMap. If my last similar post, we compared different “for loop” available in Java. These studies usually help in setting up best practices for your next project.

1. Introduction

In this post, I decided to compare the performance of different ways to traverse through the HashMap in Java. HashMap is a very widely used class, and most of the time, we fetch the value using get(Object key) method provided by the class. But it is sometimes required to iterate over the whole Map and fetch all key-value pairs stored in it.

For example, analyzing all request parameters sent from the client. In such cases, for every client, we are iterating the whole map at least once in during the request processing.

If we are using this type of iteration in many places in the code and there are many requests, then we surely would like to optimize the HashMap iteration code to make the best use of it. My below-given analysis will help us to decide our next step.

2. Different Ways to Iterate over a Map

Let us start with different ways to iterate over HashMap. The HashMap has been defined as follows:

Map<String, Integer> map = new HashMap();

2.1. HashMap.forEach()

Since Java 8, we can use the forEach() method to iterate over the keys and values stored in Map.

map.forEach((key, value) -> {
	
	System.out.println(key + ": " + value);
	//...
});

2.2. Iterating over Map Entries

The entrySet() method returns all the entries in a Set view that we can iterate similar to a normal HashSet in Java.

for (Map.Entry<String, Integer> entry : map.entrySet()) {

  String key = entry.getKey();
  Integer value = entry.getValue();

  //...
}

2.3. Iterating over Map Keys and Accessing Values

The keySet() method returns all keys as a Set. We can iterate over all the keys, and use them to access the values from the Map. Note that it requires an additional step to access the value, so in most cases, it is not recommended approach.

for (String key : map.keySet()) {

  Integer value = map.get(key);

  //...
}

2.4. Using Iterator

As we get the Set view from entrySet() and keySet(), we can use the Iterator to iterate through the Map.

The following code iterates over the Map entries using the Iterator.

Iterator<Entry<String, Integer>> entryIterator = map.entrySet().iterator();

while (entryIterator.hasNext()) {

  Map.Entry<String, Integer> entry = entryIterator.next();
  String key = entry.getKey();
  Integer value = entry.getValue();

  //...
}

Similarly, the following code iterates over the Map keys using the Iterator and accesses the values using keys.

Iterator<String> keySetIterator = map.keySet().iterator();

while (keySetIterator.hasNext()) {

  String key = keySetIterator.next();
  Integer value = map.get(key);

  //...
}

3. Comparing the Performance of Different Techniques

Now let us compare the performances of all types of iterations for a common data set stored in the Map. We are storing 1 million key-value pairs in the Map.

Map<String, Integer> map = new HashMap();

for (int i = 0; i < 10_00_000; i++) {
  map.put(String.valueOf(i), i);
}

We will iterate over the map in all four ways. We will also fetch the key and value from the map for all entries in the best suitable way. We are using the JMH module for benchmarking the performance of all the methods.

@Benchmark
public void usingForEach(Blackhole blackhole) {

  map.forEach((key, value) -> {
    blackhole.consume(key);
    blackhole.consume(value);
  });
}

@Benchmark
public void usingEntrySetWithForLoop(Blackhole blackhole) {

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

@Benchmark
public void usingKeySetWithForLoop(Blackhole blackhole) {

  for (String key : map.keySet()) {
    blackhole.consume(map.get(key));
  }
}

@Benchmark
public void usingEntrySetWithForIterator(Blackhole blackhole) {

  Iterator<Entry<String, Integer>> entryIterator = map.entrySet().iterator();
  while (entryIterator.hasNext()) {
    Map.Entry<String, Integer> entry = entryIterator.next();
    blackhole.consume(entry.getKey());
    blackhole.consume(entry.getValue());
  }
}

4. Result

The benchmarking score of the above program is :

c.h.c.collections.map...usingForEach 					thrpt   15    89.044 ±   2.703  ops/s
c.h.c.collections.map...usingEntrySetWithForLoop 		thrpt   15    54.906 ±   6.326  ops/s
c.h.c.collections.map...usingKeySetWithForLoop  		thrpt   15    52.163 ±   4.517  ops/s
c.h.c.collections.map...usingEntrySetWithForIterator  	thrpt   15    63.494 ±   4.334  ops/s

Although there is not much difference in all mobe methods, we can see that:

• Using for loop with the keySet(), entrySet() methods perform almost equally.
• Using iterator() methods perform comparatively worse.
• Surprisingly, the forEach() method takes the most time. It is because the forEach method uses internal iteration, which means that the iteration logic is handled within the HashMap implementation. It calls the provided lambda expression for each element in the HashMap. This internal iteration comes with some overhead due to lambda expression execution and additional function calls.

For the sake of clean coding, we can conclude that:

• If Map contains only a few entries, using HashMap.forEach() is the best way to iterate over a HashMap.
• If Map contains only a million of entries, using HashMap.entrySet() is the best way to iterate over a HashMap.

5. Conclusion

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

But if you want to make the conclusion, using an entry set very specifically is more powerful and yields better performance than others. The result varies from 20% – 50% when the above program is executed multiple times.

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

Happy Learning !!

Source Code on Github