Java. Sorted map by value [duplicate]

Question

Possible Duplicate:
How to sort a Map<Key, Value> on the values in Java?

I need sorted map like TreeMap but sorted by value. My map will be huge, so i can't just sort my map anytime i need. Exist any good solution to resolve this problem? Maybe exist external jar who meets this?

Answer 1

There are a number of ways to satisfy your requirement. As you have subsequently clarified that you may have duplicate objects in your current TreeMap, perhaps you could replace your TreeMap with a third-party multimap (Guava, Apache Commons Collections), then swap your keys and values around - i.e. replace TreeMap<Key, Value> with Multimap<Value, Key>. Depending on the details of your situation I believe this stands a good chance of working for you.

Answer 2

If you are using the TreeMap to maintain an index for your values, i.e. you are using it primarily to quickly find the matching value for a given key, another thing you can do is keep 2 data structures:

• The TreeMap that you are using now for the indexing
• A PriorityQueue (or other sorted list) to iterate over your values in sorted order

Then, simply add and remove values to both lists when you have any changes. For this, you will not need to keep two copies of the values around either. You can simply add the one copy you have now to both lists, since the lists only work with the references to your values.

Answer 3

There doesn't really exist any data structure that could do this efficiently: you have to maintain a data structure that makes it efficient to look up by keys, and sorting the values makes it more difficult to maintain that structure.

If you don't modify the map after it's created, though, then you could do something like this:

List<Map.Entry<Key, Value>> list = new ArrayList<Map.Entry<Key, Value>>(
    map.entrySet());
Collections.sort(list, new Comparator<Map.Entry<Key, Value>>() {
  public int compare(Map.Entry<Key, Value> e1, Map.Entry<Key, Value> e2) {
    return e1.getValue().compareTo(e2.getValue());
  }
});
Map<Key, Value> sortedByValues = new LinkedHashMap<Key, Value>();
for (Map.Entry<Key, Value> entry : list) {
  sortedByValues.put(entry.getKey(), entry.getValue());
}

The resulting LinkedHashMap would iterate in sorted value order.

Answer 4

If your data are unique you could hold them in a Set which would be iterable in ascending order (assuming you implement Comparable).

You could then hold your Map separately without much extra cost than just holding the original Map.