Sort a Map<Key, Value> by values

1 436

569

I am relatively new to Java, and often find that I need to sort a Map<Key, Value> 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?

Abe

Posted 2008-09-20T21:03:23.403

Reputation: 1 283

17A map is not meant to be sorted, but accessed fast. Object equal values break the constraint of the map. Use the entry set, like List&lt;Map.Entry&lt;...&gt;&gt; list =new LinkedList(map.entrySet()) and Collections.sort .... it that way. – Hannes – 2014-02-09T17:34:42.997

A case where this might arise when we try to make use of a Counter in Java (Map<Object, Integer>). Sorting by number of occurrences would then be a common operation. A language like Python has a built in Counter data structure. For an alternate way of implementation in Java, here is an example

– demongolem – 2017-12-21T20:03:58.910

2There are plenty of use cases for sorted maps, that's why you have TreeMap and ConcurrentSkipListMap in jdk. – alobodzk – 2018-04-22T19:10:45.333

Answers

808

Here's a generic-friendly version:

public class MapUtil {
    public static <K, V extends Comparable<? super V>> Map<K, V> sortByValue(Map<K, V> map) {
        List<Entry<K, V>> list = new ArrayList<>(map.entrySet());
        list.sort(Entry.comparingByValue());

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

        return result;
    }
}

Carter Page

Posted 2008-09-20T21:03:23.403

Reputation: 1 940

why use Collections.sort if there is Arrays.sort? see my answer for more details – ciamej – 2012-05-30T00:50:32.873

This saved me a TON of time! The test case is great too. :) Is there a reason why you used a LinkedHashMap as opposed to a regular HashMap? – John Mark – 2012-06-19T16:06:04.317

7Glad this helps. John, the LinkedHashMap is important to the solution as it provides predictable iteration order. – Carter Page – 2012-07-01T12:46:16.207

Note this solution would not work reliably on a map which contains mutable values e.g. AtomicLong. I wanted to use it for a performance statistics collector in our application. So first needed to snapshot all the AtomicLong values and then sort a map with the snapshots. – buzz3791 – 2013-04-25T15:02:29.750

3@buzz3791 True. That's going to be the case in any sorting algorithm. Change the value of nodes in a structure during a sort creates unpredictable (and nearly always bad) results. – Carter Page – 2013-04-25T18:55:17.233

DOESN'T WORK, I tried your code in android, it sorts the hashmap by value but after that when it iterates to fill the result Map it gets sorted again by key – Shaegorath – 2014-11-01T07:53:22.923

3@Sheagorath I tried it in Android and it works too. It is not a platform specific problem, considering you are using the Java 6 version. Have you implemented Comparable correctly in your value object? – saiyancoder – 2014-12-08T01:12:29.613

This solution did not work for me. I am using BigDecimal as my value object and Pair<K, V> for the key (from Apache Commons). The values are not sorted when I access the map after sorting. – anton1980 – 2015-02-02T22:29:54.923

5Shouldn't the Java 8 version use forEachOrdered instead of forEach, since the docs of forEach states: "The behavior of this operation is explicitly nondeterministic."? – rob – 2015-06-27T14:06:30.910

