Benchmarking Approaches to Sort Java Map by Value

Spread the love
  •  
  •  
  •  
  •  

As the name suggests, this blog tries to explore a few ways one could use to sort a Java Map by values it contains and present a quick comparison of these approaches.

Alright, first things first, sorting a Map by Value is not supported directly through a JDK API, at least until Java 8, so one needs to write some code to do that. Java 8 has a somewhat direct API and we will explore that too as one of the approaches.

So, without wasting any time, let us directly dive into the approaches.

Using TreeMap

When one thinks of Java Maps and sorting, the first abstraction that comes to mind is TreeMap, an implementation of the SortedMap interface, provided within the JDK itself. It stores pairs, maintained in a sorted order. So one idea could be to create a TreeMap from the Map you want to sort and you are done!!

Well, that is easier said that done, because by default, the ordering in a TreeMap is a function of the natural sorting order of the Key, assuming that the Key implements Comparable interface. Alternately, sorting can also be governed by providing an implementation of Comparator interface during creation of the Map.  However, even with a custom Comparator, the sort order is defined by the Keys.

Essentially in terms of code, the Comparator instance you provide to a TreeMap would receive the two keys to compare as inputs to the compare method.

Considering that our key for the Map is Employee class and value is an Integer, our TreeMap definition to have the TreeMap sorted by employee name would look something like

As you can observe, since there is no reference to the values in the Comparator code, the order will be driven by the Keys. But we are looking at sorting by values.

Alright, let me break the suspense!!!

The solution is simple enough – we have the Employee objects (which are Keys in the original Map as well), and we have the original Map that we want to sort. Why not look up the Values associated with the Keys in the Comparator code and then use the values to drive the compareTo. Here is a sample code snippet.

Alright, so we have learnt one smart way to use a TreeMap and sort a Map by values!!!

Let us look at another way.

Using Map.Entry collection

Any Java Map can return a Collection of Map.Entry objects. And we know how easy it is to sort a collection in Java. So, we can grab the collection of Map.Entry objects, turn it into a List, sort the list by the Value object within Map.Entry objects, and then create a new LinkedHashMap and insert all the Map.Entry objects from the sorted list. I realise it sounds a bit complex, but a look at code would make it much more easier. So, here we go…

Alright, all of the above certainly makes sense, however there is some work to do – one has to come up with an approach, and implement it in code, unit test it and so on. What if there is something ready to use….after all, we are in the age of read to eat meals 🙂

Here comes Java 8 to the rescue!!!

Using Java 8

As you may observe, Java 8 certainly does that in style!!! Well, if you are familiar with Java 8, then you can easily skim through what is being done. For those who are not, this is nothing but our Map.Entry collection approach, at least logically, with use of some Java 8 specific features like streams, mappers and collectors.

Here is a quick way to understand it –

  • Think of stream() as a way to iterate over a view of the entryset
  • sorted(Map.Entry.comparingByValue) is like running a Comparator with value used for comparison, just that this is provided out of the box by Java 8
  • The call to collect() is to accumulate the results of the above two operations into a new LinkedHashMap

Comparison of Approaches

So, all in all, we have looked at three approaches of achieving the same (well it is not exactly same, because the TreeMap implementation lets us have a running sorted Map that maintains the sorted order all along its life, while the other two approaches give us a static sorted Map when asked for).  So that is one big difference.

Let us now compare these on another aspect, that is how do they perform on timing.

To start with, one may think that the TreeMap approach may probably be better since it is based on the binary tree idea, and if you think alike, a big surprise awaits you.

The average time taken for sorting a Map containing close to 2 million entries using each of the above described approaches is as follows:

TreeMap approach: ~15000 milliseconds

Map.Entry Collection approach: ~6010 milliseconds

Java 8 approach: ~5500 milliseconds

As you may observe, the TreeMap approach is in fact the costliest of all!! Why so?

On the first look, the not-so-obvious reason appears to lie hidden in the code we wrote up in our Comparator we passed to the TreeMap. A careful look at the code would make one realise that there are two additional Map lookup operations (get calls to the original Map) involved for every comparison call. Obviously, these would consume some additional time. So, I tried segregating the lookup time from the overall time, post which, one would expect to see comparable performance. However, that was not case. It appears so that the lookup time is just half of the overall time, which means the other half is spent populating the TreeMap and it is still way higher than the other two approaches in our example above. WHY? The reason is again because of a “kind of lookup”. The TreeMap would perform a typical binary tree element addition operation to find the right place for the new element, and this would be done for every new element.

So, the learning here is very simple….its not only important to choose the right algorithm, its equally important to choose the right data structures to perform the task at hand. TreeMap is useful in cases where the elements in the Map continually need to be maintained in sorted order.  However there is a cost involved for maintaining that order on an ongoing basis. So, in cases where getting the elements in a sorted fashion is a one time need, the other techniques outlined would payoff well.

Happy coding!! Happy Exploring!!


Spread the love
  •  
  •  
  •  
  •  

Leave a Reply

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