Java 8 Streams: Sorting List and Maps

Photo by nousnou iwasaki on Unsplash

The streams API in Java 8 allows you to perform functional-style operations on a series of elements. You can perform filtering, sorting, transformations and reduce on different collections. Streams have the following properties:

1. It is not a data storage. It refers to the elements from a source from a computational pipeline.
2. Functional. Operations performed on streams does not modify the source. It creates intermediate streams that flow downstream.
3. Intermediate operations are lazy. We will define intermediate operations later.
4. Can be infinite. Streams can have no boundaries, although terminal operations can complete the operation. We will define terminal operations later.

Stream Operations

There are two types of stream operations, intermediate and terminal. Intermediate operations return a new stream. This allows for further chaining of operations. Intermediate operations are lazy, meaning, they are not processed immediately. It will only create a new stream. Terminal operations traverses the stream. When a terminal operation is performed, the stream is considered consumed and can not be used anymore. Terminal operations either returns a void or a non-stream result, so further chaining is impossible.

Stream sources

Stream can be obtained from the following:

1. Using the stream and parallelStream method of Collection
2. From an array using the Arrays.stream method
3. From static factory methods such as Stream.of, Intstream.range, etc.
4. From BufferedReader and Files

Stream type

There are two types of stream, sequential and parallel stream. As the name implies, parallel streams allows you to process operations on multiple thread. They are more efficient in terms of performance. For now, we will focus on sequential streams.

Intermediate Operations

Let us try and experiment on some intermediate functions. First, let us prove the laziness of intermediate operations. Take a look at the example below.

Note: Streams are available in API 24 and beyond.

Running this code will not output anything in logcat. This is because filter is an intermediate operation. It is lazy, and will only traverse the list until a terminating operation is chained. Now let us append a terminating operation.

Running this code will output the following:

D/Lazy test: Filtering: 1
D/Lazy test: Filtering: 2
D/Lazy test: Filtering: 3
D/Lazy test: Filtering: 4
D/Lazy test: Filtering: 5
D/Lazy test: Filtering: 6
D/Lazy test: foreach: 6
D/Lazy test: Filtering: 7
D/Lazy test: foreach: 7
D/Lazy test: Filtering: 8
D/Lazy test: foreach: 8
D/Lazy test: Filtering: 9
D/Lazy test: foreach: 9
D/Lazy test: Filtering: 10
D/Lazy test: foreach: 10

Filter returns a new stream that satisfies the predicate. Notice that each element in the stream traverses the entire chain one by one. This is a stateless operation. It means the operation is performed vertically.

Now let’s take a look at another stateless operation called map. This is a very useful operation as it allows you to transform the stream into another type.

In the code above, we transform an integer element into a string. After the map, the downstream will be receiving a string stream already. Running this will output this log:

D/Map test: foreach: Element1
D/Map test: foreach: Element2
D/Map test: foreach: Element3
D/Map test: foreach: Element4
D/Map test: foreach: Element5
D/Map test: foreach: Element6
D/Map test: foreach: Element7
D/Map test: foreach: Element8
D/Map test: foreach: Element9
D/Map test: foreach: Element10

This next example is a stateful operation. Unlike stateless, they are processed horizontally before emitting the elements. Check the code below.

Sorted sorts the input stream and then outputs the sorted stream. Sorting is a stateful operation as it requires the knowledge of the the entire stream before it can output a sorted stream. It process the stream horizontally first before it propagates to the next operation. It does not modify the original stream however. It creates an intermediate one. Check the result:

D/Sort test: Input1: y2 Input2: z1
D/Sort test: Input1: x3 Input2: y2
D/Sort test: Input1: w4 Input2: x3
D/Sort test: foreach: w4
D/Sort test: foreach: x3
D/Sort test: foreach: y2
D/Sort test: foreach: z1

The original stream was exhausted first, before the next operation in the chain was executed.

When working with streams, it is important to consider that the order of operations matter. Let’s see why by introducing an example.

In our first example, we sorted the stream first before filtering. By now, you are already familiar that sorted is a horizontal operation. It will sort the entire stream first, before sending it to filter. The entire sequence goes like this.

D/Sort test: Input1: 2 Input2: 1
D/Sort test: Input1: 3 Input2: 2
D/Sort test: Input1: 4 Input2: 3
D/Sort test: Input1: 5 Input2: 4
D/Sort test: Input1: 6 Input2: 5
D/Sort test: Input1: 7 Input2: 6
D/Sort test: Input1: 8 Input2: 7
D/Sort test: Input1: 9 Input2: 8
D/Sort test: Input1: 10 Input2: 9
D/Filter test: Filtering: 1
D/Filter test: Filtering: 2
D/Filter test: Filtering: 3
D/Filter test: Filtering: 4
D/Filter test: Filtering: 5
D/Filter test: Filtering: 6
D/Order Test: foreach: 6
D/Filter test: Filtering: 7
D/Order Test: foreach: 7
D/Filter test: Filtering: 8
D/Order Test: foreach: 8
D/Filter test: Filtering: 9
D/Order Test: foreach: 9
D/Filter test: Filtering: 10
D/Order Test: foreach: 10

Now let us try to reverse the process.

This will output:

D/Filter test: Filtering: 1
D/Filter test: Filtering: 2
D/Filter test: Filtering: 3
D/Filter test: Filtering: 4
D/Filter test: Filtering: 5
D/Filter test: Filtering: 6
D/Filter test: Filtering: 7
D/Filter test: Filtering: 8
D/Filter test: Filtering: 9
D/Filter test: Filtering: 10
D/Sort test: Input1: 7 Input2: 6
D/Sort test: Input1: 8 Input2: 7
D/Sort test: Input1: 9 Input2: 8
D/Sort test: Input1: 10 Input2: 9
D/Order Test: foreach: 6
D/Order Test: foreach: 7
D/Order Test: foreach: 8
D/Order Test: foreach: 9
D/Order Test: foreach: 10