1totally ripped this, but credited @CarterPage in the comments (it'll be in an open source project anyway). thanks so much. – Nathan Beach – 2015-09-02T03:07:48.840

Any specific reason for using LinkedList and LinkedHashMap? – i_am_zero – 2015-09-06T11:55:34.630

@akhil_mittal LinkedList should be replaced by ArrayList but LinkedHashMap is necessary because it preserves insertion order. – Solomonoff's Secret – 2015-09-30T14:53:00.343

@trillions Could you tell me what change you made to reverse the order? Thanks. – cirko – 2015-11-13T12:40:40.620

+1, but the junit test is not the best, based on randomness it could fail or succeed without changes in the code – Ferrybig – 2015-11-17T11:26:30.937

The Java 8 version should use the collectors approach... Look at Collectors.toMap. – Alexis C. – 2015-12-20T21:25:28.653

How are identical values sorted with code? – Dake – 2016-08-26T11:02:03.850

The Java 8 version only compiles in my Eclipse environment if I replace LinkedHashMap::new by LinkedHashMap&lt;K, V&gt;::new – basZero – 2016-10-04T15:33:15.127

I think LinkedList should be replaced with ArrayList as we just want to itertate over list . – emilly – 2016-11-28T14:50:34.453

You might want to change for(int i = 0 ; i &lt; 1000 ; ++i) { by while (testMap.size() &lt; 1000) { in the unit test because same key might be generated by random. This might fails the testMap.size() assertion. – R. Oosterholt – 2017-05-05T08:20:59.900

Not loving the test that uses different data every time new Random(System.currentTimeMillis()) – weston – 2017-05-15T16:35:16.633

I removed all solutions except the original one. The others should get their own answers instead. – Lii – 2018-03-10T22:14:30.203

407

Important note:

This code can break in multiple ways. If you intend to use the code provided, be sure to read the comments as well to be aware of the implications. For example, values can no longer be retrieved by their key. (get always returns null.)


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

public class Testing {
    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<String, Double>(bvc);

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

        System.out.println("unsorted map: " + map);
        sorted_map.putAll(map);
        System.out.println("results: " + sorted_map);
    }
}

class ValueComparator implements Comparator<String> {
    Map<String, Double> base;

    public ValueComparator(Map<String, Double> base) {
        this.base = base;
    }

    // Note: this comparator imposes orderings that are inconsistent with
    // equals.
    public int compare(String a, String b) {
        if (base.get(a) >= base.get(b)) {
            return -1;
        } else {
            return 1;
        } // returning 0 would merge keys
    }
}

Output:

unsorted map: {D=67.3, A=99.5, B=67.4, C=67.4}
results: {D=67.3, B=67.4, C=67.4, A=99.5}

user157196

Posted 2008-09-20T21:03:23.403

Reputation: 1 000

84Just in case it's not clear to people: this solution will probably not do what you want if you have multiple keys mapping to the same value -- only one of those keys will appear in the sorted result. – Maxy-B – 2011-11-24T04:37:55.447

4It's practically a bug ... I can image a very few use cases for omitting one of 2 map entries that have the same value... – lisak – 2012-05-23T14:37:58.183

61

Louis Wasserman (yes, one of the Google Guava guys), actually dislikes this answer quite a bit: "It breaks in several really confusing ways if you even look at it funny. If the backing map changes, it will break. If multiple keys map to the same value, it will break. If you call get on a key that isn't in the backing map, it will break. If you do anything whatsoever that would cause a lookup to happen on a key that isn't in the map -- a Map.equals call, containsKey, anything -- it will break with really weird stack traces." https://plus.google.com/102216152814616302326/posts/bEQLDK712MJ

– haylem – 2012-07-03T21:19:30.537

2If ValueComparator#compare() does not return 0 for equals (see edited answer) @Maxy-B 's comment about missing keys no longer applies – Tomasz – 2012-09-06T17:14:42.940

8

I regret using this approach. Now I reproduced in my code all the bugs described here in comments. My mistake was not reading the comments. This http://stackoverflow.com/a/2581754/1537800 works just fine.

– Volodymyr Krupach – 2013-04-08T15:58:34.740

3var sorted_map = map.OrderByDescending(entry =&gt; entry.Value); (in C#). Sorry, I couldn't resist ;) +1, though – Konrad Morawski – 2013-09-11T22:05:49.860

1I think adding if(a.equals(b)) return 0; in compare will make it perfect. As it will eliminate duplicate keys + will make normal traversal possible. Let me know if I am missing something, I am going to give it a chance in production...:P – Mohammad – 2014-03-11T09:05:41.053

16

Not any more (http://stackoverflow.com/questions/109383/how-to-sort-a-mapkey-value-on-the-values-in-java/3420912#3420912). Also, why was there a cast to Double? Shouldn't it just be return ((Comparable)base.get(a).compareTo(((Comparable)base.get(b)))?

– Stephen – 2010-08-11T21:50:54.957

12@Stephen: No. In this case all keys equal by value are dropped (difference between equals and comparion by reference). Additionally: Even this code has problems with the following sequence
map.put("A","1d");map.put("B","1d");map.put("C",67d);map.put("D",99.5d);
– steffen – 2010-08-20T07:00:23.617

40The comparator used for the treemap is inconsistent with equals (see the sortMap javadox). This means retireving items from the tree map will not work. sorted_map.get("A") will return null. That means this use of treemap is broken. – mR_fr0g – 2010-12-01T14:36:50.983

1Can't we just use a TreeMap instead? Did I miss anything? – Aniket Kapse – 2015-04-13T12:54:12.937

@AniketKapse, you can use only a tree map constructed after the map is populated (There is no need ValueComparator). Then you can iterate through the map following an order. – Victor – 2015-08-22T15:57:07.810

@Override public int compare(Character o1, Character o2) { if (charToTimes.get(o1) == null || charToTimes.get(o2) == null) { return -o1.compareTo(o2); } int result = -charToTimes.get(o1).compareTo(charToTimes.get(o2)); if (result != 0) { return result; } return -o1.compareTo(o2);} – Bruce Zu – 2016-01-14T19:28:07.600

Don'y you compare objects and not primitive values...thus don't you compare memory position instead real values ? – hephestos – 2018-10-09T08:44:43.223

@mR_fr0g That is true only if the base map is altered. As long as it is not modified the natural order of the keys (according to the comparator) will follow the natural order of the values. – aalku – 2011-11-05T16:16:00.727

239

Java 8 offers a new answer: convert the entries into a stream, and use the comparator combinators from Map.Entry:

Stream<Map.Entry<K,V>> sorted =
    map.entrySet().stream()
       .sorted(Map.Entry.comparingByValue());

This will let you consume the entries sorted in ascending order of value. If you want descending value, simply reverse the comparator:

Stream<Map.Entry<K,V>> sorted =
    map.entrySet().stream()
       .sorted(Collections.reverseOrder(Map.Entry.comparingByValue()));

If the values are not comparable, you can pass an explicit comparator:

Stream<Map.Entry<K,V>> sorted =
    map.entrySet().stream()
       .sorted(Map.Entry.comparingByValue(comparator));

You can then proceed to use other stream operations to consume the data. For example, if you want the top 10 in a new map:

Map<K,V> topTen =
    map.entrySet().stream()
       .sorted(Map.Entry.comparingByValue(Comparator.reverseOrder()))
       .limit(10)
       .collect(Collectors.toMap(
          Map.Entry::getKey, Map.Entry::getValue, (e1, e2) -> e1, LinkedHashMap::new));

Or print to System.out:

map.entrySet().stream()
   .sorted(Map.Entry.comparingByValue())
   .forEach(System.out::println);

Brian Goetz

Posted 2008-09-20T21:03:23.403

Reputation: 55 659

Nice, but what about the use of parallelStream() in this case ? – Benj – 2014-12-09T18:21:54.987

8It will work in parallel, however, you may find that the cost of merging maps to combine the partial results is too expensive and the parallel version may not perform as well as you'd hope. But it does work and produce the correct answer. – Brian Goetz – 2014-12-09T18:37:25.633

Thanks for your useful advice. It was exactly what I was wondering, though it depends on what type of key you use and so many parameters... The important thing is "it does work and produce the correct answer". – Benj – 2014-12-10T19:30:49.693

How can I sort according to the values being Lists with different sizes? I want to sort by descending list size. – Pete – 2015-04-28T15:04:26.807

Once sorted how would we go about extracting back the map from the Stream<>? – CyberMew – 2015-10-06T09:18:13.417

2don' t you have to use compareByValue in the top10 example? – Leo – 2016-08-19T23:34:01.403

How do I copy the sorted values of the map in a list? – chandresh – 2017-07-04T06:25:20.137

The part for making up a top ten is incorrect, you need to add two more parameters as posted here: https://stackoverflow.com/a/19671853/5655767

– Steven – 2017-08-21T11:19:11.897

Collectors.toMap here would default to plain HashMap, which would discard the ordering. Refer to the top answer for properly collecting to LinkedHashMap. – Vadzim – 2017-11-21T00:28:45.337

@Vadzim The point was to capture the top 10, not to preserve the order. – shmosel – 2017-11-21T00:47:40.433

@shmosel, the order makes sense even for top 10 ;) – Vadzim – 2017-11-21T01:50:34.650

@Vadzim Not sure what you're trying to say. – shmosel – 2017-11-21T01:51:48.870

208

Three 1-line answers...

I would use Google Collections Guava to do this - if your values are Comparable then you can use

valueComparator = 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

valueComparator = 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):

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

Implementation

So now that we've got a comparator that does what we want, we need to get a result from it.

map = ImmutableSortedMap.copyOf(myOriginalMap, valueComparator);

Now this will most likely work work, but:

  1. needs to be done given a complete finished map
  2. Don't try the comparators above on a TreeMap; there's no point trying to compare an inserted key when it doesn't have a value until after the put, i.e., it will break really fast

Point 1 is a bit of a deal-breaker for me; google collections is incredibly lazy (which is good: you can do pretty much every operation in an instant; the real work is done when you start using the result), and this requires copying a whole map!

"Full" answer/Live sorted map by values

Don't worry though; if you were obsessed enough with having a "live" map sorted in this manner, you could solve not one but both(!) of the above issues with something crazy like the following:

Note: This has changed significantly in June 2012 - the previous code could never work: an internal HashMap is required to lookup the values without creating an infinite loop between the TreeMap.get() -> compare() and compare() -> get()

import static org.junit.Assert.assertEquals;

import java.util.HashMap;
import java.util.Map;
import java.util.TreeMap;

import com.google.common.base.Functions;
import com.google.common.collect.Ordering;

class ValueComparableMap<K extends Comparable<K>,V> extends TreeMap<K,V> {
    //A map for doing lookups on the keys for comparison so we don't get infinite loops
    private final Map<K, V> valueMap;

    ValueComparableMap(final Ordering<? super V> partialValueOrdering) {
        this(partialValueOrdering, new HashMap<K,V>());
    }

    private ValueComparableMap(Ordering<? super V> partialValueOrdering,
            HashMap<K, V> valueMap) {
        super(partialValueOrdering //Apply the value ordering
                .onResultOf(Functions.forMap(valueMap)) //On the result of getting the value for the key from the map
                .compound(Ordering.natural())); //as well as ensuring that the keys don't get clobbered
        this.valueMap = valueMap;
    }

    public V put(K k, V v) {
        if (valueMap.containsKey(k)){
            //remove the key in the sorted set before adding the key again
            remove(k);
        }
        valueMap.put(k,v); //To get "real" unsorted values for the comparator
        return super.put(k, v); //Put it in value order
    }

    public static void main(String[] args){
        TreeMap<String, Integer> map = new ValueComparableMap<String, Integer>(Ordering.natural());
        map.put("a", 5);
        map.put("b", 1);
        map.put("c", 3);
        assertEquals("b",map.firstKey());
        assertEquals("a",map.lastKey());
        map.put("d",0);
        assertEquals("d",map.firstKey());
        //ensure it's still a map (by overwriting a key, but with a new value) 
        map.put("d", 2);
        assertEquals("b", map.firstKey());
        //Ensure multiple values do not clobber keys
        map.put("e", 2);
        assertEquals(5, map.size());
        assertEquals(2, (int) map.get("e"));
        assertEquals(2, (int) map.get("d"));
    }
 }

When we put, we ensure that the hash map has the value for the comparator, and then put to the TreeSet for sorting. But before that we check the hash map to see that the key is not actually a duplicate. Also, the comparator that we create will also include the key so that duplicate values don't delete the non-duplicate keys (due to == comparison). These 2 items are vital for ensuring the map contract is kept; if you think you don't want that, then you're almost at the point of reversing the map entirely (to Map<V,K>).

The constructor would need to be called as

 new ValueComparableMap(Ordering.natural());
 //or
 new ValueComparableMap(Ordering.from(comparator));

Stephen

Posted 2008-09-20T21:03:23.403

Reputation: 13 835

ImmutableSortedMap.copyOf throws IllegalArgumentException if there are duplicate values in the original map. – lbalazscs – 2013-04-30T09:39:17.313

@Ibalazscs Yes it will - You should be able to use ImmutableSetMultiMap or ImmutableListMultiMap to contain the collection of duplicate variables. – Stephen – 2013-05-01T00:31:18.997

1Thanks for this, I used your solution in one project. I think there's a problem in put though: to behave like a map it needs to return the value previously associated with the key, if it exists, but like this it will never do. The solution I used is to return the removed value if it exists. – alex – 2013-08-21T09:22:37.400

Currently, class ValueComparableMap&lt;K extends Comparable&lt;K&gt;,V&gt; extends TreeMap&lt;K,V&gt;. Why K extends Comparable&lt;K&gt;? What about just K? Requiring the key type K to be a Comparable seems overly restrictive. – Abdull – 2014-04-22T09:41:49.153

@Abdull, you probably want to read the paragraph under the code a few times. (I've just re-read it and have had a little trouble a year later ;)). We have to ensure the keys are not clobbered (otherwise we could remove items with the same values). The easiest way to do this is to make the key comparable. So yes, it is restrictive, but you'd need to have 2 comparators otherwise (which is certainly possible, but outside the scope of the question). – Stephen – 2014-04-22T18:07:20.947

Hi @Stephen , can you give an example how to use Ordering ? I look into Ordering's source code , and totally cannot figure out what .natural().onResultOf(...) returns! The source code is "public <F> Ordering<F> onResultOf" , I even don't know how it compiles ! Most important , how to use "<F> Ordering<F>" to sort a map ? Is it a comparator or something ? Thanks. – smallufo – 2010-11-10T10:58:52.470

Ordering is simply a rich Comparator. I've tried commenting each example (the italics underneath each one). "natural" indicates that the objects are Comparable; it's like apache common's ComparableComparator. onResultOf applies a function to the item being compared. So if you had a function that added 1 to an integer, then natural().onResultOf(add1Function).compare(1,2) would end up doing 2.compareTo(3) – Stephen – 2010-11-11T11:44:54.983

Couldn't this simply work without the valueMap by using super.put() in the first place? Just thinking, haven't tried yet... – Christian Hujer – 2015-03-05T22:47:36.283

Object valueComparator = Ordering.natural().onResultOf(Functions.forMap(map)).compound(Ordering.natural()); results in an error, Cannot resolve .compound(Ordering<Comparable>) – Ryan The Leach – 2015-06-10T02:39:53.827

Thanks for the solution, I had to add:@Override public boolean containsKey(Object key) { return valueMap.containsKey(key); } to overcome an exception thrown when calling containsKey. – has981 – 2016-06-05T07:56:43.893

175

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

private static <K, V> Map<K, V> sortByValue(Map<K, V> map) {
    List<Entry<K, V>> list = new LinkedList<>(map.entrySet());
    Collections.sort(list, new Comparator<Object>() {
        @SuppressWarnings("unchecked")
        public int compare(Object o1, Object o2) {
            return ((Comparable<V>) ((Map.Entry<K, V>) (o1)).getValue()).compareTo(((Map.Entry<K, V>) (o2)).getValue());
        }
    });

    Map<K, V> result = new LinkedHashMap<>();
    for (Iterator<Entry<K, V>> it = list.iterator(); it.hasNext();) {
        Map.Entry<K, V> entry = (Map.Entry<K, V>) it.next();
        result.put(entry.getKey(), entry.getValue());
    }

    return result;
}

devinmoore

Posted 2008-09-20T21:03:23.403

Reputation: 2 487

why use Collections.sort if there is Arrays.sort? see my answer for more details – ciamej – 2012-05-30T00:49:53.530

@DimitrisAndreou, why is it bad to sort a linkedlist? – kaspersky – 2012-11-28T11:15:35.287

3

@gg.kaspersky I'm not saying "it's bad to sort a LinkedList", but that LinkedList itself is a bad choice here, regardless of sorting.

Much better to use an ArrayList, and for extra points, size it at exactly map.size().

Also see http://code.google.com/p/memory-measurer/wiki/ElementCostInDataStructures

average cost per element in ArrayList: 5 bytes average cost per element in LinkedList: 24 bytes.

For an exactly sized ArrayList, the average cost would be 4 bytes. That is, LinkedList takes SIX times the amount of memory that ArrayList needs. It's just bloat

– Dimitris Andreou – 2012-11-29T19:29:47.590

16The list to be sorted is "new LinkedList"?? Gee. Thankfully Collections.sort() dump the list to an array first, to avoid precisely this kind of error (but still, dumping an ArrayList to an array should be faster than doing the same for a LinkedList). – Dimitris Andreou – 2010-04-08T13:13:35.040

Shows an error: The method sort(List<T>, Comparator<? super T>) in the type Collections is not applicable for the arguments (List, new Comparator(){}) – Rishi Dua – 2014-06-26T03:33:50.347

^Sorry about that. I didn't import java.util.comparator – Rishi Dua – 2014-06-26T03:34:31.617

2using above values has been sorted in ascending order. How to sort in descending ? – ram – 2015-04-16T13:09:58.467

cannot convert from Iterator to TernaryTree.Iterator – lisak – 2011-06-03T16:31:15.290

1Replace o1 and o2 to sort descending. – Soheil – 2017-06-05T20:14:11.253

35

With Java 8, you can use the streams api to do it in a significantly less verbose way:

Map<K, V> sortedMap = map.entrySet().stream()
                         .sorted(Entry.comparingByValue())
                         .collect(Collectors.toMap(Entry::getKey, Entry::getValue, (e1, e2) -> e1, LinkedHashMap::new));

assylias

Posted 2008-09-20T21:03:23.403

Reputation: 242 241

How to sort it in a reverse order? – Vlad Holubiev – 2014-06-01T19:18:17.407

@VladGolubev comparing(Entry::getValue).reversed() – assylias – 2014-06-01T19:33:21.130

6found a solution - Collections.reverseOrder(comparing(Entry::getValue)) – Vlad Holubiev – 2014-08-09T08:26:56.137

look at this example code – Vlad Holubiev – 2014-08-09T08:49:57.443

1I think I see a typo there -- shouldn't the " toMap " be called as " Collectors.toMap() " ? – Jake Stokes – 2017-10-02T14:31:13.013

1@JakeStokes Or use a static import :-) – assylias – 2017-10-03T05:59:20.360

1A better way to sort by entry value in reverse order is: Entry.comparingByValue(Comparator.reverseOrder()) – Gediminas Rimsa – 2018-11-24T09:20:39.517

30

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

volley

Posted 2008-09-20T21:03:23.403

Reputation: 5 704

The second version can be more concise if you return List<Map.Entry<K,V>> This also makes it easier to iterate and get both the keys and the values without having to do a lot of extra gets to the map. This is all assuming you are ok with this code being thread-unsafe. If the backing map or sorted list are shared in a multithreaded environment, all bets are off. – Mike Miller – 2011-09-20T21:00:55.093

25

The commons-collections library contains a solution called TreeBidiMap. Or, you could have a look at the Google Collections API. It has TreeMultimap which you could use.

And if you don't want to use these framework... they come with source code.

p3t0r

Posted 2008-09-20T21:03:23.403

Reputation: 1 663

You don't have to use the commons-collection. Java comes with its own java.util.TreeMap. – yoliho – 2008-09-21T04:23:04.080

2yes, but TreeMap is far less flexible when sorting on the value part of the mapentries. – p3t0r – 2008-09-21T06:18:20.450

8The trouble with BidiMap is that it adds a 1:1 relation constraint between keys and values in order to make the relation invertible (ie. both keys and values need to be unique). This means you can't use this to store something like a word count object since many words will have the same count. – Doug – 2010-07-23T19:49:15.660

23

I've looked at the given answers, 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 fits better:

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.

Anthony

Posted 2008-09-20T21:03:23.403

Reputation: 923

This looks a clean solution to me , except the fact that @ErelSegalHalevi pointed out , checking whether the values exist in the Map will not be possible as you specified the comparator. map.put("1", "One"); map.put("2", "Two"); map.put("3", "Three"); map.put("4", "Four"); map.put("5", "Five"); map.containsKey("1") will always return false , if you return new object in the function sortByValues() like return new TreeMap<K, V>(sortedByValues); solves the problem . Thanks Abhi – abhi – 2013-05-14T08:14:40.347

pretty much the same as user157196's and Carter Page's answer. Carter Page's contains the LinkedHashMap fix – Kirby – 2014-04-22T17:37:16.437

4th line of the solution should be int compare = map.get(k1).compareTo(map.get(k2)); if you need ascending order – cosmolev – 2014-07-22T08:20:05.080

6PROBLEM: if you want to use the returned map later, for example to check if it contains a certain element, you will always get false, because of your custom comparator!

A possible solution: replace the last line with:

 return new LinkedHashMap&lt;K,V&gt;(sortedByValues);
 – Erel Segal-Halevi  – 2011-10-02T15:58:30.847

17

To accomplish this with the new features in Java 8:

import static java.util.Map.Entry.comparingByValue;
import static java.util.stream.Collectors.toList;

<K, V> List<Entry<K, V>> sort(Map<K, V> map, Comparator<? super V> comparator) {
    return map.entrySet().stream().sorted(comparingByValue(comparator)).collect(toList());
}

The entries are ordered by their values using the given comparator. Alternatively, if your values are mutually comparable, no explicit comparator is needed:

<K, V extends Comparable<? super V>> List<Entry<K, V>> sort(Map<K, V> map) {
    return map.entrySet().stream().sorted(comparingByValue()).collect(toList());
}

The returned list is a snapshot of the given map at the time this method is called, so neither will reflect subsequent changes to the other. For a live iterable view of the map:

<K, V extends Comparable<? super V>> Iterable<Entry<K, V>> sort(Map<K, V> map) {
    return () -> map.entrySet().stream().sorted(comparingByValue()).iterator();
}

The returned iterable creates a fresh snapshot of the given map each time it's iterated, so barring concurrent modification, it will always reflect the current state of the map.

gdejohn

Posted 2008-09-20T21:03:23.403

Reputation: 5 227

This returns a List of Entries rather than a map sorted by value. Other version that returns a map: http://stackoverflow.com/a/22132422/829571

– assylias – 2014-03-03T17:26:05.857

14

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.

Lyudmil

Posted 2008-09-20T21:03:23.403

Reputation: 730

This method is much easier and more intuitive than creating a Map<V, List<K>> object with pretty much the same effect. The values are not really supposed to be keys in a Map object, what you're really looking for is a list in this situation, IMHO. – Jeff Wu – 2011-12-30T01:49:48.027

This solution doesn't work with lots of values, it screwed with my counts (the value associated with each key) – Sam Levin – 2012-09-15T16:17:33.390

1That's strange. Could you elaborate? What was your output and what was the output you expected? – Lyudmil – 2012-09-29T10:24:53.577

14

Create customized comparator and use it while creating new TreeMap object.

class MyComparator implements Comparator<Object> {

    Map<String, Integer> map;

    public MyComparator(Map<String, Integer> map) {
        this.map = map;
    }

    public int compare(Object o1, Object o2) {

        if (map.get(o2) == map.get(o1))
            return 1;
        else
            return ((Integer) map.get(o2)).compareTo((Integer)     
                                                            map.get(o1));

    }
}

Use the below code in your main func

    Map<String, Integer> lMap = new HashMap<String, Integer>();
    lMap.put("A", 35);
    lMap.put("B", 75);
    lMap.put("C", 50);
    lMap.put("D", 50);

    MyComparator comparator = new MyComparator(lMap);

    Map<String, Integer> newMap = new TreeMap<String, Integer>(comparator);
    newMap.putAll(lMap);
    System.out.println(newMap);

Output:

{B=75, D=50, C=50, A=35}

Sujan Reddy A

Posted 2008-09-20T21:03:23.403

Reputation: 77

1This works for duplicate values too!!! – Sujan Reddy A – 2013-02-10T06:12:12.253

11

Use a generic comparator such as :

final class MapValueComparator<K,V extends Comparable<V>> implements Comparator<K> {

    private Map<K,V> map;

    private MapValueComparator() {
        super();
    }

    public MapValueComparator(Map<K,V> map) {
        this();
        this.map = map;
    }

    public int compare(K o1, K o2) {
        return map.get(o1).compareTo(map.get(o2));
    }
}

RoyalBigorno

Posted 2008-09-20T21:03:23.403

Reputation: 11

11

The answer voted for the most does not work when you have 2 items that equals. the TreeMap leaves equal values out.

the exmaple: unsorted map

key/value: D/67.3
key/value: A/99.5
key/value: B/67.4
key/value: C/67.5
key/value: E/99.5

results

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

So leaves out E!!

For me it worked fine to adjust the comparator, if it equals do not return 0 but -1.

in the example:

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 -1;
} else {
  return -1;
}

} }

