Java 8: A quick introduction to Parallelism and the Spliterator

java-8-parellelism-spliterator

With the release of Java 8 a number of new language features were introduced [1]. These included lambda functionsstreamsand completable futures. Colleagues of mine have already reviewed these features in previous articles on this blog, which I recommend reading as part of this topic [2][3]. In this article I will touch on an aspect of the Java 8 release that relates to the push towards exploiting parallelism, in the context of the existing Collections Framework – specifically the new Spliterator interface.

Due to the size and complexity of these topics, it will only be possible to provide a high-level introduction, but it is hoped that this will trigger interest in the reader, to go off and delve further into an area of growing importance and interest.

Parallelism

First thing first – what is meant by the term ‘parallelism’? For the purpose of this article, at a high level, it is a term that refers to programming in a way to exploit multi-core CPU units. That is to say, to take a piece of work (a task) and break it out into separate units (sub-tasks) that can be processed in parallel. Then aggregating the results of all the processed units to complete the original work [4]. This is sufficient for now, although the reader might want to investigate further on differences between parallelism, concurrency and sequential programming.

Figure 1

For this to be successful, the processing on a unit should not have a dependency on any other unit – this processing should be stateless and also should not depend on the result of the processing of any other unit. This is important when it comes to the data that is involved – as parallel computing lends itself to situations where vast amounts of data is to be handled.

This also raises the question of when to go for parallelism – there is an overhead in the added complexity of identifying and breaking out the units of work and then coordinating the parallel processing. Then there is also the issue of latency in reading the data – the savings found in using parallel cores for processing is to try to keep each CPU core busy all the time – which requires reading data as and when is needed without delay. Before embarking on a parallel processing architecture, some cost-benefit analysis is required to be sure that this is the right approach.

With the introduction of Java 8 Oracle was aiming to make it more attractive and simpler for developers to use Java in parallel programming. The inclusion of features such as lambda functions and the Streams API was to be seen as part of this push [5]. How successful that becomes, time will tell.

This concept of parallelism is behind the existing fork/join framework found in Java, which will be covered in a future article, but for now we will confine our overview to the new Spliteratorinterface, found in the java.util library.

Collections Framework

The Collections Framework is also found in the java.util library, and provides a range of classes that act as containers to hold objects (technically, references to the objects) and allow useful behaviour such as adding new objects, searching the container for a particular object, and the sorting of such objects – the behaviour available is depending on the type of container used [6].

Within the library there are two different concepts of containers, captured in the core interfaces, that are defined within the framework [7]. One concept is that of a Collection that is a sequence of individual elements, which is further refined by extending the Collectioninterface with interfaces for ListSetQueue or Deque.

Listing 1 – Simple Iterator on an ArrayList

// Create a new Collection type; in this case an ArrayList Collection<Person> people = new ArrayList<Person>(); // Add some people using Person objects people.add(new Person("Jane", "Doe", "Ireland")); people.add(new Person("Joe", "Doe", "England")); people.add(new Person("John", "Doe", "Scotland")); people.add(new Person("Julie", "Doe", "Wales")); people.add(new Person("Jerry", "Doe", "France")); people.add(new Person("Jim", "Doe", "Italy")); // simple iterator example Iterator<Person> peopleIterator = people.iterator(); while(peopleIterator.hasNext()) { Person person = peopleIterator.next(); System.out.println("Hello " + person.getFirst_name() + " " + person.getLast_name() + " from " + person.getCountry()); }

The output is:

Hello Jane Doe from Ireland Hello Joe Doe from England Hello John Doe from Scotland Hello Julie Doe from Wales Hello Jerry Doe from France Hello Jim Doe from Italy

Separately, there is the concept of a container, defined in the Map interface, holding a group of key-value object pairs, which allow the use of a key to find a value – in this way an object (value) can be found using another object (key) that has been mapped to it.

Both the interfaces of Collection and Map are found in the Collections Framework, in java.util, along with a class called Collections. Note that the Collections class consists exclusively of static methods, which include polymorphic algorithms, that operate on or return collections.

Paralellism and the Collections Framework

A problem with using the containers of the Collections Framework in some form of parallel programming is that these containers are not thread-safe. Wrappers are provided for adding automatic synchronization (thread safety) but the drawback is that this introduces thread contention, where two or more threads are trying to access the same resource simultaneously and therefore cause the runtime to either suspend their execution or execute them more slowly.

