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?
1 Aug
Posted by DrNI@AM on 2 August 2009 at 03:46:20
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.
Posted by Jason Adams on 2 August 2009 at 08:09:22
Thanks for the tip on Apache Commons. SortedBidiMap is probably more than I need for this, but glad to know it exists.
Posted by Jon Elsas on 2 August 2009 at 06:58:01
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().
Posted by Jason Adams on 2 August 2009 at 08:22:10
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.
Posted by jhumphries on 8 August 2009 at 18:38:30
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.