now it returns:

unsorted map:

key/value: D/67.3
key/value: A/99.5
key/value: B/67.4
key/value: C/67.5
key/value: E/99.5

results:

key/value: A/99.5
key/value: E/99.5
key/value: C/67.5
key/value: B/67.4
key/value: D/67.3

as a response to Aliens (2011 nov. 22): I Am using this solution for a map of Integer Id's and names, but the idea is the same, so might be the code above is not correct (I will write it in a test and give you the correct code), this is the code for a Map sorting, based on the solution above:

package nl.iamit.util;

import java.util.Comparator;
import java.util.Map;

public class Comparators {


    public static class MapIntegerStringComparator implements Comparator {

        Map<Integer, String> base;

        public MapIntegerStringComparator(Map<Integer, String> base) {
            this.base = base;
        }

        public int compare(Object a, Object b) {

            int compare = ((String) base.get(a))
                    .compareTo((String) base.get(b));
            if (compare == 0) {
                return -1;
            }
            return compare;
        }
    }


}

and this is the test class (I just tested it, and this works for the Integer, String Map:

package test.nl.iamit.util;

import java.util.HashMap;
import java.util.TreeMap;
import nl.iamit.util.Comparators;
import org.junit.Test;
import static org.junit.Assert.assertArrayEquals;

public class TestComparators {


    @Test
    public void testMapIntegerStringComparator(){
        HashMap<Integer, String> unSoretedMap = new HashMap<Integer, String>();
        Comparators.MapIntegerStringComparator bvc = new Comparators.MapIntegerStringComparator(
                unSoretedMap);
        TreeMap<Integer, String> sorted_map = new TreeMap<Integer, String>(bvc);
        //the testdata:
        unSoretedMap.put(new Integer(1), "E");
        unSoretedMap.put(new Integer(2), "A");
        unSoretedMap.put(new Integer(3), "E");
        unSoretedMap.put(new Integer(4), "B");
        unSoretedMap.put(new Integer(5), "F");

        sorted_map.putAll(unSoretedMap);

        Object[] targetKeys={new Integer(2),new Integer(4),new Integer(3),new Integer(1),new Integer(5) };
        Object[] currecntKeys=sorted_map.keySet().toArray();

        assertArrayEquals(targetKeys,currecntKeys);
    }
}

here is the code for the Comparator of a Map:

public static class MapStringDoubleComparator implements Comparator {

    Map<String, Double> base;

    public MapStringDoubleComparator(Map<String, Double> base) {
        this.base = base;
    }

    //note if you want decending in stead of ascending, turn around 1 and -1
    public int compare(Object a, Object b) {
        if ((Double) base.get(a) == (Double) base.get(b)) {
            return 0;
        } else if((Double) base.get(a) < (Double) base.get(b)) {
            return -1;
        }else{
            return 1;
        }
    }
}

and this is the testcase for this:

@Test
public void testMapStringDoubleComparator(){
    HashMap<String, Double> unSoretedMap = new HashMap<String, Double>();
    Comparators.MapStringDoubleComparator bvc = new Comparators.MapStringDoubleComparator(
            unSoretedMap);
    TreeMap<String, Double> sorted_map = new TreeMap<String, Double>(bvc);
    //the testdata:
    unSoretedMap.put("D",new Double(67.3));
    unSoretedMap.put("A",new Double(99.5));
    unSoretedMap.put("B",new Double(67.4));
    unSoretedMap.put("C",new Double(67.5));
    unSoretedMap.put("E",new Double(99.5));

    sorted_map.putAll(unSoretedMap);

    Object[] targetKeys={"D","B","C","E","A"};
    Object[] currecntKeys=sorted_map.keySet().toArray();

    assertArrayEquals(targetKeys,currecntKeys);
}

of cource you can make this a lot more generic, but I just needed it for 1 case (the Map)

michel.iamit

Posted 2008-09-20T21:03:23.403

Reputation: 3 779

1It does not work for me. I get all values as null. – Aliens – 2011-11-22T00:42:43.810

you were right, there was some error in the code I gave at first! i Hope my recent edit will help you. – michel.iamit – 2011-11-23T13:12:40.023

9

Instead of using Collections.sort as some do I'd suggest using Arrays.sort. Actually what Collections.sort does is something like this:

public static <T extends Comparable<? super T>> void sort(List<T> list) {
    Object[] a = list.toArray();
    Arrays.sort(a);
    ListIterator<T> i = list.listIterator();
    for (int j=0; j<a.length; j++) {
        i.next();
        i.set((T)a[j]);
    }
}

It just calls toArray on the list and then uses Arrays.sort. This way all the map entries will be copied three times: once from the map to the temporary list (be it a LinkedList or ArrayList), then to the temporary array and finally to the new map.

My solution ommits this one step as it does not create unnecessary LinkedList. Here is the code, generic-friendly and performance-optimal:

public static <K, V extends Comparable<? super V>> Map<K, V> sortByValue(Map<K, V> map) 
{
    @SuppressWarnings("unchecked")
    Map.Entry<K,V>[] array = map.entrySet().toArray(new Map.Entry[map.size()]);

    Arrays.sort(array, new Comparator<Map.Entry<K, V>>() 
    {
        public int compare(Map.Entry<K, V> e1, Map.Entry<K, V> e2) 
        {
            return e1.getValue().compareTo(e2.getValue());
        }
    });

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

    return result;
}

ciamej

Posted 2008-09-20T21:03:23.403

Reputation: 4 617

8

This is a variation of Anthony's answer, which doesn't work if there are duplicate values:

public static <K, V extends Comparable<V>> Map<K, V> sortMapByValues(final Map<K, V> map) {
    Comparator<K> valueComparator =  new Comparator<K>() {
        public int compare(K k1, K k2) {
            final V v1 = map.get(k1);
            final V v2 = map.get(k2);

            /* Not sure how to handle nulls ... */
            if (v1 == null) {
                return (v2 == null) ? 0 : 1;
            }

            int compare = v2.compareTo(v1);
            if (compare != 0)
            {
                return compare;
            }
            else
            {
                Integer h1 = k1.hashCode();
                Integer h2 = k2.hashCode();
                return h2.compareTo(h1);
            }
        }
    };
    Map<K, V> sortedByValues = new TreeMap<K, V>(valueComparator);
    sortedByValues.putAll(map);
    return sortedByValues;
}

Note that it's rather up in the air how to handle nulls.

One important advantage of this approach is that it actually returns a Map, unlike some of the other solutions offered here.

Roger

Posted 2008-09-20T21:03:23.403

Reputation: 303

It's incorrect, my method works if there are duplicate values. I've used it with maps having more than 100 keys with "1" as value. – Anthony – 2012-02-25T16:40:53.637

7

Major problem. If you use the first answer (Google takes you here), change the comparator to add an equal clause, otherwise you cannot get values from the sorted_map by keys:

public int compare(String a, String b) {
        if (base.get(a) > base.get(b)) {
            return 1;
        } else if (base.get(a) < base.get(b)){
            return -1;
        } 

        return 0;
        // returning 0 would merge keys
    }

cuneyt

Posted 2008-09-20T21:03:23.403

Reputation: 1

Now when you add two entries with equal values they will be merged you should only return 0 if you are sure that the objects are the same (equal) – Masood_mj – 2013-01-23T04:54:00.193

6

Best Approach

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

public class OrderByValue {

  public static void main(String a[]){
    Map<String, Integer> map = new HashMap<String, Integer>();
    map.put("java", 20);
    map.put("C++", 45);
    map.put("Unix", 67);
    map.put("MAC", 26);
    map.put("Why this kolavari", 93);
    Set<Entry<String, Integer>> set = map.entrySet();
    List<Entry<String, Integer>> list = new ArrayList<Entry<String, Integer>>(set);
    Collections.sort( list, new Comparator<Map.Entry<String, Integer>>()
    {
        public int compare( Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2 )
        {
            return (o1.getValue()).compareTo( o2.getValue() );//Ascending order
            //return (o2.getValue()).compareTo( o1.getValue() );//Descending order
        }
    } );
    for(Map.Entry<String, Integer> entry:list){
        System.out.println(entry.getKey()+" ==== "+entry.getValue());
    }
  }}

Output

java ==== 20

MAC ==== 26

C++ ==== 45

Unix ==== 67

Why this kolavari ==== 93

Nilesh Jadav

Posted 2008-09-20T21:03:23.403

Reputation: 606

6

There are a lot of answers for this question already, but none provided me what I was looking for, a map implementation that returns keys and entries sorted by the associated value, and maintains this property as keys and values are modified in the map. Two other questions ask for this specifically.

I cooked up a generic friendly example that solves this use case. This implementation does not honor all of the contracts of the Map interface, such as reflecting value changes and removals in the sets return from keySet() and entrySet() in the original object. I felt such a solution would be too large to include in a Stack Overflow answer. If I manage to create a more complete implementation, perhaps I will post it to Github and then to it link in an updated version of this answer.

import java.util.*;

/**
 * A map where {@link #keySet()} and {@link #entrySet()} return sets ordered
 * by associated values based on the the comparator provided at construction
 * time. The order of two or more keys with identical values is not defined.
 * <p>
 * Several contracts of the Map interface are not satisfied by this minimal
 * implementation.
 */
public class ValueSortedMap<K, V> extends HashMap<K, V> {
    protected Map<V, Collection<K>> valueToKeysMap;

    // uses natural order of value object, if any
    public ValueSortedMap() {
        this((Comparator<? super V>) null);
    }

    public ValueSortedMap(Comparator<? super V> valueComparator) {
        this.valueToKeysMap = new TreeMap<V, Collection<K>>(valueComparator);
    }

    public boolean containsValue(Object o) {
        return valueToKeysMap.containsKey(o);
    }

    public V put(K k, V v) {
        V oldV = null;
        if (containsKey(k)) {
            oldV = get(k);
            valueToKeysMap.get(oldV).remove(k);
        }
        super.put(k, v);
        if (!valueToKeysMap.containsKey(v)) {
            Collection<K> keys = new ArrayList<K>();
            keys.add(k);
            valueToKeysMap.put(v, keys);
        } else {
            valueToKeysMap.get(v).add(k);
        }
        return oldV;
    }

    public void putAll(Map<? extends K, ? extends V> m) {
        for (Map.Entry<? extends K, ? extends V> e : m.entrySet())
            put(e.getKey(), e.getValue());
    }

    public V remove(Object k) {
        V oldV = null;
        if (containsKey(k)) {
            oldV = get(k);
            super.remove(k);
            valueToKeysMap.get(oldV).remove(k);
        }
        return oldV;
    }

    public void clear() {
        super.clear();
        valueToKeysMap.clear();
    }

    public Set<K> keySet() {
        LinkedHashSet<K> ret = new LinkedHashSet<K>(size());
        for (V v : valueToKeysMap.keySet()) {
            Collection<K> keys = valueToKeysMap.get(v);
            ret.addAll(keys);
        }
        return ret;
    }

    public Set<Map.Entry<K, V>> entrySet() {
        LinkedHashSet<Map.Entry<K, V>> ret = new LinkedHashSet<Map.Entry<K, V>>(size());
        for (Collection<K> keys : valueToKeysMap.values()) {
            for (final K k : keys) {
                final V v = get(k);
                ret.add(new Map.Entry<K,V>() {
                    public K getKey() {
                        return k;
                    }

                    public V getValue() {
                        return v;
                    }

                    public V setValue(V v) {
                        throw new UnsupportedOperationException();
                    }
                });
            }
        }
        return ret;
    }
}

David Bleckmann

Posted 2008-09-20T21:03:23.403

Reputation: 51

5

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

Ryan Delucchi

Posted 2008-09-20T21:03:23.403

Reputation: 4 907

I don't see why this was -1, so far LinkedHashMap is probably the best solution for me, I'm just trying to figure out how expensive it is to throw away and create a new LinkedHashMap. – NobleUplift – 2016-04-18T20:07:15.260

5

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 the map into a set this way:

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

You will create class Results,

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()
        );
}

