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

Question

I am relatively new to Java, and often find that I need to sort a Map on the values. Since the values are not unique, I find myself converting the keySet into an array, and sorting that array through array sort with a custom comparator that sorts on the value associated with the key. Is there an easier way?

Answer 1

From http://www.programmersheaven.com/download/49349/download.aspx

static Map sortByValue(Map map) {
     List list = new LinkedList(map.entrySet());
     Collections.sort(list, new Comparator() {
          public int compare(Object o1, Object o2) {
               return ((Comparable) ((Map.Entry) (o1)).getValue())
              .compareTo(((Map.Entry) (o2)).getValue());
          }
     });
// logger.info(list);
Map result = new LinkedHashMap();
for (Iterator it = list.iterator(); it.hasNext();) {
     Map.Entry entry = (Map.Entry)it.next();
     result.put(entry.getKey(), entry.getValue());
     }
return result;
}

Answer 2

Depending on the context, using java.util.LinkedHashMap<T> which rememebers the order in which items are placed into the map. Otherwise, if you need to sort values based on their natural ordering, I would recommend maintaining a separate List which can be sorted via Collections.sort().

Answer 3

the commons-collections library contains a solution called TreeBidiMap:

http://commons.apache.org/collections/api-release/org/apache/commons/collections/bidimap/TreeBidiMap.html

or, you could have a look at the Google Collections API. It has a TreeMultimap which you could use:

http://google-collections.googlecode.com/svn/trunk/javadoc/com/google/common/collect/TreeMultimap.html

and if you don't want to use these framework... they come with sources.

Answer 4

If your Map values implement Comparable (e.g. String), this should work

Map<Object, String> map = new HashMap<Object, String>();
// Populate the Map
List<String> mapValues = new ArrayList<String>(map.values());
Collections.sort(mapValues);

If the map values themselves don't implement Comparable, but you have an instance of Comparable that can sort them, replace the last line with this:

Collections.sort(mapValues, comparable);

Answer 5

You say you often come across this problem?? I've been programming Java for over 8 years now and must say I haven't needed it more then two or three times. Maybe I am missing something; but I guess you are using a map where a different data structure might be a better solution. Could you give a concrete example?

Answer 6

Sorry, I just read it's about sorting the map upon the values. Was wrong on that, thoght you want key based sortig. Anyway: for sorting upon the keys I found a better solution with a TreeMap (I will try to get a solution for value based sorting ready too):

public static void main(String[] args) {
 Map<String, String> unsorted = new HashMap<String, String>();
 unsorted.put("Cde", "Cde_Value");
 unsorted.put("Abc", "Abc_Value");
 unsorted.put("Bcd", "Bcd_Value");

 Comparator<String> comparer = new Comparator<String>() {
  @Override
  public int compare(String o1, String o2) {
   return o1.compareTo(o2);
  }};

 Map<String, String> sorted = new TreeMap<String, String>(comparer);
 sorted.putAll(unsorted);
 System.out.println(sorted);
}

Old post:

I would suggest this operation, maybe you find it well working:

public static void main(String[] args) {

 Map<String, String> map = new HashMap<String, String>();

 map.put("Cde", "Cde_Value");
 map.put("Abc", "Abc_Value");
 map.put("Bcd", "Bcd_Value");

 System.out.println(sort(map, new Comparator<String>() {

  @Override
  public int compare(String o1, String o2) {
   return o1.compareTo(o2);
  }}));

}

@SuppressWarnings("unchecked")
public static <K, V> Map<K,V> sort(Map<K, V> in, Comparator<? super K> compare) {
 Map<K, V> result = new LinkedHashMap<K, V>();
 K[] array = (K[])in.keySet().toArray();
 Arrays.sort(array, compare);
 for (K item : array) {
  result.put(item, in.get(item));
 }
 return result;
}

Output would be:

{Abc=Abc_Value, Bcd=Bcd_Value, Cde=Cde_Value}

Greetz, GHad

Answer 7

Use java.util.TreeMap.

"The map is sorted according to the natural ordering of its keys, or by a Comparator provided at map creation time, depending on which constructor is used."

Answer 8

