How are identical values sorted with this code?

Question

The code in this question belongs to this answer.

My question is : how are identical values sorted with the following code?

import java.util.*;

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

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

The identical values should stay in the same order as they were before the sorting — baudsp, Aug 26 '16 at 13:29

score 4 · Answer 1 · answered Aug 26 '16 at 12:21

4

From the documentation of Collections.sort() (http://docs.oracle.com/javase/8/docs/api/java/util/Collections.html#sort-java.util.List-):

This sort is guaranteed to be stable: equal elements will not be reordered as a result of the sort.

So the order of equal elements (i.e. in this case entries with equal values) will be the same as in the original entry set returned by map.entrySet().

answered Aug 26 '16 at 12:21

Florian Link

638
4
11

Correct. The entry set, in turn, being a set, doesn’t have any particular order, so the entries may come into the list in any order. No wonder that the OP couldn’t see any specific pattern. – Ole V.V. Aug 26 '16 at 12:41
@Ole Indeed, I couldn't see any specific pattern. But, the end result is *always* in the same order. – Dake Aug 26 '16 at 12:47
… until the next version of Java comes out. ;-) Seriously, while the order is not likely to change, don’t rely hard on it always being the same as long as you have tried it only on one computer running one Java version. – Ole V.V. Aug 26 '16 at 12:50
If you need to rely on a specific ordering of equal values you should extend the Comparator to reflect that behavior. – Florian Link Aug 26 '16 at 13:36
@Florian Thank you. Can you please give an example? – Dake Aug 26 '16 at 14:25
@Ole Thanks. How should I extend the Comparator to make the equal values be sorted by their date added to the map? – Dake Aug 26 '16 at 18:44

score 2 · Answer 2 · answered Aug 26 '16 at 21:59

This answer is partly an answer to some of the comments.

First, while Dake, the original poster, observed the same order for the same input, in general, different Map implementations (like HashMap, LinkedHashMap and TreeMap) generally hand out the elements of their entry sets in different orders, which is enough to have the original poster’s code give different results on maps containing the same mappings.

Second, I was asked in a comment about a Comparator to make the equal values be sorted by their date added to the map. Generally, maps don’t keep track of such a date, so that’s not possible. However, if you use a LinkedHashMap for the origianl map, it keeps the insertion order, so this will fulfil your requirement.

Finally for the sake of completenes, say you want to sort entries with equal values by their keys:

public static <K extends Comparable<? super K>, V extends Comparable<? super V>> Map<K, V> sortByValue( Map<K, V> map )
{
    List<Map.Entry<K, V>> list = new ArrayList<Map.Entry<K, V>>( map.entrySet() );
    list.sort(Comparator.comparing(Map.Entry<K, V>::getValue).thenComparing(Map.Entry<K, V>::getKey) );

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

This is the Java 8 answer. You can obtain the same in earlier Java versions with a few more lines of code.

How are identical values sorted with this code?

2 Answers2