Darkless

Posted 2008-09-20T21:03:23.403

Reputation: 11

5

Since TreeMap<> does not work for values that can be equal, I used this:

private <K, V extends Comparable<? super V>> List<Entry<K, V>> sort(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());
        }
    });

    return list;
}

You might want to put list in a LinkedHashMap, but if you're only going to iterate over it right away, that's superfluous...

malix

Posted 2008-09-20T21:03:23.403

Reputation: 2 996

that's right but your comparator doesn't handle equals values case – Sebastien Lorber – 2011-12-27T17:48:33.950

4

Here is an OO solution (i.e., doesn't use static methods):

import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;

public class SortableValueMap<K, V extends Comparable<V>>
  extends LinkedHashMap<K, V> {
  public SortableValueMap() { }

  public SortableValueMap( Map<K, V> map ) {
    super( map );
  }

  public void sortByValue() {
    List<Map.Entry<K, V>> list = new LinkedList<Map.Entry<K, V>>( entrySet() );

    Collections.sort( list, new Comparator<Map.Entry<K, V>>() {
      public int compare( Map.Entry<K, V> entry1, Map.Entry<K, V> entry2 ) {
        return entry1.getValue().compareTo( entry2.getValue() );
      }
    });

    clear();

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

  private static void print( String text, Map<String, Double> map ) {
    System.out.println( text );

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

  public static void main( String[] args ) {
    SortableValueMap<String, Double> map =
      new SortableValueMap<String, Double>();

    map.put( "A", 67.5 );
    map.put( "B", 99.5 );
    map.put( "C", 82.4 );
    map.put( "D", 42.0 );

    print( "Unsorted map", map );
    map.sortByValue();
    print( "Sorted map", map );
  }
}

Hereby donated to the public domain.

Dave Jarvis

Posted 2008-09-20T21:03:23.403

Reputation: 20 689

4

Afaik the most cleaner way is utilizing collections to sort map on value:

Map<String, Long> map = new HashMap<String, Long>();
// populate with data to sort on Value
// use datastructure designed for sorting

Queue queue = new PriorityQueue( map.size(), new MapComparable() );
queue.addAll( map.entrySet() );

// get a sorted map
LinkedHashMap<String, Long> linkedMap = new LinkedHashMap<String, Long>();

for (Map.Entry<String, Long> entry; (entry = queue.poll())!=null;) {
    linkedMap.put(entry.getKey(), entry.getValue());
}

public static class MapComparable implements Comparator<Map.Entry<String, Long>>{

  public int compare(Entry<String, Long> e1, Entry<String, Long> e2) {
    return e1.getValue().compareTo(e2.getValue());
  }
}

lisak

Posted 2008-09-20T21:03:23.403

Reputation: 11 117

4

Some simple changes in order to have a sorted map with pairs that have duplicate values. In the compare method (class ValueComparator) when values are equal do not return 0 but return the result of comparing the 2 keys. Keys are distinct in a map so you succeed to keep duplicate values (which are sorted by keys by the way). So the above example could be modified like this:

    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 ((String)a).compareTo((String)b);
        } else {
          return -1;
        }
      }
    }