Sorting the keys requires the Comparator to look up each value for each comparison. A more scalable solution would use the entrySet directly, since then the value would be immediately available for each comparison (although I haven't backed this up by numbers).

Here's a generic version of such a thing:

public static <K, V extends Comparable<? super V>> List<K> getKeysSortedByValue(Map<K, V> map) {
    final int size = map.size();
    final List<Map.Entry<K, V>> list = new ArrayList<Map.Entry<K, V>>(size);
    list.addAll(map.entrySet());
    final ValueComparator<V> cmp = new ValueComparator<V>();
    Collections.sort(list, cmp);
    final List<K> keys = new ArrayList<K>(size);
    for (int i = 0; i < size; i++) {
        keys.set(i, list.get(i).getKey());
    }
    return keys;
}

private static final class ValueComparator<V extends Comparable<? super V>>
                                     implements Comparator<Map.Entry<?, V>> {
    public int compare(Map.Entry<?, V> o1, Map.Entry<?, V> o2) {
        return o1.getValue().compareTo(o2.getValue());
    }
}

There are ways to lessen memory rotation for the above solution. The first ArrayList created could for instance be re-used as a return value; this would require suppression of some generics warnings, but it might be worth it for re-usable library code. Also, the Comparator does not have to be re-allocated at every invocation.

Here's a more efficient albeit less appealing version:

public static <K, V extends Comparable<? super V>> List<K> getKeysSortedByValue2(Map<K, V> map) {
    final int size = map.size();
    final List reusedList = new ArrayList(size);
    final List<Map.Entry<K, V>> meView = reusedList;
    meView.addAll(map.entrySet());
    Collections.sort(meView, SINGLE);
    final List<K> keyView = reusedList;
    for (int i = 0; i < size; i++) {
        keyView.set(i, meView.get(i).getKey());
    }
    return keyView;
}

private static final Comparator SINGLE = new ValueComparator();

Finally, if you need to continously access the sorted information (rather than just sorting it once in a while), you can use an additional multi map. Let me know if you need more details...

Answer 9

Okay, this version works with two new Map objects and two iterations and sorts on values. Hope, the performs well although the map entries must be looped twice:

public static void main(String[] args) {
 Map<String, String> unsorted = new HashMap<String, String>();
 unsorted.put("Cde", "Cde_Value");
 unsorted.put("Abc", "Abc_Value");
 unsorted.put("Bcd", "Bcd_Value");

 Comparator<String> comparer = new Comparator<String>() {
  @Override
  public int compare(String o1, String o2) {
   return o1.compareTo(o2);
  }};

 System.out.println(sortByValue(unsorted, comparer));

}

public static <K, V> Map<K,V> sortByValue(Map<K, V> in, Comparator<? super V> compare) {
 Map<V, K> swapped = new TreeMap<V, K>(compare);
 for(Entry<K,V> entry: in.entrySet()) {
  if (entry.getValue() != null) {
   swapped.put(entry.getValue(), entry.getKey());
  }
 }
 LinkedHashMap<K, V> result = new LinkedHashMap<K, V>();
 for(Entry<V,K> entry: swapped.entrySet()) {
  if (entry.getValue() != null) {
   result.put(entry.getValue(), entry.getKey());
  }
 }
 return result;
}

The solution uses a TreeMap with a Comparator and sorts out all null keys and values. First, the ordering functionality from the TreeMap is used to sort upon the values, next the sorted Map is used to create a result as a LinkedHashMap that retains has the same order of values.

Greetz, GHad

Answer 10

When I'm faced with this, I just create a list on the side. If you put them together in a custom Map implementation, it'll have a nice feel to it... You can use something like the following, performing the sort only when needed. (Note: I haven't really tested this, but it compiles... might be a silly little bug in there somewhere)

(If you want it sorted by both keys and values, have the class extend TreeMap, don't define the accessor methods, and have the mutators call super.xxxxx instead of map_.xxxx)

package com.javadude.sample;

import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Set;

public class SortedValueHashMap<K, V> implements Map<K, V> {
    private Map<K, V> map_ = new HashMap<K, V>();
    private List<V> valueList_ = new ArrayList<V>();
    private boolean needsSort_ = false;
    private Comparator<V> comparator_;

    public SortedValueHashMap() {
    }
    public SortedValueHashMap(List<V> valueList) {
        valueList_ = valueList;
    }

    public List<V> sortedValues() {
        if (needsSort_) {
            needsSort_ = false;
            Collections.sort(valueList_, comparator_);
        }
        return valueList_;
    }

    // mutators
    public void clear() {
        map_.clear();
        valueList_.clear();
        needsSort_ = false;
    }

    public V put(K key, V value) {
        valueList_.add(value);
        needsSort_ = true;
        return map_.put(key, value);
    }

    public void putAll(Map<? extends K, ? extends V> m) {
        map_.putAll(m);
        valueList_.addAll(m.values());
        needsSort_ = true;
    }

    public V remove(Object key) {
        V value = map_.remove(key);
        valueList_.remove(value);
        return value;
    }

    // accessors
    public boolean containsKey(Object key)           { return map_.containsKey(key); }
    public boolean containsValue(Object value)       { return map_.containsValue(value); }
    public Set<java.util.Map.Entry<K, V>> entrySet() { return map_.entrySet(); }
    public boolean equals(Object o)                  { return map_.equals(o); }
    public V get(Object key)                         { return map_.get(key); }
    public int hashCode()                            { return map_.hashCode(); }
    public boolean isEmpty()                         { return map_.isEmpty(); }
    public Set<K> keySet()                           { return map_.keySet(); }
    public int size()                                { return map_.size(); }
    public Collection<V> values()                    { return map_.values(); }
}

Answer 11

If you are a beginner, chances are high your approach is wrong. While there are cases where you'd want a map sorted, a map is usually not the right data structure for sorted storage. You'd probably be better off with something like a balanced tree. Are you sure you need the associativity of the map?

Answer 12

While I agree that the constant need to sort a map is probably a smell, I think the following code is the easiest way to do it without using a different data structure.

public class MapUtilities {

public static <K, V extends Comparable<V>> List<Entry<K, V>> sortByValue(Map<K, V> map) {
 List<Entry<K, V>> entries = new ArrayList<Entry<K, V>>(map.entrySet());
 Collections.sort(entries, new ByValue<K, V>());
 return entries;
}

private static class ByValue<K, V extends Comparable<V>> implements Comparator<Entry<K, V>> {
 public int compare(Entry<K, V> o1, Entry<K, V> o2) {
  return o1.getValue().compareTo(o2.getValue());
 }
}

}

And here is an embarrassingly incomplete unit test:

public class MapUtilitiesTest extends TestCase {
public void testSorting() {
 HashMap<String, Integer> map = new HashMap<String, Integer>();
 map.put("One", 1);
 map.put("Two", 2);
 map.put("Three", 3);

 List<Map.Entry<String, Integer>> sorted = MapUtilities.sortByValue(map);
 assertEquals("First", "One", sorted.get(0).getKey());
 assertEquals("Second", "Two", sorted.get(1).getKey());
 assertEquals("Third", "Three", sorted.get(2).getKey());
}

}

The result is a sorted list of Map.Entry objects, from which you can obtain the keys and values.

Answer 13

Based on @devinmoore code, a map sorting methods using generics and supporting both ascending and descending ordering.

/**
 * Sort a map by it's keys in ascending order. 
 *  
 * @return new instance of {@link LinkedHashMap} contained sorted entries of supplied map.
 * @author Maxim Veksler
 */
public static <K, V> LinkedHashMap<K, V> sortMapByKey(final Map<K, V> map) {
 return sortMapByKey(map, SortingOrder.ASCENDING);
}

/**
 * Sort a map by it's values in ascending order.
 *  
 * @return new instance of {@link LinkedHashMap} contained sorted entries of supplied map.
 * @author Maxim Veksler
 */
public static <K, V> LinkedHashMap<K, V> sortMapByValue(final Map<K, V> map) {
 return sortMapByValue(map, SortingOrder.ASCENDING);
}

/**
 * Sort a map by it's keys.
 *  
 * @param sortingOrder {@link SortingOrder} enum specifying requested sorting order. 
 * @return new instance of {@link LinkedHashMap} contained sorted entries of supplied map.
 * @author Maxim Veksler
 */
public static <K, V> LinkedHashMap<K, V> sortMapByKey(final Map<K, V> map, final SortingOrder sortingOrder) {
 Comparator<Map.Entry<K, V>> comparator = new Comparator<Entry<K,V>>() {
  public int compare(Entry<K, V> o1, Entry<K, V> o2) {
   return comparableCompare(o1.getKey(), o2.getKey(), sortingOrder);
  }
 };

 return sortMap(map, comparator);
}

/**
 * Sort a map by it's values.
 *  
 * @param sortingOrder {@link SortingOrder} enum specifying requested sorting order. 
 * @return new instance of {@link LinkedHashMap} contained sorted entries of supplied map.
 * @author Maxim Veksler
 */
public static <K, V> LinkedHashMap<K, V> sortMapByValue(final Map<K, V> map, final SortingOrder sortingOrder) {
 Comparator<Map.Entry<K, V>> comparator = new Comparator<Entry<K,V>>() {
  public int compare(Entry<K, V> o1, Entry<K, V> o2) {
   return comparableCompare(o1.getValue(), o2.getValue(), sortingOrder);
  }
 };

 return sortMap(map, comparator);
}

@SuppressWarnings("unchecked")
private static <T> int comparableCompare(T o1, T o2, SortingOrder sortingOrder) {
 int compare = ((Comparable<T>)o1).compareTo(o2);

 switch (sortingOrder) {
 case ASCENDING:
  return compare;
 case DESCENDING:
  return (-1) * compare;
 }

 return 0;
}

/**
 * Sort a map by supplied comparator logic.
 *  
 * @return new instance of {@link LinkedHashMap} contained sorted entries of supplied map.
 * @author Maxim Veksler
 */
public static <K, V> LinkedHashMap<K, V> sortMap(final Map<K, V> map, final Comparator<Map.Entry<K, V>> comparator) {
 // Convert the map into a list of key,value pairs.
 List<Map.Entry<K, V>> mapEntries = new LinkedList<Map.Entry<K, V>>(map.entrySet());

 // Sort the converted list according to supplied comparator.
 Collections.sort(mapEntries, comparator);

 // Build a new ordered map, containing the same entries as the old map.  
 LinkedHashMap<K, V> result = new LinkedHashMap<K, V>(map.size() + (map.size() / 20));
 for(Map.Entry<K, V> entry : mapEntries) {
  // We iterate on the mapEntries list which is sorted by the comparator putting new entries into 
  // the targeted result which is a sorted map. 
  result.put(entry.getKey(), entry.getValue());
 }

 return result;
}

/**
 * Sorting order enum, specifying request result sort behavior.
 * @author Maxim Veksler
 *
 */
public static enum SortingOrder {
 /**
  * Resulting sort will be from smaller to biggest.
  */
 ASCENDING,
 /**
  * Resulting sort will be from biggest to smallest.
  */
 DESCENDING
}

Answer 14

It seems much easier than all of the foregoing. Use a TreeMap as follows:

public class Main {

    public static void main(String[] args) {

        HashMap<String,Double> map = new HashMap<String,Double>();
        ValueComparator bvc =  new ValueComparator(map);
        TreeMap<String,Double> sorted_map = new TreeMap(bvc);

        map.put("A",99.5);
        map.put("B",67.4);
        map.put("C",67.5);
        map.put("D",67.3);

        System.out.println("unsorted map");
        for (String key : map.keySet()) {
            System.out.println("key/value: " + key + "/"+map.get(key));
        }

        sorted_map.putAll(map);

        System.out.println("results");
        for (String key : sorted_map.keySet()) {
            System.out.println("key/value: " + key + "/"+sorted_map.get(key));
        }
    }

}

class ValueComparator implements Comparator {

  Map base;
  public ValueComparator(Map base) {
      this.base = base;
  }

  public int compare(Object a, Object b) {

    if((Double)base.get(a) < (Double)base.get(b)) {
      return 1;
    } else if((Double)base.get(a) == (Double)base.get(b)) {
      return 0;
    } else {
      return -1;
    }
  }
}

Output:

unsorted map
key/value: D/67.3
key/value: A/99.5
key/value: B/67.4
key/value: C/67.5
results
key/value: A/99.5
key/value: C/67.5
key/value: B/67.4
key/value: D/67.3

Answer 15

I've looked at the given answer but a lot of them are more complicated than needed or remove map elements when several keys have same value.

Here is a solution that I think better fit:

public static <K, V extends Comparable<V>> Map<K, V> sortByValues(final Map<K, V> map) {
Comparator<K> valueComparator =  new Comparator<K>() {
    public int compare(K k1, K k2) {
        int compare = map.get(k2).compareTo(map.get(k1));
        if (compare == 0) return 1;
        else return compare;
    }
};
Map<K, V> sortedByValues = new TreeMap<K, V>(valueComparator);
sortedByValues.putAll(map);
return sortedByValues;

}

Note that the map is sorted from the highest value to the lowest.

Answer 16

Here's a 1.5-friendly version you're free to use:

import java.util.*;

public class MapUtil
{
    public static <K, V extends Comparable<? super V>> Map<K, V> 
        sortByValue( Map<K, V> map )
    {
        List<Map.Entry<K, V>> list =
            new LinkedList<Map.Entry<K, V>>( map.entrySet() );
        Collections.sort( list, new Comparator<Map.Entry<K, V>>()
        {
            public int compare( Map.Entry<K, V> o1, Map.Entry<K, V> o2 )
            {
                return (o1.getValue()).compareTo( o2.getValue() );
            }
        } );

        Map<K, V> result = new LinkedHashMap<K, V>();
        for (Map.Entry<K, V> entry : list)
        {
            result.put( entry.getKey(), entry.getValue() );
        }
        return result;
    }
}

And an associated JUnit4 test so you don't have to take my word for it:

import java.util.*;
import org.junit.*;

public class MapUtilTest
{
    @Test
    public void testSortByValue()
    {
        Random random = new Random(System.currentTimeMillis());
        Map<String, Integer> testMap = new HashMap<String, Integer>(1000);
        for(int i = 0 ; i < 1000 ; ++i) {
            testMap.put( "SomeString" + random.nextInt(), random.nextInt());
        }

        testMap = MapUtil.sortByValue( testMap );
        Assert.assertEquals( 1000, testMap.size() );

        Integer previous = null;
        for(Map.Entry<String, Integer> entry : testMap.entrySet()) {
            Assert.assertNotNull( entry.getValue() );
            if (previous != null) {
                Assert.assertTrue( entry.getValue() >= previous );
            }
            previous = entry.getValue();
        }
    }

}

Answer 17

This is just too complicated. Maps were not supposed to do such job as sorting them by Value. The easiest way is to create your own Class so it fits your requirement.

In example lower you are supposed to add TreeMap a comparator at place where * is. But by java API it gives comparator only keys, not values. All of examples stated here is based on 2 Maps. One Hash and one new Tree. Which is odd.

The example:

Map<Driver driver, Float time> map = new TreeMap<Driver driver, Float time>(*);

so change map into set this way:

ResultComparator rc = new ResultComparator();
Set<Results> set = new TreeSet<Results>(rc);

you will create class Result

public class Results {
    private Driver driver;
    private Float time;

    public Results(Driver driver, Float time) {
        this.driver = driver;
        this.time = time;
    }

    public Float getTime() {
        return time;
    }

    public void setTime(Float time) {
        this.time = time;
    }

    public Driver getDriver() {
        return driver;
    }

    public void setDriver (Driver driver) {
        this.driver = driver;
    }
}

and the Comparator class:

public class ResultsComparator implements Comparator<Results> {

    public int compare(Results t, Results t1) {

        if (t.getTime() < t1.getTime()) {
            return 1;
        } else if (t.getTime() == t1.getTime()) {
            return 0;
        } else {
            return -1;
        }

    }
}

this way you can easily add more dependencies.

And as the last point I'll add simple iterator:

Iterator it = set.iterator();
    while (it.hasNext()) {
        Results r = (Results)it.next();
        System.out.println( r.getDriver().toString
//or whatever that is related to Driver class -getName() getSurname()
                + " "
                + r.getTime()
                );
    }

Answer 18

this seems like a common problem that may have been solved by databases - generally a table has a primary key and you can specify sorts on different columns. Is there no comparable java structure?

Answer 19

I found this answer by CliffsNote also which I found easier to understand than most of the answers here. It's similar to Anthony's answer but I couldn't get Anthony's code to work. (I'm still a Novice with Generics and Collections).

I hope you find it useful too; it'sat the end of this thread: link text

Answer 20

3 1-line answers...

I would use google collections to do this - if your values are Comparable then you can use

Ordering.natural().onResultOf(Functions.forMap(map))

Which will create a function (object) for the map [that takes any of the keys as input, returning the respective value], and then apply natural (comparable) ordering to them [the values].

If they're not comparable, then you'll need to do something along the lines of

Ordering.from(comparator).onResultOf(Functions.forMap(map)) 

These may be applied to a TreeMap (as Ordering extends Comparator), or a LinkedHashMap after some sorting

NB: If you are going to use a TreeMap, remember that if a comparison == 0, then the item is already in the list (which will happen if you have multiple values that compare the same). To alleviate this, you could add your key to the comparator like so (presuming that your keys and values are Comparable):

Ordering.natural().onResultOf(Functions.forMap(map)).compound(Ordering.natural())

= Apply natural ordering to the value mapped by the key, and compound that with the natural ordering of the key

Note that this will still not work if your keys compare to 0, but this should be sufficient for most comparable items (as hashCode, equals and compareTo are often in sync...)

See Ordering.onResultOf() and Functions.forMap()