5

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?

Community
  • 1
  • 1
user1711160
  • 169
  • 1
  • 10
  • http://stackoverflow.com/questions/5483330/how-do-i-convert-a-hashmap-to-a-list http://stackoverflow.com/questions/2784514/sort-arraylist-of-custom-objects-by-property – Tian Na Nov 22 '12 at 15:35
  • Easiest solution is to maintain both your `TreeMap` and a `TreeSet` of values. – Dunes Nov 22 '12 at 19:25

4 Answers4

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.

Mark A. Fitzgerald
  • 1,249
  • 1
  • 9
  • 20
  • 1
    This solution probably can work, but i can't duplicate values. – user1711160 Nov 22 '12 at 15:37
  • If some of your current map values are duplicates, then a reversed multimap (http://en.wikipedia.org/wiki/Multimap), which allows multiple values to be associated with one key may be what you need. Google Guava (http://docs.guava-libraries.googlecode.com/git-history/v13.0.1/javadoc/com/google/common/collect/TreeMultimap.html) and Apache Commons Collections (http://commons.apache.org/collections/api-3.1/org/apache/commons/collections/MultiMap.html) provide this data structure. – Mark A. Fitzgerald Nov 22 '12 at 16:33
  • I've revised my answer to use a multimap based on your refined requirement. – Mark A. Fitzgerald Nov 22 '12 at 19:17
0

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.

Markus A.
  • 12,349
  • 8
  • 52
  • 116
0

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.

Louis Wasserman
  • 191,574
  • 25
  • 345
  • 413
0

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.

OldCurmudgeon
  • 64,482
  • 16
  • 119
  • 213