dimkar

Posted 2008-09-20T21:03:23.403

Reputation: 11

4

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
}

Maxim Veksler

Posted 2008-09-20T21:03:23.403

Reputation: 11 279

Then again maybe a better solution would be to just use a self sorting map, in the case use org.apache.commons.collections.bidimap.TreeBidiMap – Maxim Veksler – 2009-04-14T13:48:20.293

4

For sure the solution of Stephen is really great, but for those who can't use Guava:

Here's my solution for sorting by value a map. This solution handle the case where there are twice the same value etc...

// If you want to sort a map by value, and if there can be twice the same value:

// here is your original map
Map<String,Integer> mapToSortByValue = new HashMap<String, Integer>();
mapToSortByValue.put("A", 3);
mapToSortByValue.put("B", 1);
mapToSortByValue.put("C", 3);
mapToSortByValue.put("D", 5);
mapToSortByValue.put("E", -1);
mapToSortByValue.put("F", 1000);
mapToSortByValue.put("G", 79);
mapToSortByValue.put("H", 15);

// Sort all the map entries by value
Set<Map.Entry<String,Integer>> set = new TreeSet<Map.Entry<String,Integer>>(
        new Comparator<Map.Entry<String,Integer>>(){
            @Override
            public int compare(Map.Entry<String,Integer> obj1, Map.Entry<String,Integer> obj2) {
                Integer val1 = obj1.getValue();
                Integer val2 = obj2.getValue();
                // DUPLICATE VALUE CASE
                // If the values are equals, we can't return 0 because the 2 entries would be considered
                // as equals and one of them would be deleted (because we use a set, no duplicate, remember!)
                int compareValues = val1.compareTo(val2);
                if ( compareValues == 0 ) {
                    String key1 = obj1.getKey();
                    String key2 = obj2.getKey();
                    int compareKeys = key1.compareTo(key2);
                    if ( compareKeys == 0 ) {
                        // what you return here will tell us if you keep REAL KEY-VALUE duplicates in your set
                        // if you want to, do whatever you want but do not return 0 (but don't break the comparator contract!)
                        return 0;
                    }
                    return compareKeys;
                }
                return compareValues;
            }
        }
);
set.addAll(mapToSortByValue.entrySet());


