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 theHashMap
implementation. It calls the provided lambda expression for each element in theHashMap
. 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 !!
Comments