The Spliterator

A new interface added to java.util is the Spliterator, which as the name implies, is a new special kind of Iterator that can traverse a Collection[8]. For Java 8, the Collection interface has been updated to include a new spliterator() method, that when called returns a Spliterator. This is not the case for the separate Map interface, although it is considered part of the Collections Framework as explained above.

The Spliterator can ‘split’ the Collection, partitioning off some of its elements as another Spliterator. This does allow parallel processing of different parts of a Collection but note that the Spliterator itself does not provide the parallel processing behaviour. Instead, the Spliteratoris there to support parallel traversal of the suitably partitioned parts of a Collection. This solves the problem of dividing the data, as held in a Collection such as an ArrayList, into suitably sized sub-units that can be processed in parallel.

The fork/join framework, which is found in Java 7 libraries, can be used with the Spliteratorand is designed for parallelizable work that can be broken into smaller pieces recursively to be processed independently, and then aggregating the results of the sub-units to produce a final result. Again, however note that using the Spliterator is not dependant on the fork/join framework, this framework is just one way of implementing parallel processing [9].

Listing 2 – Simple Spliterator on an ArrayList

The following code gives us an ArrayList, called people that is to hold objects of the Persontype – a user defined type:

Collection<Person> people = new ArrayList<Person>();

The ‘people’ collection then has a number of objects added, and we can now call on the spliterator() of the ArrayList:

Spliterator<Person> peopleSpliterator = people.spliterator();

This returns a Spliterator we are calling ‘peopleSpliterator’.

System.out.println(" " + peopleSpliterator.characteristics()); System.out.println(" " + peopleSpliterator.estimateSize());

The output from the above code is :

16464 
6

The value 16464 represents the characteristics of the Spliterator partition. This is important as it is these predefined characteristics that result in what ends up in each new partition and how it is structured. The int value returned from the characteristics() call is the result of the OR’ed values of the individual characteristics for an ArrayList, which is ORDEREDSORTED and SUBSIZED[10].

ORDERED indicates that the elements have a defined order, which is expected from a List, when traversing and partitioning them. SORTED means that the elements follow a predefined sort order while SUBSIZED indicates that this and any further resulting Spliterator are SIZEDSIZED means the Spliterator has been created from a source with a known size. The details of the characteristics for a particular Collection type can be found in the online API documentation. Where you wish to have a collection with non-standard characteristics, that means going down the route of implementing your own version of the Spliterator interface.

Listing 3 – Split the Spliterator

Now that we have a Spliterator, lets ‘split’ it:

Spliterator<Person> newPartition = peopleSpliterator.trySplit(); System.out.println(" " + newPartition.estimateSize()); System.out.println(" " + peopleSpliterator.estimateSize());

The output from this code is:

3 
3

As you can see we have a new partition with 3 elements, leaving the existing partition with 3. The important method of trySplit() has partitioned the elements of the original Spliterator – in this case split it evenly, leaving the existing Spliterator with a reduced number of elements in its own partition. Clearly this is very different from the behaviour of the pre-existing Iterator.

If this Spliterator can be split (partitioned), the method will try to divide the elements in half for a balanced parallel computation. This will not always be the case, and where a Spliteratorcannot be split, a null is returned. The splitting, or partitioning, can continue recursively until a Spliterator returns null. If a different behaviour is required in how the trySplit() method works, then again a custom implementation of the Spliterator interface is required.

When used in a parallel programming solution, bear in mind that the individual Spliterator is not thread safe; instead the parallel processing implementation must insure that each individual Spliterator is handled by one thread at a time. A thread calling the trySplit() of a Spliterator, may hand over the returned new Spliterator to a separate thread for processing. This follows the idea of decomposition of a larger task into smaller sub-tasks that can be processed in parallel individually of each other.

When working with a Spliterator, especially in a parallel programming environment, changes to the data structure that is undergoing processing can lead to arbitrary and unknown behaviour and that is not good. Ideally the original data source should not be interfered with (no elements added, replaced or removed). Collection types are not immutable and cannot manage concurrent modifications. To help with this problem, for the ArrayList, the trySplit() returns a ‘late-binding’ and ‘fast-fail’ Spliterator. This late-binding binds the elements to the Spliteratoron first split, first traversal or first query for estimated size rather then at the time of the creation of the Spliterator. After this binding occurs any interference with the elements is then detected, throwing a ConcurrentModificationException. Here, it fails-fast, rather then risking arbitrary and non-deterministic behaviour at a future time.