// OK NOW OUR SET IS SORTED COOL!!!!

// And there's nothing more to do: the entries are sorted by value!
for ( Map.Entry<String,Integer> entry : set ) {
    System.out.println("Set entries: " + entry.getKey() + " -> " + entry.getValue());
}




// But if you add them to an hashmap
Map<String,Integer> myMap = new HashMap<String,Integer>();
// When iterating over the set the order is still good in the println...
for ( Map.Entry<String,Integer> entry : set ) {
    System.out.println("Added to result map entries: " + entry.getKey() + " " + entry.getValue());
    myMap.put(entry.getKey(), entry.getValue());
}

// But once they are in the hashmap, the order is not kept!
for ( Integer value : myMap.values() ) {
    System.out.println("Result map values: " + value);
}
// Also this way doesn't work:
// Logic because the entryset is a hashset for hashmaps and not a treeset
// (and even if it was a treeset, it would be on the keys only)
for ( Map.Entry<String,Integer> entry : myMap.entrySet() ) {
    System.out.println("Result map entries: " + entry.getKey() + " -> " + entry.getValue());
}


// CONCLUSION:
// If you want to iterate on a map ordered by value, you need to remember:
// 1) Maps are only sorted by keys, so you can't sort them directly by value
// 2) So you simply CAN'T return a map to a sortMapByValue function
// 3) You can't reverse the keys and the values because you have duplicate values
//    This also means you can't neither use Guava/Commons bidirectionnal treemaps or stuff like that

// SOLUTIONS
// So you can:
// 1) only sort the values which is easy, but you loose the key/value link (since you have duplicate values)
// 2) sort the map entries, but don't forget to handle the duplicate value case (like i did)
// 3) if you really need to return a map, use a LinkedHashMap which keep the insertion order

The exec: http://www.ideone.com/dq3Lu

The output:

Set entries: E -> -1
Set entries: B -> 1
Set entries: A -> 3
Set entries: C -> 3
Set entries: D -> 5
Set entries: H -> 15
Set entries: G -> 79
Set entries: F -> 1000
Added to result map entries: E -1
Added to result map entries: B 1
Added to result map entries: A 3
Added to result map entries: C 3
Added to result map entries: D 5
Added to result map entries: H 15
Added to result map entries: G 79
Added to result map entries: F 1000
Result map values: 5
Result map values: -1
Result map values: 1000
Result map values: 79
Result map values: 3
Result map values: 1
Result map values: 3
Result map values: 15
Result map entries: D -> 5
Result map entries: E -> -1
Result map entries: F -> 1000
Result map entries: G -> 79
Result map entries: A -> 3
Result map entries: B -> 1
Result map entries: C -> 3
Result map entries: H -> 15

Hope it will help some folks

Sebastien Lorber

Posted 2008-09-20T21:03:23.403

Reputation: 51 201

3

You can try Guava's multimaps:

TreeMap<Integer, Collection<String>> sortedMap = new TreeMap<>(
        Multimaps.invertFrom(Multimaps.forMap(originalMap), 
        ArrayListMultimap.<Integer, String>create()).asMap());

As a result you get a map from original values to collections of keys that correspond to them. This approach can be used even if there are multiple keys for the same value.

Vitalii Fedorenko

Posted 2008-09-20T21:03:23.403

Reputation: 68 637

3

I've merged the solutions of user157196 and Carter Page:

class MapUtil {

    public static <K, V extends Comparable<? super V>> Map<K, V> sortByValue( Map<K, V> map ){
        ValueComparator<K,V> bvc =  new ValueComparator<K,V>(map);
        TreeMap<K,V> sorted_map = new TreeMap<K,V>(bvc);
        sorted_map.putAll(map);
        return sorted_map;
    }

}

class ValueComparator<K, V extends Comparable<? super V>> implements Comparator<K> {

    Map<K, V> base;
    public ValueComparator(Map<K, V> base) {
        this.base = base;
    }

    public int compare(K a, K b) {
        int result = (base.get(a).compareTo(base.get(b)));
        if (result == 0) result=1;
        // returning 0 would merge keys
        return result;
    }
}

RobotMan

Posted 2008-09-20T21:03:23.403

Reputation: 323

3

If you have duplicate keys and only a small set of data (<1000) and your code is not performance critical you can just do the following:

Map<String,Integer> tempMap=new HashMap<String,Integer>(inputUnsortedMap);
LinkedHashMap<String,Integer> sortedOutputMap=new LinkedHashMap<String,Integer>();

for(int i=0;i<inputUnsortedMap.size();i++){
    Map.Entry<String,Integer> maxEntry=null;
    Integer maxValue=-1;
    for(Map.Entry<String,Integer> entry:tempMap.entrySet()){
        if(entry.getValue()>maxValue){
            maxValue=entry.getValue();
            maxEntry=entry;
        }
    }
    tempMap.remove(maxEntry.getKey());
    sortedOutputMap.put(maxEntry.getKey(),maxEntry.getValue());
}

inputUnsortedMap is the input to the code.

The variable sortedOutputMap will contain the data in decending order when iterated over. To change order just change > to a < in the if statement.

Is not the fastest sort but does the job without any additional dependencies.

nibor

Posted 2008-09-20T21:03:23.403

Reputation: 1

2

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(); }
}

Scott Stanchfield

Posted 2008-09-20T21:03:23.403

Reputation: 25 367

2

Late Entry.

With the advent of Java-8, we can use streams for data manipulation in a very easy/succinct way. You can use streams to sort the map entries by value and create a LinkedHashMap which preserves insertion-order iteration.

Eg:

LinkedHashMap sortedByValueMap = map.entrySet().stream()
                .sorted(comparing(Entry<Key,Value>::getValue).thenComparing(Entry::getKey))     //first sorting by Value, then sorting by Key(entries with same value)
                .collect(LinkedHashMap::new,(map,entry) -> map.put(entry.getKey(),entry.getValue()),LinkedHashMap::putAll);

For reverse ordering, replace:

comparing(Entry<Key,Value>::getValue).thenComparing(Entry::getKey)

with

comparing(Entry<Key,Value>::getValue).thenComparing(Entry::getKey).reversed()

Pankaj Singhal

Posted 2008-09-20T21:03:23.403

Reputation: 6 088

2

This method will just serve the purpose. (the 'setback' is that the Values must implement the java.util.Comparable interface)

  /**

 * Sort a map according to values.

 * @param <K> the key of the map.
 * @param <V> the value to sort according to.
 * @param mapToSort the map to sort.

 * @return a map sorted on the values.

 */ 
