Java Sortedmap Example Sort by Value
Learn about Sort Map by Value in Java.
Overview
There are several direct ways to deal with the order of the keys in a map because keys must be unique. However, for sorting based on values, there isn't any direct method available in Java yet. So, we have discussed different ways by which a Map can be sorted by its values. We'll use Stream API's sorted() method, Collections.sort() and Comparator interface to enable sorting based on values.
Scope
- The article discusses several ways to sort a Map by value in Java by making use of Comparator, Collections.sort(), and Stream API.
- It is better to have an idea about Comparable and Comparator in Java before going through this discussion.
- Stream API along with the needed methods has been briefly explained.
- The use of constructor reference or double colon operator(::) needs prior knowledge.
Introduction
It isn't easy to deal with the values of a map in Java. There might be some guidelines to follow while assigning a key to any key-value pair. However, the same doesn't apply to the corresponding values. The reason is obvious: there needs to be a unique key in order to fetch the values, but there can be the same values for two unique keys.
It can be sometimes puzzling to obtain a map that is sorted according to the values. Moreover, there's no such sort() method for a map. Collections.sort() method is only applicable for lists such as ArrayList, LinkedList, etc. So, the discomfort brings us back to creating our own way of sorting a map by value in Java.
Upon a closer look, it's clear that a list can be used as a way to facilitate sorting of map's elements with the help of Collections.sort(). We can also make use of a comparator at times to sort the values in a map. And although we do have the access to TreeMap, a TreeMap makes a comparison to sort elements after every modification, be it insertion, deletion or change in any value. This makes the TreeMap slower as compared to the HashMap.
| Maps | HashMap | TreeMap |
|---|---|---|
| put | O(1) | O(logN) |
| remove | O(1) | O(logN) |
| get | O(1) | O(logN) |
| containsKey | O(1) | O(logN) |
| Data Structure | Hashtable | Red-Black Tree |
Let us consider an example where we have a Map of fruits as keys with the mentioned prices as their values. Now, we need to sort all the fruits as per their price value. So, we have the following approach to deal with this challenge.
Example: Sort Map by Value in Java Using sort() Method
The basic idea to sort a map by value in Java will be to make our way into using what's already available:sort() method for lists.
First of all, lambda expressions will be used along with forEach loop to avoid multiple lines, specifying the entire for loop with the print statement.
hashmap.forEach((key,value)-> System.out.println(key + " -> " + value));
A lambda expression is an instance of a functional interface (interface comprising only one abstract method). It is an anonymous method that provides the implementation for the abstract method. Lambda expressions are translated into byte code during the compilation process.
Notice that the parameters are mentioned inside the braces. The surrounding context of the expression in Java reduces the need for type declarations of these parameters. It is followed by a lambda operator (->), which is then followed by the implementation of the abstract method. During compilation, this implementation will be generated with a private method or private static method. Moreover, forEach loop is simply being used to iterate over the elements of the Map one by one.
Coming back to our example, we have to create a list from the entrySet of the Map.
List<Map.Entry<String, Integer>> list = new ArrayList<>(hashmap.entrySet());
Since we are dealing with an entry of a Map, we'll specify that the list accepts the entry being converted to the generic Map.Entry, which makes the accessing of elements (entry) from a Map more convenient due to the availability of several methods.
The Map.Entry interface comprises the comparingByValue() method, which in turn, compares Map.Entry based on the values and follows the natural sorting order. Alternatively, it also uses the user-defined Comparator to compare the values in a map.
list.sort(Map.Entry.comparingByValue());
Inside the sort() method, pass the comparingByValue() method to enable comparison among the values of the entry.
Note: The method comparingByValue() throws NullPointerException while comparing any entry having null value.
Therefore, the list eventually consists of the elements sorted according to their values.
import java.util.*; public class Main { public static void main (String[] args) { //Creating a map (fruit name -> key, price -> value) Map<String, Integer> hashmap = new HashMap<>(); //Inserting elements hashmap.put( "Avocado" , 80 ); hashmap.put( "Honeydew" , 60 ); hashmap.put( "Blueberries" , 45 ); hashmap.put( "Cranberries" , 60 ); hashmap.put( "Mango" , 75 ); //Using forEach loop to print the elements //Before sorting System.out.println( "The original array before sorting:" ); hashmap.forEach((key,value)->System.out.println(key + " -> " + value)); //After sorting System.out.println( "\nAfter sorting by their prices:" ); //Creating a list of the original hashmap in order to sort //the elements with sort() method List<Map.Entry<String, Integer>> list = new ArrayList<>(hashmap.entrySet()); //Using Entry's comparingByValue() method for sorting in ascending order list.sort(Map.Entry.comparingByValue()); //Printing the elements from the list list.forEach((fruit)->System.out.println(fruit.getKey() + " -> " + fruit.getValue())); } }
Output:
The original array before sorting: Blueberries -> 45 Avocado -> 80 Mango -> 75 Honeydew -> 60 Cranberries -> 60 After sorting by their prices: Blueberries -> 45 Cranberries -> 60 Honeydew -> 60 Mango -> 75 Avocado -> 80
Time Complexity:
O(NlogN), where 'N' is the number of inputs
Example: Sort Map by Value in Java using Stream APIs (In ascending and descending order)
Sorting in Ascending Order
The second option would be to make use of Stream API to sort the map by values. We'll make use of it for ascending as well as descending order.
The collection of objects can be processed with the use of several methods present in Stream API. A stream is a collection of objects which is backed by different pipelined methods.
The intermediate operations in Stream API return a stream object which is then processed by the terminal operations. Here, we are going to use sorted() method for stream objects.
So, we use stream() method to convert the entrySet of the Map into the stream and apply sorted() method to them which will sort the map.
Also, the sorted method is informed of the natural sorting order with the help of Map.Entry comparingByValue() method. With forEach, we can access all the elements to get the key-value pairs one by one.
hashmap.entrySet().stream() .sorted(Map.Entry.<String, Integer> comparingByValue()) .forEach((fruit)->System.out.println(fruit.getKey() + " -> " + fruit.getValue()));
import java.util.*; public class Main { public static void main (String[] args) { //Creating a hashmap (fruit name -> key, price -> value) Map<String, Integer> hashmap = new HashMap<>(); //Inserting elements hashmap.put( "Avocado" , 80 ); hashmap.put( "Honeydew" , 60 ); hashmap.put( "Blueberries" , 45 ); hashmap.put( "Cranberries" , 60 ); hashmap.put( "Mango" , 75 ); //Using forEach loop to print the elements //Before sorting System.out.println( "The original array before sorting:" ); hashmap.forEach((key,value)->System.out.println(key + " -> " + value)); //Sorting in the increasing order System.out.println( "After sorting in increasing order of their prices:" ); //Using stream() method on entrySet, //followed by sorted method that uses comparingByValue and //finally, forEach with lambda expression to get key and value separately hashmap.entrySet().stream() .sorted(Map.Entry.<String, Integer> comparingByValue()) .forEach((fruit)->System.out.println(fruit.getKey() + " -> " + fruit.getValue())); } }
Output:
The original array before sorting: Blueberries -> 45 Avocado -> 80 Mango -> 75 Honeydew -> 60 Cranberries -> 60 After sorting in increasing order of their prices: Blueberries -> 45 Honeydew -> 60 Cranberries -> 60 Mango -> 75 Avocado -> 80
Time Complexity:
O(NlogN), where 'N' is the number of inputs
Sorting in Descending Order
Everything here is the same as we did for the ascending order, except for comparingByValue().reversed() method that will follow the reverse ordering of the elements.
hashmap.entrySet().stream() .sorted(Map.Entry.<String, Integer> comparingByValue().reversed()) .forEach((fruit)->System.out.println(fruit.getKey() + " -> " + fruit.getValue()));
import java.util.*; public class Main { public static void main (String[] args) { //Creating a hashmap (fruit name -> key, price -> value) Map<String, Integer> hashmap = new HashMap<>(); //Inserting elements hashmap.put( "Avocado" , 80 ); hashmap.put( "Honeydew" , 60 ); hashmap.put( "Blueberries" , 45 ); hashmap.put( "Cranberries" , 60 ); hashmap.put( "Mango" , 75 ); //Using forEach loop to print the elements //Before sorting System.out.println( "The original array before sorting:" ); hashmap.forEach((key,value)->System.out.println(key + " -> " + value)); //Sorting in the reversed order System.out.println( "\nAfter sorting in decreasing order of their prices:" ); //Using stream() method on entrySet, //followed by sorted method that uses comparingByValue().reversed() //to print the elements in the decreasing order of their prices, and //finally, forEach with lambda expression to get key and value separately hashmap.entrySet().stream() .sorted(Map.Entry.<String, Integer> comparingByValue().reversed()) .forEach((fruit)->System.out.println(fruit.getKey() + " -> " + fruit.getValue())); } }
Output:
The original array before sorting: Blueberries -> 45 Avocado -> 80 Mango -> 75 Honeydew -> 60 Cranberries -> 60 After sorting in decreasing order of their prices: Avocado -> 80 Mango -> 75 Honeydew -> 60 Cranberries -> 60 Blueberries -> 45
Time Complexity:
O(NlogN), where 'N' is the number of inputs
Note: We haven't stored the sorted elements anywhere using Stream API yet, so the ordering isn't maintained once we have accessed each element through forEach loop. The hashmap will remain unsorted after the process. To deal with this problem, we'll be using collect() method in the further examples.
Example: Sort Map by Value in Java Using sort() Method with Comparator
The idea is to create a list (LinkedList in this case) to perform our sorting operation but also with a comparator that accepts an entry from a map and internally uses compare() method to compare the entries based on their respective values.
List<Map.Entry<String, Integer> > list = new LinkedList<>(hashmap.entrySet()); Collections.sort(list, new Comparator<Map.Entry<String, Integer>>(){ public int compare (Map.Entry<String, Integer> fruit1, Map.Entry<String, Integer> fruit2) { return (fruit1.getValue()).compareTo(fruit2.getValue()); } });
Then, we need to maintain the insertion order of the elements from now on. So, we'll use LinkedHashMap to insert the elements one by one from the LinkedList.
LinkedHashMap is exactly the same as a HashMap but LinkedHashMap also has LinkedList along with Hashtable as its data structure. Therefore, unlike HashMap, it can preserve the insertion order.
HashMap<String, Integer> sortedHashMap = new LinkedHashMap<String, Integer>();
import java.util.*; public class Main { public static void main (String[] args) { //Creating a hashmap (fruit name -> key, price -> value) Map<String, Integer> hashmap = new HashMap<>(); //Inserting elements hashmap.put( "Avocado" , 80 ); hashmap.put( "Honeydew" , 60 ); hashmap.put( "Blueberries" , 45 ); hashmap.put( "Cranberries" , 60 ); hashmap.put( "Mango" , 75 ); //Using forEach loop to print the elements //Before sorting System.out.println( "The original array before sorting:" ); hashmap.forEach((key,value)->System.out.println(key + " -> " + value)); //After sorting System.out.println( "\nAfter sorting by their prices:" ); //In order to use Collections' sorting method, //we need to create a List that contains the entries List<Map.Entry<String, Integer> > list = new LinkedList<>(hashmap.entrySet()); // Using comaparator to compare and sort the elements // based on the increasing order of their values Collections.sort(list, new Comparator<Map.Entry<String, Integer> >() { //Compare method facilitates custom sorting order public int compare (Map.Entry<String, Integer> fruit1, Map.Entry<String, Integer> fruit2) { return (fruit1.getValue()).compareTo(fruit2.getValue()); } }); // Creating a LinkedHashMap to store the elements from list // and maintain their insertion order HashMap<String, Integer> sortedHashMap = new LinkedHashMap<String, Integer>(); // Storing the elements(keys -> values) by iterating over list elements for (Map.Entry<String, Integer> fruit : list) { sortedHashMap.put(fruit.getKey(), fruit.getValue()); } //Printing the elements with the help of forEach loop sortedHashMap.forEach((key,value)-> System.out.println(key + " -> " + value)); } }
Output
The original array before sorting: Blueberries -> 45 Avocado -> 80 Mango -> 75 Honeydew -> 60 Cranberries -> 60 After sorting by their prices: Blueberries -> 45 Honeydew -> 60 Cranberries -> 60 Mango -> 75 Avocado -> 80
Time Complexity:
O(NlogN), where 'N' is the number of inputs
Example: Sort Map by Value in Java Using collect() and toMap() Method
Initially, we need to know a bit about the Collector interface. It consists of various reduction operations by which we can gather the elements in a container. The toMap() method present in the Collector interface accumulates the elements in a Map. There are 3 different ways to specify overloading on toMap() method, out of which, we are going to use the following one:
Syntax:
public static <T, K, U, M extends Map> Collector toMap (Function keyMapper, Function valueMapper, BinaryOperator<U> mergeFunction, Supplier mapSupplier)
Here, T refers to the type of the input elements. toMap() comprises four different parameters.
- keyMapper generates all the keys
- valueMapper generates all the values
- mergeFunction will be used at places where different values have been assigned the same keys in order to avoid collision
- mapSupplier is a new empty Map passed as to insert the elements from the original map. In our case, we'll be using LinkedHashMap to store the elements with their insertion order.
Collectors.toMap(Map.Entry::getKey, Map.Entry::getValue, (key, value) -> key, LinkedHashMap:: new )
Note: We have also used constructor reference (::) to provide direct reference to the constructor. Example:
Finally, the collect() method is a terminal operation that collects the elements of the stream on which we can use forEach loop to print the elements.
//import Collectors to use Collectors.toMap() directly import java.util.*; import java.util.stream.Collectors; public class Main { public static void main (String[] args) { //Creating a hashmap (fruit name -> key, price -> value) Map<String, Integer> hashmap = new HashMap<>(); //Inserting elements hashmap.put( "Avocado" , 80 ); hashmap.put( "Honeydew" , 60 ); hashmap.put( "Blue Berries" , 45 ); hashmap.put( "Cranberries" , 60 ); hashmap.put( "Mango" , 75 ); //Using forEach loop to print the elements //Before sorting System.out.println( "The original array before sorting:" ); hashmap.forEach((key,value)->System.out.println(key + " -> " + value)); //After sorting System.out.println( "\nAfter sorting by their prices:" ); //Using collect() with Collectors.toMap to yield a map //which will be stored in the LinkedHashMap to maintain order Map<String, Integer> sortedMap = hashmap.entrySet().stream() .sorted(Map.Entry.<String, Integer> comparingByValue()) //the constructor refernce operator has been used to create a LinkedHashMap .collect(Collectors.toMap(Map.Entry::getKey, Map.Entry::getValue, (key, value) -> key, LinkedHashMap:: new )); //Printing the elements from sortedMap sortedMap.forEach((key, value)->System.out.println(key + " -> " + value)); } }
Output:
The original array before sorting: Blue Berries -> 45 Avocado -> 80 Mango -> 75 Honeydew -> 60 Cranberries -> 60 After sorting by their prices: Blue Berries -> 45 Honeydew -> 60 Cranberries -> 60 Mango -> 75 Avocado -> 80
Time Complexity:
O(NlogN), where 'N' is the number of inputs
Example: Sort Map by Value in Java using Custom Code
We can create our own Comparator class of Object type that has a map as its instance variable. We also need to define a constructor with a map as a parameter.
The compare() method will compare the two objects as per their mapped values. The sorting operation depends on the value that the compare() method returns.
import java.util.*; public class Main { //Class CustomComparator to define our own sorting criteria public static class CustomComparator implements Comparator < Object > { //Here, map is an instance variable CustomComparator class Map<String, Integer> map; //Defining constructor to accept the incoming map as a parameter public CustomComparator (Map<String, Integer> map) { this .map = map; } //compare() method aceepts and compares two objects //based on their mapped values public int compare (Object fruit1, Object fruit2) { //it returns 1 if the values are equal //to retain both the entries with same values if (map.get(fruit1) == map.get(fruit2)) return 1 ; //When the above condition fails, the objects will be compared by compareTo( method) //if it returns -1, then fruit1 will be put before fruit2 in the map //if it returns 1, then fruit2 will be put before fruit1 in the map return ((Integer) map.get(fruit1)).compareTo((Integer) map.get(fruit2)); } } //Main method public static void main (String[] args) { //Creating a hashmap (fruit name -> key, price -> value) Map<String, Integer> hashmap = new HashMap<>(); //Inserting elements hashmap.put( "Avocado" , 80 ); hashmap.put( "Honeydew" , 60 ); hashmap.put( "Blueberries" , 45 ); hashmap.put( "Cranberries" , 60 ); hashmap.put( "Mango" , 75 ); //Using forEach loop to print the elements //Before sorting System.out.println( "The original array before sorting:" ); hashmap.forEach((key,value)->System.out.println(key + " -> " + value)); //Creating a treeMap with the CustomComparator as an argument //CustomComparator accepts the hashmap as a parameter to compare hashmap's objects Map<String, Integer> treeMap = new TreeMap<>( new CustomComparator(hashmap)); //Putting all the entries from the hashmap //The comparison between the entries will be done after the insertion treeMap.putAll(hashmap); //After sorting System.out.println( "\nAfter sorting by their prices:" ); treeMap.forEach((key, value) -> System.out.println(key + " -> " + value)); } }
Output:
The original array before sorting: Blueberries -> 45 Avocado -> 80 Mango -> 75 Honeydew -> 60 Cranberries -> 60 After sorting by their prices: Blueberries -> 45 Honeydew -> 60 Cranberries -> 60 Mango -> 75 Avocado -> 80
Time Complexity:
O(NlogN), where 'N' is the number of inputs
Conclusion
- We can create a list to sort the elements of a map and use Map.Entry.comparingByValue() method to sort them as per the natural sorting order.
- Stream API can be implemented to sort maps in Java either in ascending order with stream().sorted() that uses comparingbyValue() as a parameter.
- For descending order, stream().sorted() will be used along with comparingbyValue().reversed() as a parameter.
- We can also make use of the Comparator interface to implement compare method for the sorting operation.
- The Collector interface constitutes the collect method to accumulate the stream of objects and toMap() method can be used to convert the collection into a Map.
- TreeMap can also be used with the user-defined Comparator class. However, since the sorting happens with every modification in the map, TreeMap becomes slower than HashMap.
Source: https://www.scaler.com/topics/sort-map-by-value-in-java/
0 Response to "Java Sortedmap Example Sort by Value"
Post a Comment