Of course with the above trivial example of only 6 elements in the list, this is hardly a work load that would justify parallel programming – but as mentioned before, Spliterator itself does not provide the parallel programming behaviour – the reader might be interested in experimenting with a Collection type holding a vastly larger number of objects and then look to implement a parallel processing solution to exploit the use of the Spliterator. A suggestion is that such a solution may incorporate the fork/join framework and/or the Stream API.

Future articles will delve further into this interesting and increasingly important area.

What Does RandomAccess Mean?

RandomAccess is a marker interface, like the Serializable and Cloneable interfaces. All these marker interfaces do not define methods. Instead, they identify a class as having a particular capability. In the case of Serializable, the interface specifies that if the class is serialized using the serialization I/O classes, a NotSerializableException will not be thrown (unless the object contains some other class that cannot be serialized). Cloneable similarly indicates that the use of the Object.clone( ) method for a Cloneable class will not throw aCloneNotSupportedException.

The RandomAccess interface identifies that a particular java.util.List implementation has fast random access. (A more accurate name for the interface would have been “FastRandomAccess.”) This interface tries to define an imprecise concept: what exactly is fast? The documentation provides a simple guide: if repeated access using the List.get( ) method is faster than repeated access using the Iterator.next( ) method, then the List has fast random access. The two types of access are shown in the following code examples.

Repeated access using List.get( ):

Object o;
for (int i=0, n=list.size(  ); i < n; i++)
  o = list.get(i);

Repeated access using Iterator.next( ):

Object o;
for (Iterator itr=list.iterator(  ); itr.hasNext(  ); )
  o = itr.next(  );

A third loop combines the previous two loops to avoid the repeated Iterator.hasNext( ) test on each loop iteration:

Object o;
Iterator itr=list.iterator(  );
for (int i=0, n=list.size(  ); i < n; i++)
  o = itr.next(  );

This last loop relies on the normal situation where List objects cannot change in size while they are being iterated through without an exception of some sort occurring. So, because the loop size remains the same, you can simply count the accessed elements without testing at each iteration whether the end of the list has been reached. This last loop is generally faster than the previous loop with the Iterator.hasNext( ) test. In the context of the RandomAccess interface, the first loop using List.get( ) should be faster than both the other loops that use Iterator.next( ) for a list to implement RandomAccess.

How Is RandomAccess Used?

So now that we know what RandomAccess means, how do we use it? There are two aspects to using the other marker interfaces, Serializable and Cloneable: defining classes that implement them and using their capabilities via ObjectInput /ObjectOutput and Object.clone( ), respectively.RandomAccess is a little different. Of course, we still need to decide whether any particular class implements it, but the possible classes are severely restricted: RandomAccess should be implemented only in java.util.List classes. And most such classes are created outside of projects. The SDK provides the most frequently used implementations, and subclasses of the SDK classes do not need to implement RandomAccess because they automatically inherit the capability where appropriate.

The second aspect, using the RandomAccess capability, is also different. Whether a class is Serializable or Cloneable is automatically detected when you use ObjectInput/ObjectOutput and Object.clone( ). But RandomAccess has no such automatic support. Instead, you need to explicitly check whether a class implements RandomAccess using the instanceof operator:

if (listObject instanceof RandomAccess)
  ...

You must then explicitly choose the appropriate access method, List.get( ) or Iterator.next( ). Clearly, if we test for RandomAccess on every loop iteration, we would be making a lot of redundant calls and probably losing the benefit of RandomAccess as well. So the pattern to follow in usingRandomAccess makes the test outside the loop. The canonical pattern looks like this:

Object o;
if (listObject instanceof RandomAccess)
{
  for (int i=0, n=list.size(  ); i < n; i++)
  {
    o = list.get(i);
    //do something with object o
  }
   
}
else
{
  Iterator itr = list.iterator(  );
  for (int i=0, n=list.size(  ); i < n; i++)
  {
    o = itr.next(  );
    //do something with object o
   
  }
}

