Java: Map sorted by value

November 20th, 2008 by  |  Published in Java  |  15 Comments

Today, I wanted to solve a – at first sight – rather simple problem in Java. I wanted to iterate over the keys and values of a Map in an order given by its values. E.g.

Map m = new ...
m.put("foo", 47);
m.put("bar", 11);
m.put("baz", 11);
m.put("qux", 100);
// {bar=11, baz=11, foo=47, qux=100}
System.out.println(m);
 
m.put("foo", 101);
// {bar=11, baz=11, qux=100, foo=101}
System.out.println(m);


For the impatient: skip the following block of finest blah that makes this entry look far more complicated than it really is 😉

I didn’t know of any data structure that solves the problem, so I started googling. However, 30 minutes of online research for an existing implementation didn’t give a satisfying result. A lot of people describe their need for such a data structure though (e.g. 1, ). Forums and blogs are full of suggestions to either use a Comparator with a reference to the map itself, or convert a regular Map to a LinkedHashMap (that keeps insertion order) by sorting and inserting, sort a List of Map.Entry or use a dedicated helper class, …

Not a single suggested solution did fully hide the sorting from the user. I therefore decided to go for my own implementation. My first thought was to create a Map implementation that uses two data structures internally: a hash table for key-value-lookups and a sorted structure for iterations. A first idea to use a HashMap and a TreeMap wasn’t promising though, as this wouldn’t allow duplicate values (which was a requirement).

After browsing through the commons collections library for a while I came up with an implementation. It is based on LinkedMap (which is the same as LinkedHashMap but customizable) and uses the double-linked list to keep iteration order:

// required to access LinkEntry.before and LinkEntry.after
package org.apache.commons.collections.map;
 
// SNIP: imports
 
/**
* map implementation based on LinkedMap that maintains a sorted list of
* values for iteration
*/
public class ValueSortedHashMap extends LinkedMap {
private final boolean _asc;
 
// don't use super()!
public ValueSortedHashMap(final boolean asc) {
super(DEFAULT_CAPACITY);
_asc = asc;
}
 
// SNIP: some more constructors with initial capacity and the like
 
protected void addEntry(final HashEntry entry, final int hashIndex) {
final LinkEntry link = (LinkEntry) entry;
insertSorted(link);
data[hashIndex] = entry;
}
 
protected void updateEntry(final HashEntry entry,
final Object newValue) {
entry.setValue(newValue);
final LinkEntry link = (LinkEntry) entry;
link.before.after = link.after;
link.after.before = link.before;
link.after = link.before = null;
insertSorted(link);
}
 
private void insertSorted(final LinkEntry link) {
LinkEntry cur = header;
// iterate whole list, could (should?) be replaced with quicksearch
// start at end to optimize speed for in-order insertions
while ((cur = cur.before) != header && !insertAfter(cur, link)) {
}
link.after = cur.after;
link.before = cur;
cur.after.before = link;
cur.after = link;
}
 
protected boolean insertAfter(final LinkEntry cur,
final LinkEntry link) {
if (_asc) {
return ((Comparable) cur.getValue())
.compareTo((V) link.getValue()) <= 0;
} else {
return ((Comparable) cur.getValue())
.compareTo((V) link.getValue()) >= 0;
}
}
 
public boolean isAscending() {
return _asc;
}
}

And that’s it. If somebody finds the time to improve insertion speed by implementing a quick search or similar, please send me your changes – your not required to do so, as all the code here is in the public domain, no GPL burdens ;).

