Performance Comparison of Different Ways to Iterate over a 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.

1. Introduction

In this post, I decided to compare traversal in the HashMap in java. HashMap is a very frequently 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. If you are using this, the for every client, you will be iterating the whole map at least once in your code.

If you are using this type of iteration in many places in code and there are many requests, then you surely would like to optimize your iteration code to make the best use of it. My below-given analysis will help you to decide your 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. Iterating over Map.entrySet()

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

2.2. Iterating over Map.keySet() in For-each Loop

for (String key : map.keySet()) {
  Integer value = map.get(key);
}

2.3. Using Iterator with Map.entrySet()

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();
}

2.4. Using Iterator with Map.keySet()

Iterator<String> keySetIterator = map.keySet().iterator();
while (keySetIterator.hasNext()) {
  String key = keySetIterator.next();
  Integer value = map.get(key);
}

3. Performance Comparison

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

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

static {
  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 10 lacs entries in the best suitable way. We are using the JMH module for benchmarking the performance of all the methods.

@BenchmarkMode(Mode.Throughput)
@Warmup(iterations = 3, time = 10, timeUnit =  TimeUnit.MILLISECONDS)
@Measurement(iterations = 3, time = 10, timeUnit =  TimeUnit.MILLISECONDS)
public class PerformanceCompareForIterations {

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

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

  public static void main(String[] args) throws IOException {

    org.openjdk.jmh.Main.main(args);
  }

  @Benchmark
  public void method1(Blackhole blackhole) {

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

  @Benchmark
  public void method2(Blackhole blackhole) {

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

  @Benchmark
  public void method3(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());
    }
  }

  @Benchmark
  public void method4(Blackhole blackhole) {

    Iterator<String> keySetIterator = map.keySet().iterator();
    while (keySetIterator.hasNext()) {
      String key = keySetIterator.next();
      blackhole.consume(map.get(key));
    }
  }
}

4. Result

The benchmarking score of the above program is :

Benchmark                                                       Mode  Cnt     Score     Error  Units

c.h.c.collections.map.PerformanceCompareForIterations.method1  thrpt   15    54.895 ±   2.441  ops/s
c.h.c.collections.map.PerformanceCompareForIterations.method2  thrpt   15    46.474 ±   1.580  ops/s
c.h.c.collections.map.PerformanceCompareForIterations.method3  thrpt   15    55.088 ±   2.922  ops/s
c.h.c.collections.map.PerformanceCompareForIterations.method4  thrpt   15    46.765 ±   1.827  ops/s

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 using the key set for iteration. 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