Notice the difference? If we count the number of logs as operations, it can be seen that the second approach is much efficient. This is because we filtered the input to sorted first. Since sorted is a horizontal operation, it needs the entire stream first. If we limit the input to sorted, we optimize the pipeline.

Terminal Operators

Before going to terminal operators, let us briefly check the Optional object. Optional is a wrapper object that can contain a null or non-null value. It is important in streams as it may sometimes not satisfy the terminating condition.

We already discussed one terminal operator, the foreach. It iterates across the entire stream. Now let’s check out some basic terminal operators.

The findFirst operator finds the first element of the stream and returns an optional. It is a short-circuiting terminal operator as it terminates the pipeline if it is satisfied. It’s output goes like this:

D/Peek test: Element: 1
D/Find first test: First element: 1

Notice that the stream was not traversed pass the first element anymore as findFirst was already satisfied. There are other short-circuiting operations such as findAny, limit, anyMatch, etc, and I encourage you to explore them.

Now we explore a very useful terminal operation that can transform a stream into a collection. The operation is called collect. Collect is a mutable reduction operation that accumulates all the elements of the stream and stores them in a mutable container such as a List or a Map. The collect operation requires three functions:

1. Supplier — constructs new instances of the result container
2. Accumulator — incorporates the input element into a result container
3. Combiner — merge contents of one result container into another

I know this might sound complicated at first but you will hardly implement those functions. Java 8 provides various built-in implementation of collectors.

Here are some of the available collectors defined in Collectors class.

The Collectors.toList collects the stream elements and outputs a List. The above function will output:

D/List test: [aaa, aab, aac, aba, abb, abc, aca, acb, acc]

Another useful collector is the Collectors.toMap. Like the toList, it outputs a collection but this time, a Map.

Collectors.toMap has an overload that takes 3 parameters. The first one is how to determine the key of the entry. In our example, we used the first character of each string as Key. The next parameter is how to determine the value. We used the input string as is for value. The last one is a merge function. This is where we define the conflict resolution policy. In our case, we just append the value to the original value. This will return a Map with both key and value as strings. This will output:

D/Map test: {a=aaa aab aac aba abb abc aca acb acc, b=baa bab bac bba bbb bbc bca bcb bcc}

There are other interesting collectors such as Collectors.groupingBy which allows you to group the inputs and return a map. You can check them in the official documentation. You can also implement your own collectors if you wish.

Sorting List and Maps

Now we go to our original goal of sorting Lists and Maps. List sorting is pretty straightforward.

We initialize the source stream, call sorted, and collect as List. If a different sorting rule is required, the sorted has an overload that accepts a comparator. Running this code will output:

D/Sort list test: [aaa, aab, aac, aba, abb, abc, aca, acb, acc, baa, bab, bac, bba, bbb, bbc, bca, bcb, bcc]

Now we go to sorting Maps. Maps can be sorted in two ways, by key and by value. This is difficult to perform pre-Java 8. This is how it is done using streams.

First we initialize a map with random values. Then we convert this to stream by first taking the entrySet. The stream will be of type

Map.Entry<Integer, String>

Remember we can pass a custom comparator in sorted so we pass the Map.Entry.comparingByKey. This is a predefined comparator that compares the key in Map.Entry. Now we collect the elements using toMap and specifying the functions. Map.Entry::getKey supplies the key, Map.Entry.getValue supplies the value, the conflict resolution policy will return the first value. The last parameter is something new. It is called the map supplier. It will return this type of map as a container. It is important for us to specify LinkedHashMap because we want to preserve the ordering of entries.

Note: If you are not familiar with the :: operator, it is called the Method Reference operator. It is a reference to a method by name. They are used to simplify cases wherein a lambda function just call an existing method. For more information, check the documentation here.

Now let us try to run the above code.

D/Sort map test: Raw input: {64=Element10, 0=Element43, 67=Element26, 4=Element90, 36=Element4, 5=Element61, 6=Element39, 9=Element12, 41=Element43, 49=Element44, 81=Element14, 18=Element64, 83=Element85, 52=Element19, 25=Element62, 26=Element32, 59=Element33, 27=Element61}
D/Sort map test: Sorted: {0=Element43, 4=Element90, 5=Element61, 6=Element39, 9=Element12, 18=Element64, 25=Element62, 26=Element32, 27=Element61, 36=Element4, 41=Element43, 49=Element44, 52=Element19, 59=Element33, 64=Element10, 67=Element26, 81=Element14, 83=Element85}

Now our map is beautifully sorted by key. Let’s try sorting by value.

The code is basically the same. We just changed the comparingByKey to comparingByValue. Running this code yields this output:

D/Sort map test: Raw input: {1=Element93, 65=Element69, 35=Element33, 36=Element80, 7=Element91, 9=Element96, 46=Element57, 79=Element74, 16=Element29, 48=Element79, 84=Element63, 52=Element18, 54=Element70, 56=Element65, 57=Element72, 92=Element49, 62=Element27, 94=Element0}
D/Sort map test: Sorted: {94=Element0, 52=Element18, 62=Element27, 16=Element29, 35=Element33, 92=Element49, 46=Element57, 84=Element63, 56=Element65, 65=Element69, 54=Element70, 57=Element72, 79=Element74, 48=Element79, 36=Element80, 7=Element91, 1=Element93, 9=Element96}

That’s it for the primer to Java 8 streams. Sorting has never been this easy right?