public static <K, V extends Comparable< ? super V>> Map<K, V>
sortMapByValues(final Map <K, V> mapToSort)
{
    List<Map.Entry<K, V>> entries =
        new ArrayList<Map.Entry<K, V>>(mapToSort.size());  

    entries.addAll(mapToSort.entrySet());

    Collections.sort(entries,
                     new Comparator<Map.Entry<K, V>>()
    {
        @Override
        public int compare(
               final Map.Entry<K, V> entry1,
               final Map.Entry<K, V> entry2)
        {
            return entry1.getValue().compareTo(entry2.getValue());
        }
    });      

    Map<K, V> sortedMap = new LinkedHashMap<K, V>();      

    for (Map.Entry<K, V> entry : entries)
    {
        sortedMap.put(entry.getKey(), entry.getValue());

    }      

    return sortedMap;

}

http://javawithswaranga.blogspot.com/2011/06/generic-method-to-sort-hashmap.html

didxga

Posted 2008-09-20T21:03:23.403

Reputation: 3 799

0

My solution is a quite simple approach in the way of using mostly given APIs. We use the feature of Map to export its content as Set via entrySet() method. We now have a Set containing Map.Entry objects.

Okay, a Set does not carry an order, but we can take the content an put it into an ArrayList. It now has an random order, but we will sort it anyway.

As ArrayList is a Collection, we now use the Collections.sort() method to bring order to chaos. Because our Map.Entry objects do not realize the kind of comparison we need, we provide a custom Comparator.

public static void main(String[] args) {
    HashMap<String, String> map = new HashMap<>();
    map.put("Z", "E");
    map.put("G", "A");
    map.put("D", "C");
    map.put("E", null);
    map.put("O", "C");
    map.put("L", "D");
    map.put("Q", "B");
    map.put("A", "F");
    map.put(null, "X");
    MapEntryComparator mapEntryComparator = new MapEntryComparator();

    List<Entry<String,String>> entryList = new ArrayList<>(map.entrySet());
    Collections.sort(entryList, mapEntryComparator);

    for (Entry<String, String> entry : entryList) {
        System.out.println(entry.getKey() + " : " + entry.getValue());
    }

}

Alexander

Posted 2008-09-20T21:03:23.403

Reputation: 1 158

0

Here is the code by Java 8 with AbacusUtil

Map<String, Integer> map = N.asMap("a", 2, "b", 3, "c", 1, "d", 2);
Map<String, Integer> sortedMap = Stream.of(map.entrySet()).sorted(Map.Entry.comparingByValue()).toMap(e -> e.getKey(), e -> e.getValue(),
    LinkedHashMap::new);
N.println(sortedMap);
// output: {c=1, a=2, d=2, b=3}

Declaration: I'm the developer of AbacusUtil.

user_3380739

Posted 2008-09-20T21:03:23.403

Reputation: 838

0

If there is a preference of having a Map data structure that inherently sorts by values without having to trigger any sort methods or explicitly pass to a utility, then the following solutions may be applicable:

(1) org.drools.chance.core.util.ValueSortedMap (JBoss project) maintains two maps internally one for lookup and one for maintaining the sorted values. Quite similar to previously added answers, but probably it is the abstraction and encapsulation part (including copying mechanism) that makes it safer to use from the outside.

(2) http://techblog.molindo.at/2008/11/java-map-sorted-by-value.html avoids maintaining two maps and instead relies/extends from Apache Common's LinkedMap. (Blog author's note: as all the code here is in the public domain):

// 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 & amp; & amp; !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()) & lt; = 0;
        } else {
            return ((Comparable) cur.getValue())
            .compareTo((V) link.getValue()) & gt; = 0;
        }
    }

    public boolean isAscending() {
        return _asc;
    }
}

(3) Write a custom Map or extends from LinkedHashMap that will only sort during enumeration (e.g., values(), keyset(), entryset()) as needed. The inner implementation/behavior is abstracted from the one using this class but it appears to the client of this class that values are always sorted when requested for enumeration. This class hopes that sorting will happen mostly once if all put operations have been completed before enumerations. Sorting method adopts some of the previous answers to this question.

public class SortByValueMap<K, V> implements Map<K, V> {

    private boolean isSortingNeeded = false;

    private final Map<K, V> map = new LinkedHashMap<>();

    @Override
    public V put(K key, V value) {
        isSortingNeeded = true;
        return map.put(key, value);
    }

    @Override
    public void putAll(Map<? extends K, ? extends V> map) {
        isSortingNeeded = true;
        map.putAll(map);
    }

    @Override
    public Set<K> keySet() {
        sort();
        return map.keySet();
    }

    @Override
    public Set<Entry<K, V>> entrySet() {
        sort();
        return map.entrySet();
    }

    @Override
    public Collection<V> values() {
        sort();
        return map.values();
    }

    private void sort() {
        if (!isSortingNeeded) {
            return;
        }

        List<Entry<K, V>> list = new ArrayList<>(size());

        for (Iterator<Map.Entry<K, V>> it = map.entrySet().iterator(); it.hasNext();) {
            Map.Entry<K, V> entry = it.next();
            list.add(entry);
            it.remove();
        }

        Collections.sort(list);

        for (Entry<K, V> entry : list) {
            map.put(entry.getKey(), entry.getValue());
        }

        isSortingNeeded = false;
    }

    @Override
    public String toString() {
        sort();
        return map.toString();
    }
}

(4) Guava offers ImmutableMap.Builder.orderEntriesByValue(Comparator valueComparator) although the resulting map will be immutable:

Configures this Builder to order entries by value according to the specified comparator.

The sort order is stable, that is, if two entries have values that compare as equivalent, the entry that was inserted first will be first in the built map's iteration order.

Kenston Choi

Posted 2008-09-20T21:03:23.403

Reputation: 2 054

0

I rewrote devinmoore's method that performs sorting a map by it's value without using Iterator :

public static Map<K, V> sortMapByValue(Map<K, V> inputMap) {

    Set<Entry<K, V>> set = inputMap.entrySet();
    List<Entry<K, V>> list = new ArrayList<Entry<K, V>>(set);

    Collections.sort(list, new Comparator<Map.Entry<K, V>>()
    {
        @Override
        public int compare(Entry<K, V> o1, Entry<K, V> o2) {
            return (o1.getValue()).compareTo( o2.getValue() );  //Ascending order
        }
    } );

    Map<K, V> sortedMap = new LinkedHashMap<>();

    for(Map.Entry<K, V> entry : list){
        sortedMap.put(entry.getKey(), entry.getValue());
    }

    return sortedMap;
}

Note: that we used LinkedHashMap as output map, because our list has been sorted by value and now we should store our list into output map with order of inserted key,values. So if you use for example TreeMap as your output map, your map will be sorted by map keys again!

This is the main method:

public static void main(String[] args) {
    Map<String, String> map = new HashMap<>();
    map.put("3", "three");
    map.put("1", "one");
    map.put("5", "five");
    System.out.println("Input Map:" + map);
    System.out.println("Sorted Map:" + sortMapByValue(map));
}

Finally, this is the output:

Input Map:{1=one, 3=three, 5=five}
Sorted Map:{5=five, 1=one, 3=three}

smart-developer

Posted 2008-09-20T21:03:23.403

Reputation: 27

0

The simplest brute-force sortHashMap method for HashMap<String, Long>: you can just copypaste it and use like this:

public class Test  {
    public static void main(String[] args)  {
        HashMap<String, Long> hashMap = new HashMap<>();
        hashMap.put("Cat", (long) 4);
        hashMap.put("Human", (long) 2);
        hashMap.put("Dog", (long) 4);
        hashMap.put("Fish", (long) 0);
        hashMap.put("Tree", (long) 1);
        hashMap.put("Three-legged-human", (long) 3);
        hashMap.put("Monkey", (long) 2);

        System.out.println(hashMap);  //{Human=2, Cat=4, Three-legged-human=3, Monkey=2, Fish=0, Tree=1, Dog=4}
        System.out.println(sortHashMap(hashMap));  //{Cat=4, Dog=4, Three-legged-human=3, Human=2, Monkey=2, Tree=1, Fish=0}
   }

   public LinkedHashMap<String, Long> sortHashMap(HashMap<String, Long> unsortedMap)  {
         LinkedHashMap<String, Long> result = new LinkedHashMap<>();

          //add String keys to an array: the array would get sorted, based on those keys' values
          ArrayList<String> sortedKeys = new ArrayList<>();
          for (String key: unsortedMap.keySet())  {
                   sortedKeys.add(key);
          }

            //sort the ArrayList<String> of keys    
           for (int i=0; i<unsortedMap.size(); i++)  {
                    for (int j=1; j<sortedKeys.size(); j++)  {
                         if (unsortedMap.get(sortedKeys.get(j)) > unsortedMap.get(sortedKeys.get(j-1))) {
                               String temp = sortedKeys.get(j);
                               sortedKeys.set(j, sortedKeys.get(j-1));
                               sortedKeys.set(j-1, temp);

                          }
                        }
                }

             //construct the result Map
            for (String key: sortedKeys)  {
                  result.put(key, unsortedMap.get(key));
                }

             return result;
        }
}