Speedup from RandomAccess

I tested the four code loops shown in this section, using the 1.4 release, separately testing the -client (default) and -server options. To test the effect of the RandomAccess interface, I used the java.util.ArrayList and java.util.LinkedList classes. ArrayList implements RandomAccess, while LinkedList does not. ArrayList has an underlying implementation consisting of an array with constant access time for any element, so using the ArrayList iterator is equivalent to using the ArrayList.get( ) method but with some additional overhead. LinkedList has an underlying implementation consisting of linked node objects with access time proportional to the shortest distance of the element from either end of the list, whereas iterating sequentially through the list can shortcut the access time by traversing one node after another.

Times shown are the average of three runs, and all times have been normalized to the first table cell, i.e., the time taken by the ArrayList to iterate the list using the List.get( ) method in client mode.

Loop type (loop test) and access method

ArrayList java -client

LinkedList java -client

ArrayList java -server

LinkedList java -server

loop counter (i<n) and List.get( )

100%

too long

77.5%

too long

iterator (Iterator.hasNext( )) and Iterator.next( )

141%

219%

109%

213%

iterator (i<n) and Iterator.next( )

121%

205%

98%

193%

RandomAccess test with loop from row 1 or 3

100%

205%

77.5%

193%

The most important results are in the last two rows. The last line shows the times obtained by making full use of the RandomAccess interface, and the line before that shows the most optimal general technique for iterating lists if RandomAccess is not available. The size of the lists I used for the test (and consequently the number of loop iterations required to access every element) was sufficiently large that the instanceof test had no measurable cost in comparison to the time taken to run the loop. Consequently, we can see that there was no cost (but also no benefit) in adding the instanceofRandomAccess test when iterating the LinkedList, whereas the ArrayList was iterated more than 20% quicker when the instanceof test was included.

Forward and Backward Compatibility

Can you use RandomAccess and maintain backward compatibility with VM versions prior to 1.4? There are three aspects to using RandomAccess:

  • You may want to include code referencing RandomAccess without moving to 1.4.

  • Many projects need their code to be able to run in any VM, so the code needs to be backward-compatible to run in VMs using releases earlier than 1.4, where RandomAccess does not exist.

  • You will want to make your code forward-compatible so that it automatically takes advantage of RandomAccess when running in a 1.4+ JVM.

Making RandomAccess available to your development environment is the first issue, and if you are using an environment prior to 1.4, this can be as simple as adding the RandomAccess interface to your classpath. Any version of the SDK can create the RandomAccess interface. The definition for RandomAccess is:

package java.util;
public interface RandomAccess {  }

We also need to handle RandomAccess in the runtime environment. For pre-1.4 environments, the test:

if (listObject instanceof RandomAccess)

generates a NoClassDefFoundError at runtime when the JVM tries to load the RandomAccess class (for the instanceof test to be evaluated, the class has to be loaded). However, we can guard the test so that it is executed only if RandomAccess is available. The simplest way to do this is to check whether RandomAccess exists, setting a boolean guard as the outcome of that test:

static boolean RandomAccessExists;
...
   
  //execute this as early as possible after the application starts
  try
  {
    Class c =  Class.forName("java.util.RandomAccess");
    RandomAccessExists = true;
  }
  catch (ClassNotFoundException e)
  {
    RandomAccessExists = false;
  }

Finally, we need to change our instanceof tests to use the RandomAccessExists variable as a guard:

if (RandomAccessExists && (listObject instanceof RandomAccess) )

With the guarded instanceof test, the code automatically reverts to the Iterator loop if RandomAccess does not exist and should avoid throwing a NoClassDefFoundError in pre-1.4 JVMs. And, of course, the guarded instanceof test also automatically uses the faster loop branch whenRandomAccess does exist and the list object implements it.

Iterator vs ListIterator

In this tutorial we will learn about the difference between Iterator and ListIterator . We will also look at the examples of Iterator and ListIterator one by one. We have already discussed different type of iterators  i.e fail-fast iterator and fail-safe iterator.

Difference between Iterator and ListIterator in Java with Example
 
1. Traversal Direction  :  ListIterator allows the programmers to iterate the list objects in both directions i.e forward as well as backward direction using previous() and next() method.
Iterator can be used to  iterate the list,map and set object in one direction i.e forward.

