Java maps and sorting

Posted: 1 August 2009 in Uncategorized
Tags: , , , , ,

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?

About these ads
Comments
  1. DrNI@AM says:

    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.

  2. Jon Elsas says:

    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().

    • Jason Adams says:

      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.

  3. jhumphries says:

    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.

  4. Umm, TreeMap? says:

    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.)

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s