A Java Map Trick to Improve Performance

Make your code more performant using this map iteration trick…

How do you iterate your hashmaps? Usually, we use keyset() in a for each loop, and inside the loop, fetch the values for the map. Then we do with the key and the fetched value, whatever needs doing, and move on with our day. Tell me in the comments if you do something different.

There is an alternative way to doing the same iteration. We can use the entrySet() method in the for each loop. This would do the following: instead of iterating through set of keys, it would iterate through the entry object which contains both the key and the value.

I’m here to tell you that the entrySet() iteration is the better one. Not just in terms of performance, but in terms of code quality as well. Why so, you might ask.

Think about what you usually need to do with the contents of the map when you iterate. You do operations on both the key and the value, right? So doesn’t it make sense for the iterator to provide us with both of these details while iterating?

Now contrast this with the keySet() method of iteration. The iterator gives you half of the information you need, and you manually fetch the other half. Even if we discount the manual work we are doing, how can we ignore the extra unnecessary operation of fetching the value? This also consumes a few CPU cycles. Granted it would be of constant complexity. But redundant CPU cycles are redundant and need to be eliminated. Especially, if we have identified them.

Apart from this, we can’t even discount the fact of constant complexity. Do you know when is this especially true? When we have lots of keys in our map to be iterated. In such a case, we face 2 problems.

1. The cost of fetching the values adds up, because of many entries to be processed.
2. Many keys increase the risk of hash collision, which would render the value fetching complexity of O(n) or O(log n). This would further unnecessarily increase the runtime of the entire iteration.

Using entrySet() for each loop is a great rule to follow. And turns out, that what I have said above is nothing new. This can be seen from the fact that nowadays SonarQube, which enforces code quality, also respects this optimization, and flags it as a code smell.

So are keySet() and values() methods useless in the Map interface? Should we always use entrySet() only? The answer is no. We need to use keySet() and values() methods when we only need to work with keys and values of the map respectively, but we don’t want both. When we need both, we should use entrySet().

Tell me in the comments whether you are aware of other such quirks or performance optimizations. Just add in some fun facts about Java or some design pattern etc you might be taking for granted till now ;)