2.  Set and Map implemented Objects Traversal : ListIterator can be used to traverse List object only . But Iterator can be used to traverse Map, List and Set implemented objects.

for example
// ListIterator object is created
ListIterator listIteratorObject = List.listIterator();
// Iterator object is created
Iterator  iteratorObject  = List.iterator();

3. Add or Set operation at any index : According to ListIterator Oracle docs,
ListIterator can modify the list  during iteration using add(E e) , remove() or set(E e).
Iterator can not add the element during traversal but they can remove the element from the underlying collection during the iteration as they only consist of remove() method. There is no add(E e) and set(E e) method in Iterator.

4. Determine Iterator’s current position :  ListIterator can obtain the iterator’s current position in the list. Iterator’s current position during traversal can not be determined using Iterator.

5. Retrieve Index of the element : ListIterator can obtain the index of the elements using previousIndex(E e) or nextIndex(E e) methods. We can not obtain the index using Iterator as there is no such methods present.

Example of Iterator and ListIterator 

import java.util.Iterator;
import java.util.ListIterator;

public class IteratorListIteratorExample {
public static void main(String[] args) {

List listObject = new ArrayList();
listObject.add(“Alive is awesome”);
listObject.add(“Love yourself”);

ListIterator listIteratorObject = listObject.listIterator();
System.out.println(“ListIterator object output in forward direction:”);
System.out.println(“”);
while( listIteratorObject.hasNext() )
{
System.out.println(listIteratorObject.next());
}

System.out.println(“ListIterator object output in backward direction:”);
System.out.println(“”);
while( listIteratorObject.hasPrevious() )
{
System.out.println(listIteratorObject.previous());
}

List iteratorListObject = new ArrayList();

iteratorListObject.add(“Facebook”);
iteratorListObject.add(“Google”);
iteratorListObject.add(“Apple”);

Iterator javaHungryIterator = iteratorListObject.iterator();
System.out.println(“Iterator object output in forward direction:”);

while( javaHungryIterator.hasNext() )
{
System.out.println(javaHungryIterator.next());
}

}
}

Output :

ListIterator object output in forward direction:
Alive is awesome
Love yourself
ListIterator object output in backward direction:
Love yourself
Alive is awesome
Iterator object output in forward direction:
Facebook
Google
Apple

Similarities between Iterator and ListIterator in Java

1. Interfaces : Both Iterator and ListIterator are interfaces . ListIterator extends Iterator interface.

2. Collection Framework : Both Iterator and ListIterator are member of the Java Collection Framework.

3. Traversal : Both are used to iterate over the collection of objects .

4. Interfaces added to jdk : Both interfaces are added to the jdk in java 1.2

Recap : Difference between Iterator and ListIterator in Java with Example 

ListIterator Iterator
Traversal Direction Both , forward and backward Forward
Objects traversal List only Map, Set and List
Add and Set operations Allows both operations Not possible
Iterator’s current position Yes , can be determined Not possible.
Retrieve Index Yes Not possible

Java SortedMap and TreeMap

This tutorial helps you understand SortedMap with TreeMap implementation in the Java Collections Framework.First, let’s review the API hierarchy. TreeMap doesn’t only implement the Map interface, it also implements the SortedMapand NavigableMap interfaces. Therefore, besides the behaviors inherited from the Map, TreeMap also inherits the behaviors defined by SortedMap and NavigableMap. The following picture depicts the API hierarchy of TreeMap:

TreeMapAPI

1. Understanding SortedMap

The main characteristic of a SortedMap is that, it orders the keys by their natural ordering, or by a specified comparator. So consider using a TreeMap when you want a map that satisfies the following criteria:

  • null key or null value are not permitted.
  • The keys are sorted either by natural ordering or by a specified comparator.

The following example realizes the concept of a SortedMap:

1
2
3
4
5
6
7
8
9
SortedMap<String, String> mapDomains = new TreeMap<>();
mapDomains.put(".com", "International");
mapDomains.put(".us", "United States");
mapDomains.put(".uk", "United Kingdom");
mapDomains.put(".jp", "Japan");
mapDomains.put(".au", "Australia");
System.out.println(mapDomains);

Output:

1
{.au=Australia, .com=International, .jp=Japan, .uk=United Kingdom, .us=United States}

