I’m always a little annoyed I have to implement sorting Map keys by their values myself in Java. It seems like they should be a part of the standard Collections library or something. Maybe they are and I just haven’t seen it? My solution (gist) is based on feedback from Josh in the comments to a previous post. How does that look to you?
Java maps and sorting
Posted: 1 August 2009 by Jason Adams in UncategorizedTags: algorithms, code, collections, java, programming, sorting
Comments
Looks the way I would have done it. It’s perfectly logical that there is no such service for a HashMap because it is unsorted by definition.
Did you have a look at Apache Commons? Not only do they have a useful box of convenience classes and methods for Strings, they also have a similar thing for collections: http://commons.apache.org/collections/ – their SortedBidiMap looks fancy.
Thanks for the tip on Apache Commons. SortedBidiMap is probably more than I need for this, but glad to know it exists.
you’re doing O(n log n) get()’s which isn’t a big deal if your key’s hashCode() is fast, but might be slow in some cases. Depending on what you’re storing, I would consider sorting a list of Map.Entry, then extract the keys post-sort. This would require zero calls to hashCode().
Good point. For this particular application, I’m just using wrappers for primitives (Integers and Doubles), so I’m assuming the hashCode calculation is fast. Also, the dataset is in the < 200k entries range so the sorting time is pretty much negligible. Still, I should be thinking of bigger data, if I'm wanting a general purpose sort-by-values algorithm.
You can get around the O(n log n) get()’s by using the map’s entrySet() – instead of keySet(). The comparator then has access to both values w/out having to do a look-up in the map. Of course, this means you’d be returning the sorted set of entries, not just the sorted set of keys.
What about TreeMap – its been around since almost forever?
A map that further guarantees that it will be in ascending key order, sorted according to the natural ordering of its keys (see the Comparable interface), or by a comparator provided at sorted map creation time. This order is reflected when iterating over the sorted map’s collection views (returned by the entrySet, keySet and values methods). Several additional operations are provided to take advantage of the ordering. (This interface is the map analogue of the SortedSet interface.)