Responses

  1. Ivan says:

    November 20th, 2008 at 5:17 pm (#)

    A sorted map makes no sense. Instead you need another view into the entries right? I would convert the Entry set into a List of map entries. Then you simply use a comparator which uses your values with the Collections class against your new list and you have your sorted entries by value.

  2. Stefan Fußenegger says:

    November 20th, 2008 at 5:28 pm (#)

    Yeah, that’s really *a lot* easier …

  3. Stefan Fußenegger says:

    November 20th, 2008 at 5:38 pm (#)

    Okay, now without sarcasm 🙂 It makes sense. In my special case I needed to rank a set of objects according to an integer value. Furthermore, this ranking should be passed through some methods that might add some more entries to the map. If I’d done it your way, I’d have to pass two collections to all of those methods, always make sure that the contents of those collections are in-sync, and always make sure the list is sorted when I want to extract the best/worst/top 10.I even use that map with a Hibernate CollectionUserType which makes it very easy to persist as a simple [map collection-type=”” /] mapping.So yes, in myho it *really* makes sense.

  4. Anonymous says:

    November 20th, 2008 at 11:42 pm (#)

    If ALL of the requirements had been declared (documented) up-front then corresponding implementations could have been suggested. Sarcasm or not – if you do not make clear what you want / need then you are not likely to get it.

  5. Anonymous says:

    November 21st, 2008 at 12:27 am (#)

    Hi Annonymous (or Ivan?)Not sure if you read the entry. If yes, you should have noted that Stefan provided …… a link that defines such requirements… links to different implementations… an implementation that is *much* simpler than all the other approaches and even more efficient (apart from inseration that really leave space for improvment)But most of all, the provided code is really great for people with similar requirements (like me). And those people already know that such a data structure makes perfect sense. They only want to get the code. And that’s what you can find here.Thanks Stefan, really useful post!Cheers, Marc

  6. Michael Rimov says:

    November 21st, 2008 at 4:02 am (#)

    How about Commons Collections SortedBidiMap?http://commons.apache.org/collections/api-release/index.htmlHTH!-Mike (R)

  7. Stefan Fußenegger says:

    November 21st, 2008 at 9:07 am (#)

    Hi Mike, thanks for your reply.There is a reasons not to use a BidiMap: BidiMaps don’t allow duplicate values. Even the values need to be a follow the set spec in order to be used as keys for a map!for instance:final TreeBidiMap m = new TreeBidiMap();m.put(“foo”, 47);m.put(“bar”, 11);m.put(“baz”, 11);m.put(“qux”, 100);System.out.println(m);// {baz=11, foo=47, qux=100}(Additionally, lookups by values aren’t needed for my purpose.)Regards, Stefan

  8. Anonymous says:

    November 21st, 2008 at 9:35 am (#)

    public class Map { private class Helper{ String s;int i; public Helper(String s,int i){this.s=s;this.i=i;} public String toString(){return s+","+i;} } private Vector<Helper> vec = new Vector<Helper>(); public void put(String s,int i){ vec.add(new Helper(s,i)); } public String toString(){ Comparator c = new Comparator<Helper>(){ public int compare(Helper h1,Helper h2){ return (h1.i < h2.i) ? -1: ((h1.i > h2.i) ? 1 : h1.s.compareTo(h2.s)); } }; Collections.sort(vec,c); String s=""; for (Helper h : vec){s+=h+"n";}; return s; }}

  9. uudashr's blog says:

    November 21st, 2008 at 10:22 am (#)

    Why you need it to be sort by value? does it take longer time to lookup?

  10. Stefan Fußenegger says:

    November 21st, 2008 at 10:42 am (#)

    @Anonymous:Not sure if this is even worth a reply, because- Map interface not impelmented- Inefficient lookup of keys- Keys not unique (Set spec!)- Full sort on every iteration (performance!)One could replace the Vector with a TreeSet for better performance. However, you won't be able to keep the keys unique. One could try to implement an equals implementation based on the key and a Comparable (or Comparator) implementation based on the values. One could … but everybody who knows how a tree works internally should know that this won't work. equals and compareTo must always be consistent, i.e. if a.equals(b) == (a.compareTo(b) == 0) (where a != null && b != null). Knowing this, every implementation based on a single Tree(Map|Set) is doomed to failure.@uudashr:Simple example: I want to rank a set of objects by a value. Queries for first or last object should be fast. Frequent full or partial iterations according to the ranking should be efficient, even with frequent changes.RegardsBut I am somhow surprised that "everybody" wants to suggest another solution. I didn't ask for that, I just wanted to share mine

  11. Anonymous says:

    November 21st, 2008 at 1:13 pm (#)

    > But I am somhow surprised that "everybody" wants to suggest another solution.Orly?Welcome to teh intartubes.

  12. Yves Zoundi says:

    November 21st, 2008 at 1:19 pm (#)

    :-), you should expect such criticism when you post code snippets and don’t provide a “complete” context.You provide a solution for a very common problem that most developers came/come across many times. How to sort a Map by values, if possible, with good performance?I usually do the same as @Ivan, I use an Entry from a Map EntrySet and I sort on Entry.getValue() using a Comparator. However, my requirements are probably different than yours.Nice articleYves ZoundiVFSJFileChooser : http://vfsjfilechooser.sf.netXPontus XML Editor : http://xpontus.sf.net

  13. Stefan Fußenegger says:

    November 21st, 2008 at 1:57 pm (#)

    @Anonymous:Well, not really surprised. I thought I added a ‘:)’ at the end of that sentence. Bur I really didn’t expect that much feedback though. A considerable amout of users of “teh intertubes” normally ignore my blog most of the time ;)@Yves:I’m always prepared for criticism and open for suggestions. But yelling “A sorted map makes no sense” without giving valid reason is neither of both. It might not even be that my requirements are that different though. I was just looking for a cleaner (in terms of transparency, encapsulation) and easier to use solution. I need the map sorted most of the time, so adding that to the actual map implementation makes sense. Especially if you consider how easy one could forget to sort the entries (and produce buggy code).But finally, this map was more of a programming exercise. Just one of those little (irrelevant?) challenges a programmer faces from time to time. You could go for the quick and dirty way … or bear the challenge, invest some sweat and live happily ever after 😀

  14. Adam says:

    March 11th, 2009 at 5:56 am (#)

    What about this…

    public static Ordering<Map.Entry> orderByEntryValue() {
    return Ordering.from(
    new Comparator<Map.Entry>() {
    @Override
    public int compare(Entry o1, Entry o2) {
    return o1.getValue().compareTo(o2.getValue());
    }
    });
    }

    …and then…

    orderByEntryValue().max( map.entrySet() );

    …using Ordering from google collections!

  15. Stefan Fußenegger says:

    March 11th, 2009 at 8:21 am (#)

    Hi Adam,

    Well, first I have to admit that I don’t know google collections (yet). However, It looks as if the values are sorted on demand and only once (as some other approaches suggested above). The main differences to my suggestion of maintaining a sorted list on insertion are:

    – not transparent
    – worse performance with alternating inserts and (sorted) iterations

Leave a Response