Here, this map contains mappings of domain=country, and as we see in the output, the domains (keys) are sorted by alphabetic order (natural ordering of Strings).

Besides the operations inherited from the Map interface, the SortedMap also defines the following operations:

  • Range view: returns a sub sorted map whose keys fall within a range of keys in the original map.
  • Endpoints: returns the first or last key in the sorted map.
  • Comparator access: returns the comparator (implements the Comparator interface), if any, used to sort the map.

Hence the following code is the definition of a SortedMap:

1
2
3
4
5
6
7
8
public interface SortedMap<K, V> extends Map<K, V>{
    Comparator<? super K> comparator();
    SortedMap<K, V> subMap(K fromKey, K toKey);
    SortedMap<K, V> headMap(K toKey);
    SortedMap<K, V> tailMap(K fromKey);
    K firstKey();
    K lastKey();
}

Let’s look at each type of operation in details. * Range View Operations:+ subMap(K fromKey, K toKey): returns a sorted map whose keys range from fromKey, inclusive, to toKey, exclusive.+ headMap(K toKey): returns a sorted map whose keys are strictly less than toKey.+ tailMap(K fromKey): returns a sorted map whose keys are greater than or equal to fromKey. * Endpoint operations:+ firstKey(): returns the first (lowest) key currently in the map.+ lastKey(): returns the last (highest) key currently in the map. * Comparator access:+ comparator(): returns the comparator used to order the keys in the map, or returns null if this map uses the natural ordering of its keys.

2. SortedMap and TreeMap Examples

The following code example demonstrates how to work with these operations on a TreeMap:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
SortedMap<Integer, String> mapHttpStatus = new TreeMap<>();
mapHttpStatus.put(100, "Continue");
mapHttpStatus.put(200, "OK");
mapHttpStatus.put(300, "Multiple Choices");
mapHttpStatus.put(400, "Bad Request");
mapHttpStatus.put(401, "Unauthorized");
mapHttpStatus.put(402, "Payment Required");
mapHttpStatus.put(403, "Forbidden");
mapHttpStatus.put(404, "Not Found");
mapHttpStatus.put(500, "Internal Server Error");
mapHttpStatus.put(501, "Not Implemented");
mapHttpStatus.put(502, "Bad Gateway");
System.out.println("All key-value pairs: ");
for (Integer code : mapHttpStatus.keySet()) {
    System.out.println(code + " -> " + mapHttpStatus.get(code));
}
System.out.println();
Integer firstKey = mapHttpStatus.firstKey();
String firstValue = mapHttpStatus.get(firstKey);
System.out.println("First status: " + firstKey + " -> " + firstValue);
System.out.println();
Integer lastKey = mapHttpStatus.lastKey();
String lastValue = mapHttpStatus.get(lastKey);
System.out.println("Last status: " + lastKey + " -> " + lastValue);
System.out.println();
SortedMap<Integer, String> map4xxStatus = mapHttpStatus.subMap(400, 500);
System.out.println("4xx Statuses: ");
for (Integer code : map4xxStatus.keySet()) {
    System.out.println(code + " -> " + map4xxStatus.get(code));
}
System.out.println();
SortedMap<Integer, String> mapUnder300Status = mapHttpStatus.headMap(300);
System.out.println("Statuses < 300: ");
for (Integer code : mapUnder300Status.keySet()) {
    System.out.println(code + " -> " + mapUnder300Status.get(code));
}
System.out.println();
SortedMap<Integer, String> mapAbove500Status = mapHttpStatus.tailMap(500);
System.out.println("Statuses > 500: ");
for (Integer code : mapAbove500Status.keySet()) {
    System.out.println(code + " -> " + mapAbove500Status.get(code));
}
Comparator comparator = mapHttpStatus.comparator();
System.out.println("Sorted by natural ordering? " + (comparator == null));

Output:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
All key-value pairs:
100 -> Continue
200 -> OK
300 -> Multiple Choices
400 -> Bad Request
401 -> Unauthorized
402 -> Payment Required
403 -> Forbidden
404 -> Not Found
500 -> Internal Server Error
501 -> Not Implemented
502 -> Bad Gateway
First status: 100 -> Continue
Last status: 502 -> Bad Gateway
4xx Statuses:
400 -> Bad Request
401 -> Unauthorized
402 -> Payment Required
403 -> Forbidden
404 -> Not Found
Statuses < 300:
100 -> Continue
200 -> OK
Statuses > 500:
500 -> Internal Server Error
501 -> Not Implemented
502 -> Bad Gateway
Sorted by natural ordering? true   