parsecer

Posted 2008-09-20T21:03:23.403

Reputation: 701

-1

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);
}

Output would be:

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

GHad

Posted 2008-09-20T21:03:23.403

Reputation: 6 602

put all the value in treeMap autometically they'll be sorted by its key using R-B Tree. – sitakant – 2015-12-15T11:19:40.680

The comparator passed to the TreeMap constructor compares the KEYS of the TreeMap instead of the VALUES.

In your example, it worked because sorting by keys is the same as sorting by values.

The full constructor is: public TreeMap(Comparator<? super K> comparator) Where it accepts decedents of K which is the key. For more refer to:

http://docs.oracle.com/javase/6/docs/api/java/util/TreeMap.html#TreeMap(java.util.Comparator)

– Hussein El Motayam – 2017-07-06T11:41:17.200

-1

public class Test {
  public static void main(String[] args) {
    TreeMap<Integer, String> hm=new TreeMap();
    hm.put(3, "arun singh");
    hm.put(5, "vinay singh");
    hm.put(1, "bandagi singh");
    hm.put(6, "vikram singh");
    hm.put(2, "panipat singh");
    hm.put(28, "jakarta singh");

    ArrayList<String> al=new ArrayList(hm.values());
    Collections.sort(al, new myComparator());

    System.out.println("//sort by values \n");
    for(String obj: al){
        for(Map.Entry<Integer, String> map2:hm.entrySet()){
            if(map2.getValue().equals(obj)){
                System.out.println(map2.getKey()+" "+map2.getValue());
            }
        } 
     }
  }
}

class myComparator implements Comparator{
    @Override
    public int compare(Object o1, Object o2) {
       String o3=(String) o1;
       String o4 =(String) o2;
       return o3.compareTo(o4);
    }   
}

OUTPUT=

//sort by values 

3 arun singh
1 bandagi singh
28 jakarta singh
2 panipat singh
6 vikram singh
5 vinay singh

Arun Raaj

Posted 2008-09-20T21:03:23.403

Reputation: 766

-1

public class SortedMapExample {

    public static void main(String[] args) {
        Map<String, String> map = new HashMap<String, String>();

        map.put("Cde", "C");
        map.put("Abc", "A");
        map.put("Cbc", "Z");
        map.put("Dbc", "D");
        map.put("Bcd", "B");
        map.put("sfd", "Bqw");
        map.put("DDD", "Bas");
        map.put("BGG", "Basd");

        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 V> compare) {
        Map<K, V> result = new LinkedHashMap<K, V>();
        V[] array = (V[])in.values().toArray();
        for(int i=0;i<array.length;i++)
        {

        }
        Arrays.sort(array, compare);
        for (V item : array) {
            K key= (K) getKey(in, item);
            result.put(key, item);
        }
        return result;
    }

    public static <K, V>  Object getKey(Map<K, V> in,V value)
    {
       Set<K> key= in.keySet();
       Iterator<K> keyIterator=key.iterator();
       while (keyIterator.hasNext()) {
           K valueObject = (K) keyIterator.next();
           if(in.get(valueObject).equals(value))
           {
                   return valueObject;
           }
       }
       return null;
   }

}

// Please try here. I am modifing the code for value sort.

Sunil Kumar Sahoo

Posted 2008-09-20T21:03:23.403

Reputation: 36 707

That's in O(n^2)... – assylias – 2014-03-03T17:24:08.240

-2

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

GHad

Posted 2008-09-20T21:03:23.403

Reputation: 6 602

1Doesn't work with duplicate values. – assylias – 2014-03-03T17:19:57.583

-2

We simply sort a map just like this

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

    unsortedMap.put("E", "E Val");
    unsortedMap.put("F", "F Val");
    unsortedMap.put("H", "H Val");
    unsortedMap.put("B", "B Val");
    unsortedMap.put("C", "C Val");
    unsortedMap.put("A", "A Val");
    unsortedMap.put("G", "G Val");
    unsortedMap.put("D", "D Val");

    Map<String, String> sortedMap = new TreeMap<String, String>(unsortedMap);

    System.out.println("\nAfter sorting..");
    for (Map.Entry <String, String> mapEntry : sortedMap.entrySet()) {
        System.out.println(mapEntry.getKey() + " \t" + mapEntry.getValue());

Rashid C Y

Posted 2008-09-20T21:03:23.403

Reputation: 101

9this just creates a treemap, treemaps sort on the key – NimChimpsky – 2012-09-18T11:55:11.903

-2

If there's not any value bigger than the size of the map, you could use arrays, this should be the fastest approach:

public List<String> getList(Map<String, Integer> myMap) {
    String[] copyArray = new String[myMap.size()];
    for (Entry<String, Integer> entry : myMap.entrySet()) {
        copyArray[entry.getValue()] = entry.getKey();
    }
    return Arrays.asList(copyArray);
}

Uxio

Posted 2008-09-20T21:03:23.403

Reputation: 911

-2

    static <K extends Comparable<? super K>, V extends Comparable<? super V>>
    Map sortByValueInDescendingOrder(final Map<K, V> map) {
        Map re = new TreeMap(new Comparator<K>() {
            @Override
            public int compare(K o1, K o2) {
                if (map.get(o1) == null || map.get(o2) == null) {
                    return -o1.compareTo(o2);
                }
                int result = -map.get(o1).compareTo(map.get(o2));
                if (result != 0) {
                    return result;
                }
                return -o1.compareTo(o2);
            }
        });
        re.putAll(map);
        return re;
    }
    @Test(timeout = 3000l, expected = Test.None.class)
    public void testSortByValueInDescendingOrder() {
        char[] arr = "googler".toCharArray();
        Map<Character, Integer> charToTimes = new HashMap();
        for (int i = 0; i < arr.length; i++) {
            Integer times = charToTimes.get(arr[i]);
            charToTimes.put(arr[i], times == null ? 1 : times + 1);
        }
        Map sortedByTimes = sortByValueInDescendingOrder(charToTimes);
        Assert.assertEquals(charToTimes.toString(), "{g=2, e=1, r=1, o=2, l=1}");
        Assert.assertEquals(sortedByTimes.toString(), "{o=2, g=2, r=1, l=1, e=1}");
        Assert.assertEquals(sortedByTimes.containsKey('a'), false);
        Assert.assertEquals(sortedByTimes.get('a'), null);
        Assert.assertEquals(sortedByTimes.get('g'), 2);
        Assert.assertEquals(sortedByTimes.equals(charToTimes), true);
    }

Bruce Zu

Posted 2008-09-20T21:03:23.403

Reputation: 152

-4

Best thing is to convert HashMap to TreeMap. TreeMap sort keys on its own. If you want to sort on values than quick fix can be you can switch values with keys if your values are not duplicates.

Tanuj Verma

Posted 2008-09-20T21:03:23.403

Reputation: 340

-9

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

Dónal

Posted 2008-09-20T21:03:23.403

Reputation: 120 536

3Won't work because you are just sorting a copy of the values, thus leaving the map untouched. – whiskeysierra – 2010-01-10T14:05:23.100

1Agreed. Simple and makes sense when compared to other submissions here. I'm not sure why everyone else is suggesting more complicated ways to solve this when Collections already has it done for you. – Aaron – 2008-09-21T19:27:08.400

19The reason is that this doesn't solve the problem. It sorts the values all right, but it throws away the keys. What the question asked for was a way to sort the map, meaning that the keys and values should still be linked. – gregory – 2008-10-20T13:22:17.017

-10

as map is unordered to sort it ,we can do following

Map<String, String> map= new TreeMap<String, String>(unsortMap);

You should note that, unlike a hash map, a tree map guarantees that its elements will be sorted in ascending key order.

rohan kamat

Posted 2008-09-20T21:03:23.403

Reputation: 537

8This sorts based on keys, not values. – Duncan Jones – 2014-04-15T07:29:24.533

-11

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

yoliho

Posted 2008-09-20T21:03:23.403

Reputation: 375

I'd use the SortedMap interface along with the TreeMap. Then you aren't tied to the TreeMap's implementation. – ScArcher2 – 2008-09-20T23:45:22.017

8The documentation is saying TreeMap sorts its keys based on their natural ordering or by a Comparator you provide. But the sorting is based on the keys, not the values. A Comparator that compared the values would give a tree structure the same as using the value as the key in the first place. – benzado – 2008-09-20T23:59:05.977