Sorting a single-element collection (e.g., arrays or lists) is quite easy in Java. It uses advanced techniques like CountingSort and DualPivotQuickSort. However, it is sometimes necessary to sort multi-element collects such as LinkedHashMaps. Prior to streams in Java 1.8, there was no relatively simply means of sorting these types of collections. I say “relatively simple” because it is still a process as opposed to calling Collections.sort(list), for instance. In this post, I will discuss three ways to sort a LinkedHashMap by key/value in forward/reverse order.
Three Approaches
The three implemented methods are streams returning a new collection (streaming-new), streams sorting within the given collection (streaming-replace), and a non-stream in-place sorting approach (non-streaming).
Streams, introduced in java.util in Java 1.8, execute sophisticated data processing queries on collections (not to be confused with I/O streams). They are thread-safe, employ lambda expressions, and are obtained from the collection to process. The methods of interest in this post are sorted, collect, and forEachOrdered.
Prior to streams, one had to create a custom Comparator within Collections.sort(list, comparator). While this is not a tedious process, it is not nearly as clean and concise as a stream.
Stream and Comparator Sorting
Below is the implemented code for the three approaches in two K/V configurations: String/String and String/Integer – other forms are easily derived from these examples. The methods sortSS_Stream_New and sortSI_Stream_New return a new LinkedHashMap; the others sort the passed map.
The stream is retrieved from the LinkedHashMap‘s entry set. That value is then configured for sorting using sorted(comparator). An in-place sort is executed using the forEachOrdered statement (e.g., lines 44-47), which first removes the K/V pair, then reenters it (these steps are required to effectively change the linked list order). A new collection is created using collect(Collectors.toMap(keyMapper, valueMapper, mergeFunction, mapSupplier) (e.g. lines 70-75), which effectively creates a new LinkedHashMap() and populates it with the results of the sorted function.
The non-stream comparator version first creates an ArrayList of the map’s entry set (e.g., line 142). Then, it sorts the list using a custom Comparator (e.g., lines 143-162). After sorting, it reenters the values from the list into the supplied map (e.g., lines 165-169).
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;
import java.util.stream.Collectors;
/**
* Provides static sorting methods for {@link LinkedHashMap}s. It can sort by
* key or value ({@link SORT}) in forward or reverse ({@link ORDER}). Supported
* in this class are {@code K/V} pairs: {@code String/String} and
* {@code String/Integer}. Other forms are easily derived from these examples.
* @author Ray Hylock
*/
public class SortLHM {
/** Sort options. */
public static enum SORT { KEY, VALUE };
public static enum ORDER { FORWARD, REVERSE };
/** This class should not be instantiated. */
private SortLHM(){}
/**
* Sorts a {@link LinkedHashMap} with a {@link String} key and
* {@link String} value based on the {@link SORT} parameter in
* {@link ORDER} - Java 1.8+ required. This sorts the {@code map}.
* @param map the {@link LinkedHashMap} to sort
* @param sort sort on the key or value
* @param order sort forward or reverse
*/
public static void sortSS_Stream(LinkedHashMap<String, String> map,
final SORT sort, final ORDER order) {
map.entrySet().stream()
.sorted(
(sort == SORT.KEY) ?
(order == ORDER.FORWARD) ? Map.Entry.comparingByKey()
: Map.Entry.comparingByKey(Comparator.reverseOrder())
:
(order == ORDER.FORWARD) ? Map.Entry.comparingByValue()
: Map.Entry.comparingByValue(Comparator.reverseOrder())
)
.forEachOrdered(e -> {
map.remove(e.getKey(), e.getValue()); // removes old order
map.put(e.getKey(), e.getValue()); // adds new order
});
}
/**
* Sorts a {@link LinkedHashMap} with a {@link String} key and
* {@link String} value based on the {@link SORT} parameter in
* {@link ORDER} - Java 1.8+ required.
* @param map the {@link LinkedHashMap} to sort
* @param sort sort on the key or value
* @param order sort forward or reverse
* @return sorted {@link LinkedHashMap}
*/
public static LinkedHashMap<String, String> sortSS_Stream_New(
LinkedHashMap<String, String> map, final SORT sort, final ORDER order) {
return map.entrySet().stream()
.sorted(
(sort == SORT.KEY) ?
(order == ORDER.FORWARD) ? Map.Entry.comparingByKey()
: Map.Entry.comparingByKey(Comparator.reverseOrder())
:
(order == ORDER.FORWARD) ? Map.Entry.comparingByValue()
: Map.Entry.comparingByValue(Comparator.reverseOrder())
)
.collect(Collectors.toMap(
Map.Entry::getKey,
Map.Entry::getValue,
(x, y) -> { throw new AssertionError(); },
LinkedHashMap::new
));
}
/**
* Sorts a {@link LinkedHashMap} with a {@link String} key and
* {@link Integer} value based on the {@link SORT} parameter in
* {@link ORDER} - Java 1.8+ required. This sorts the {@code map}.
* @param map the {@link LinkedHashMap} to sort
* @param sort sort on the key or value
* @param order sort forward or reverse
*/
public static void sortSI_Stream(LinkedHashMap<String, Integer> map,
final SORT sort, final ORDER order) {
map.entrySet().stream()
.sorted(
(sort == SORT.KEY) ?
(order == ORDER.FORWARD) ? Map.Entry.comparingByKey()
: Map.Entry.comparingByKey(Comparator.reverseOrder())
:
(order == ORDER.FORWARD) ? Map.Entry.comparingByValue()
: Map.Entry.comparingByValue(Comparator.reverseOrder())
)
.forEachOrdered(e -> {
map.remove(e.getKey(), e.getValue()); // removes old order
map.put(e.getKey(), e.getValue()); // adds new order
});
}
/**
* Sorts a {@link LinkedHashMap} with a {@link String} key and
* {@link Integer} value based on the {@link SORT} parameter in
* {@link ORDER} - Java 1.8+ required.
* @param map the {@link LinkedHashMap} to sort
* @param sort sort on the key or value
* @param order sort forward or reverse
* @return sorted {@link LinkedHashMap}
*/
public static LinkedHashMap<String, Integer> sortSI_Stream_New(
LinkedHashMap<String, Integer> map, final SORT sort, final ORDER order) {
return map.entrySet().stream()
.sorted(
(sort == SORT.KEY) ?
(order == ORDER.FORWARD) ? Map.Entry.comparingByKey()
: Map.Entry.comparingByKey(Comparator.reverseOrder())
:
(order == ORDER.FORWARD) ? Map.Entry.comparingByValue()
: Map.Entry.comparingByValue(Comparator.reverseOrder())
)
.collect(Collectors.toMap(
Map.Entry::getKey,
Map.Entry::getValue,
(x, y) -> { throw new AssertionError(); },
LinkedHashMap::new
));
}
/**
* Sorts a {@link LinkedHashMap} with a {@link String} key and
* {@link String} value based on the {@link SORT} parameter in
* {@link ORDER}. This sorts the {@code map}.
* @param map the {@link LinkedHashMap} to sort
* @param sort sort on the key or value
* @param order sort forward or reverse
*/
public static void sortSS(LinkedHashMap<String, String> map,
final SORT sort, final ORDER order) {
// convert to a list and sort
List list = new ArrayList(map.entrySet());
Collections.sort(list, new Comparator() {
@Override
public int compare(Object o1, Object o2) {
if(sort == SORT.KEY){
return (order == ORDER.FORWARD) ?
((Comparable)((Map.Entry)o1).getKey())
.compareTo(((Map.Entry)o2).getKey())
:
((Comparable)((Map.Entry)o2).getKey())
.compareTo(((Map.Entry)o1).getKey());
} else {
return (order == ORDER.FORWARD) ?
((Comparable)((Map.Entry)o1).getValue())
.compareTo(((Map.Entry)o2).getValue())
:
((Comparable)((Map.Entry)o2).getValue())
.compareTo(((Map.Entry)o1).getValue());
}
}
});
// put sorted list back into map
map.clear();
for (Iterator it = list.iterator(); it.hasNext();) {
Map.Entry entry = (Map.Entry)it.next();
map.put((String)entry.getKey(), (String)entry.getValue());
}
// clean up
list = null;
}
/**
* Sorts a {@link LinkedHashMap} with a {@link String} key and
* {@link Integer} value based on the {@link SORT} parameter in
* {@link ORDER}. This sorts the {@code map}.
* @param map the {@link LinkedHashMap} to sort
* @param sort sort on the key or value
* @param order sort forward or reverse
*/
public static void sortSI(LinkedHashMap<String, Integer> map,
final SORT sort, final ORDER order) {
// convert to a list and sort
List list = new ArrayList(map.entrySet());
Collections.sort(list, new Comparator() {
@Override
public int compare(Object o1, Object o2) {
if (sort == SORT.KEY) {
return (order == ORDER.FORWARD) ?
((Comparable)((Map.Entry)o1).getKey())
.compareTo(((Map.Entry)o2).getKey())
:
((Comparable)((Map.Entry)o2).getKey())
.compareTo(((Map.Entry)o1).getKey());
} else {
int i1 = (Integer)((Map.Entry)o1).getValue();
int i2 = (Integer)((Map.Entry)o2).getValue();
if (i1 > i2) {
if(order == ORDER.FORWARD) return 1;
else return -1;
} else if (i1 < i2) {
if (order == ORDER.FORWARD) return -1;
else return 1;
} else return 0;
}
}
});
// put sorted list back into map
map.clear();
for (Iterator it = list.iterator(); it.hasNext();) {
Map.Entry entry = (Map.Entry) it.next();
map.put((String)entry.getKey(), (Integer)entry.getValue());
}
// clean up
list = null;
}
}Test Class
Below is a sample class for using these sort function.
import blog.SortLHM.ORDER;
import blog.SortLHM.SORT;
import edu.uiowa.icts.ray.systemutils.Memory;
import edu.uiowa.icts.ray.systemutils.SystemUtils;
import edu.uiowa.icts.ray.systemutils.Timer;
import java.security.SecureRandom;
import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.Map;
public class SortLHMTest {
public static void main(String[] args) {
SortLHMTest t = new SortLHMTest();
// String/String
t.sortSSStreamTest(); // Java 1.8+ only
t.sortSSStreamNewTest(); // Java 1.8+ only
t.sortSSTest();
// String/Integer
t.sortSIStreamTest(); // Java 1.8+ only
t.sortSIStreamNewTest(); // Java 1.8+ only
t.sortSITest();*/
}
/**
* Sorts a {@code String/String} {@link LinkedHashMap} using a stream. This
* is only available in Java 1.8+.
*/
private void sortSSStreamTest() {
System.out.println("----- String/String stream -----");
LinkedHashMap<String, String> map = new LinkedHashMap<String, String>();
map.put("AAA", "ZZZ"); // 1, 5
map.put("ABA", "ZXC"); // 2, 4
map.put("BCA", "DFD"); // 4, 3
map.put("BBA", "AAA"); // 3, 1
map.put("CDA", "ASD"); // 5, 2
// forward key stream (does not alter map)
System.out.println("Forward key stream");
SortLHM.sortSS_Stream(map, SORT.KEY, ORDER.FORWARD);
print(map);
// reverse key stream (does not alter map)
System.out.println("\nReverse key stream");
SortLHM.sortSS_Stream(map, SORT.KEY, ORDER.REVERSE);
print(map);
// forward value stream (does not alter map)
System.out.println("\nForward value stream");
SortLHM.sortSS_Stream(map, SORT.VALUE, ORDER.FORWARD);
print(map);
// reverse value stream (does not alter map)
System.out.println("\nReverse value stream");
SortLHM.sortSS_Stream(map, SORT.VALUE, ORDER.REVERSE);
print(map);
}
/**
* Sorts a {@code String/String} {@link LinkedHashMap} using a stream. This
* is only available in Java 1.8+.
*/
private void sortSSStreamNewTest() {
System.out.println("----- String/String new stream -----");
LinkedHashMap<String, String> map = new LinkedHashMap<String, String>();
map.put("AAA", "ZZZ"); // 1, 5
map.put("ABA", "ZXC"); // 2, 4
map.put("BCA", "DFD"); // 4, 3
map.put("BBA", "AAA"); // 3, 1
map.put("CDA", "ASD"); // 5, 2
// forward key stream (does not alter map)
System.out.println("Forward key stream");
LinkedHashMap<String, String> lhm =
SortLHM.sortSS_Stream_New(map, SORT.KEY, ORDER.FORWARD);
print(lhm);
// reverse key stream (does not alter map)
System.out.println("\nReverse key stream");
lhm = SortLHM.sortSS_Stream_New(map, SORT.KEY, ORDER.REVERSE);
print(lhm);
// forward value stream (does not alter map)
System.out.println("\nForward value stream");
lhm = SortLHM.sortSS_Stream_New(map, SORT.VALUE, ORDER.FORWARD);
print(lhm);
// reverse value stream (does not alter map)
System.out.println("\nReverse value stream");
lhm = SortLHM.sortSS_Stream_New(map, SORT.VALUE, ORDER.REVERSE);
print(lhm);
}
/**
* Sorts a {@code String/String} {@link LinkedHashMap}.
*/
private void sortSSTest() {
System.out.println("\n----- String/String non-stream -----");
LinkedHashMap<String, String> map = new LinkedHashMap<String, String>();
map.put("AAA", "ZZZ"); // 1, 5
map.put("ABA", "ZXC"); // 2, 4
map.put("BCA", "DFD"); // 4, 3
map.put("BBA", "AAA"); // 3, 1
map.put("CDA", "ASD"); // 5, 2
// forward key stream (alters map)
System.out.println("Forward key");
SortLHM.sortSS(map, SORT.KEY, ORDER.FORWARD);
print(map);
// reverse key stream (alters map)
System.out.println("\nReverse key");
SortLHM.sortSS(map, SORT.KEY, ORDER.REVERSE);
print(map);
// forward value stream (alters map)
System.out.println("\nForward value");
SortLHM.sortSS(map, SORT.VALUE, ORDER.FORWARD);
print(map);
// reverse value stream (alters map)
System.out.println("\nReverse value");
SortLHM.sortSS(map, SORT.VALUE, ORDER.REVERSE);
print(map);
}
/**
* Sorts a {@code String/Integer} {@link LinkedHashMap} using a stream. This
* is only available in Java 1.8+.
*/
private void sortSIStreamTest() {
System.out.println("\n----- String/Integer stream -----");
LinkedHashMap<String, Integer> map = new LinkedHashMap<String, Integer>();
map.put("AAA", 5); // 1, 5
map.put("ABA", 4); // 2, 4
map.put("BCA", 3); // 4, 3
map.put("BBA", 1); // 3, 1
map.put("CDA", 2); // 5, 2
System.out.println("Forward key stream: " + map.size());
SortLHM.sortSI_Stream(map, SORT.KEY, ORDER.FORWARD);
print(map);
// reverse key stream (does not alter map)
System.out.println("\nReverse key stream");
SortLHM.sortSI_Stream(map, SORT.KEY, ORDER.REVERSE);
print(map);
// forward value stream (does not alter map)
System.out.println("\nForward value stream");
SortLHM.sortSI_Stream(map, SORT.VALUE, ORDER.FORWARD);
print(map);
// reverse value stream (does not alter map)
System.out.println("\nReverse value stream");
SortLHM.sortSI_Stream(map, SORT.VALUE, ORDER.REVERSE);
print(map);
}
/**
* Sorts a {@code String/Integer} {@link LinkedHashMap} using a stream. This
* is only available in Java 1.8+.
*/
private void sortSIStreamNewTest() {
System.out.println("\n----- String/Integer new stream -----");
LinkedHashMap<String, Integer> map = new LinkedHashMap<String, Integer>();
map.put("AAA", 5); // 1, 5
map.put("ABA", 4); // 2, 4
map.put("BCA", 3); // 4, 3
map.put("BBA", 1); // 3, 1
map.put("CDA", 2); // 5, 2
System.out.println("Forward key stream: " + map.size());
LinkedHashMap<String, Integer> lhm =
SortLHM.sortSI_Stream_New(map, SORT.KEY, ORDER.FORWARD);
print(lhm);
// reverse key stream (does not alter map)
System.out.println("\nReverse key stream");
lhm = SortLHM.sortSI_Stream_New(map, SORT.KEY, ORDER.REVERSE);
print(lhm);
// forward value stream (does not alter map)
System.out.println("\nForward value stream");
lhm = SortLHM.sortSI_Stream_New(map, SORT.VALUE, ORDER.FORWARD);
print(lhm);
// reverse value stream (does not alter map)
System.out.println("\nReverse value stream");
lhm = SortLHM.sortSI_Stream_New(map, SORT.VALUE, ORDER.REVERSE);
print(lhm);
}
/**
* Sorts a {@code String/Initeger} {@link LinkedHashMap}.
*/
private void sortSITest() {
System.out.println("\n----- String/Integer non-stream -----");
LinkedHashMap<String, Integer> map = new LinkedHashMap<String, Integer>();
map.put("AAA", 5); // 1, 5
map.put("ABA", 4); // 2, 4
map.put("BCA", 3); // 4, 3
map.put("BBA", 1); // 3, 1
map.put("CDA", 2); // 5, 2
// forward key stream (does not alter map)
System.out.println("Forward key stream");
SortLHM.sortSI(map, SORT.KEY, ORDER.FORWARD);
print(map);
// reverse key stream (does not alter map)
System.out.println("\nReverse key stream");
SortLHM.sortSI(map, SORT.KEY, ORDER.REVERSE);
print(map);
// forward value stream (does not alter map)
System.out.println("\nForward value stream");
SortLHM.sortSI(map, SORT.VALUE, ORDER.FORWARD);
print(map);
// reverse value stream (does not alter map)
System.out.println("\nReverse value stream");
SortLHM.sortSI(map, SORT.VALUE, ORDER.REVERSE);
print(map);
}
/**
* Prints a {@link LinkedHashMap}.
* @param map {@link LinkedHashMap} to print
*/
private void print(LinkedHashMap map){
Iterator<Map.Entry> it = map.entrySet().iterator();
while(it.hasNext()){
Map.Entry entry = it.next();
System.out.println(entry.getKey() + "=" + entry.getValue());
}
}
}Stream vs Comparator
I’ve been using the comparator approach for many years now, but decided to switch over to streams due to its benefits (e.g., parallelization and nesting capabilities). However, I wasn’t sure how doing so would affect time and heap space allocation. Therefore, I performed a few scaled tests with the following setup:
- Collection:
LinkedHashMap– this requires less memory thanString/String, thus allowing for greater scaling - Size: 1, 2, 5, 7, 10, 12, and 15 million
- Iterations: 10
- Measured: Java heap size and execution time
- Significance test: two-tailed independent t-test with p < 0.05
The output for experiments can be found in the charts below.
While the differences appear negligible from the charts, there are actually some statistically significant results to discuss. For size, streaming-replace and non-streaming are significantly smaller than streaming-new at p < 0.0001 for 2+ million. There is no significant difference between streaming-replace and non-streaming. In terms of time, streaming-replace is significantly faster than streaming-new at p < 0.00001 for 1, 5, 7, and 15 million, and not for 2, 10, and 12 million. For 7+ million, non-streaming is significantly faster than streaming-replace at p < 0.0001 or better. Non-streaming is also faster than streaming-new for all reported sizes at p < 0.001 or better.
So, what does these results suggest. Quite simply, non-streaming consumes the same size as streaming-replace, yet requires less time. Thus, I’m going to stick with the non-streaming implementation for now.