And the following example shows how to use a comparator:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
SortedMap<Integer, String> mapHttpStatus = new TreeMap<>(new ReverseComparator());
mapHttpStatus.put(100, "Continue");
mapHttpStatus.put(200, "OK");
mapHttpStatus.put(300, "Multiple Choices");
mapHttpStatus.put(400, "Bad Request");
mapHttpStatus.put(401, "Unauthorized");
mapHttpStatus.put(402, "Payment Required");
mapHttpStatus.put(403, "Forbidden");
mapHttpStatus.put(404, "Not Found");
mapHttpStatus.put(500, "Internal Server Error");
mapHttpStatus.put(501, "Not Implemented");
mapHttpStatus.put(502, "Bad Gateway");
for (Integer code : mapHttpStatus.keySet()) {
    System.out.println(code + " -> " + mapHttpStatus.get(code));
}

Here’s the code of the comparator class:

1
2
3
4
5
class ReverseComparator implements Comparator<Integer> {
    public int compare(Integer num1, Integer num2) {
        return num2.compareTo(num1);
    }
}

Output:

1
2
3
4
5
6
7
8
9
10
11
502 -> Bad Gateway
501 -> Not Implemented
500 -> Internal Server Error
404 -> Not Found
403 -> Forbidden
402 -> Payment Required
401 -> Unauthorized
400 -> Bad Request
300 -> Multiple Choices
200 -> OK
100 -> Continue

As you can see, this comparator sorts the map by the descending order of its keys.In case you are working on Java 8, use Lambda expressions to shorten the comparator code like this:

1
SortedMap<Integer, String> mapHttpStatus = new TreeMap<>((i1, i2) -> i2.compareTo(i1));

Class diagram of Queue API

Queue API is the most complex API in the family of Java Collections Framework. Queue<E> is the base interface for all kind of queues.

  • Sub interfaces: BlockingQueue<E>, Deque<E> and BlockingDeque<E>.
  • Abstract classes: AbstractQueue<E>.
  • Implementation classes:
    • ArrayBlockingQueue<E>
    • ArrayDeque<E>
    • ConcurrentLinkedQueue<E>
    • DelayQueue<E extends Delayed>
    • LinkedBlockingDeque<E>
    • LinkedBlockingQueue<E>
    • LinkedList<E>
    • PriorityBlockingQueue<E>
    • PriorityQueue<E>
    • SynchronousQueue<E>

The following class diagram outlines the hierarchy of Queue API:

Queue API class diagram

Class diagram of Map API

A map stores elements in terms of key=value pair. Map<K, V> is the base interface for all kind of maps.

  • Sub interfaces: ConcurrentMap<K, V>, SortedMap<K, V>, NavigableMap<K, V> and ConcurrentNavigableMap<K, V>.
  • Abstract classes: AbstractMap<E>.
  • Implementation classes:
    • Hashtable<K, V>
    • HashMap<K, V>
    • LinkedHashMap<K, V>
    • IdentityHashMap<K, V>
    • ConcurrentHashMap<K, V>
    • ConcurrentSkipListMap<K, V>
    • EnumMap<K extends Enum<K>, V>
    • WeakHashMap<K, V>
    • TreeMap<K, V>

The following class diagram outlines the hierarchy of Map API:

Map API class diagram

Class diagram of Set API

In Set API:

  • Set<E> is the base interface for all kinds of set. This interface extends all methods from the Collection<E>interface and does not define any new methods.
  • Sub interfaces: SortedSet<E> and NavigableSet<E>.
  • Abstract subclasses: AbstractSet<E> and EnumSet<E extends enum<E>>.
  • Concrete implementation classes: HashSet<E>, LinkedHashSet<E>, TreeSet<E>,ConcurrentSkipListSet<E> and CopyOnWriteArraySet<E> (these two last classes are under java.util.concurrent package).
  • The JobStateReasons class extends HashSet<E> but it is not a member of Java Collections Framework.

The following class diagram outlines the Set API in Java Collections Framework:

Set API class diagram