Why do we need List to sort using Collection.sort() method?

Question

I am planning to sort keys from a hashmap. I am using a customized sort method.

Following code gives me compile-time error on compareTo() method where I am using Set as Collection

Set<String> set = map.keySet();
Collections.sort(set, (a, b) -> map.get(a) == map.get(b) ?  a.compareTo(b) : map.get(b) - map.get(a));

If I convert Set to List and then sort then everything works fine.

List<String> words = new ArrayList<>(map.keySet());
Collections.sort(words, (a, b) -> map.get(a) == map.get(b) ?  a.compareTo(b) : map.get(b) - map.get(a));

What is the reason that I need to convert to List to sort the collection? Why can't I sort using Set?

Untold

Answer 1

A Set has no API to change the order. You will notice yourself if you try, e.g. to swap the first and second elements of a Set.

Further, sets have their own contracts regarding the order which would be violated if you could change it from the outside

• HashSet and the key set of a HashMap do not maintain an order at all. This is the general assumption for sets if no other contract is specified
• LinkedHashSet and the key set of a LinkedHashMap will reflect the insertion order
• TreeSet and the key set of a TreeMap use the natural order of the keys or the order of an explicitly specified comparator. All implementations of SortedSet are bound to a Comparator or the natural order of the keys.

In order to sort something you need a collection which maintains an order and has an API supporting to alter the order.

A List is a natural candidate. You can also sort arrays. Since LinkedHashMap reflects the insertion order, you can create a LinkedHashMap with a specific order by adding the elements in the desired order:

map = map.entrySet().stream()
    .sorted(Map.Entry.<String,Integer>comparingByValue().reversed()
                     .thenComparing(Map.Entry::getKey))
    .collect(Collectors.toMap(Map.Entry::getKey, Map.Entry::getValue,
                              (a,b)->b, LinkedHashMap::new));

Besides, your comparator looks broken. The term map.get(b) - map.get(a) indicates that the values are numerical, in the examples above I assumed Integer, but map.get(a) == map.get(b) compares the references of the boxed objects.

And in case of Integer, the difference map.get(b) - map.get(a) can overflow. You should use Integer.compare(map.get(b), map.get(a) instead.

Or use the factory methods for comparators whenever applicable

List<String> words = new ArrayList<>(map.keySet());
words.sort(Comparator.<String>comparingInt(map::get).reversed()
                     .thenComparing(Comparator.naturalOrder()));

Yonit

Answer 2

By definition in Java, Set is NOT an ordered collection.

We can’t sort a Java Set collection by calling Collections.sort() method on a Set.

There is no direct support for sorting the sets in Java. To sort a set, follow these steps:

• Convert set to list.
• Sort list using Collections.sort() API.
• Convert list back to set.

OR

We can use a sorted implementation of set.

According to the following diagram HashSet, LinkedHashSet, and TreeSet are implementations of Set.

• HashSet: Unordered
• LinkedHashSet: Insertion order
• TreeSet: Ordered (natural order i.e. alphabetic, alphanumeric or chronological)

Note: HashSet is the default implementation used in most cases.

Diagram Reference: https://dzone.com/articles/an-introduction-to-the-java-collections-framework

Gagman