Guide to the SortedSet interface in Java

Overview

The Set interface has no definition of first or last elements. To say differently, there is no order in a Set. SortedSet solves that problem by offering an order of elements and letting you access elements by their indexes.

Let’s take a look at the part of the Set interface where we have the SortedSet:

SortedSet in the Set interface in Java

As you can see, SortedSet has no direct concrete implementation. We have TreeSet and ConcurrentSkipListSet implement SortedSet through NavigableSet interface.

Here are the methods of SortedSet

Method nameFunction
comparator()Returns the comparator that used to order elements in the set
first()Get the first element
headSet(E e)Get a SortedSet of elements that are less than e
last()Get the last element
tailSet(E from)Get a SortedSet of elements that are greater than or equal to e (inclusive)
subSet(E from, E to)Get a subset of elements that are greater than from and less than to
spliterator()Creates a Spliterator over the elements in the set
Overview of methods in SortedSet interface

Since elements in SortedSet are ordered, the elements’ class must implement Comparable or when creating the SortedSet, you must pass in a Comparator that accepts the element’s type.

You may recall another data structure that has similar requirements, which is PriorityQueue.

SortedSet in action

Let’s try the operations of a SortedSet by using a TreeSet. As you can see from the diagram, TreeSet implements NavigableSet that in turn extends SortedSet.

Consider the following block:

    private static void sortedSetBasicOperations() {

        SortedSet<String> mySet = new TreeSet<>();
        mySet.add("Karen");
        mySet.add("Zed");
        mySet.add("Abby");
        mySet.add("Quentin");
        mySet.add("Randall");
      
        //print the full set
        System.out.println("The full set is: " + mySet);

        //Getting first and last elements
        System.out.println("First element: " + mySet.first());
        System.out.println("Last element: " + mySet.last());

        //Getting all elements from Karen
        System.out.println("From Karen: " + mySet.tailSet("Karen"));

        //Getting all elements before Quentin
        System.out.println("To Quentin: " + mySet.headSet("Quentin"));

        //Getting all elements from Karen to before Quentin
        System.out.println("From Karen To Quentin: " + mySet.subSet("Karen", "Quentin"));
    }

This is the output of the above code when executed:

Using SortedSet in multi-threaded code

From the diagram, you can see, that there is one implementation of the SortedSet in the java.util.concurrent package. That’s ConcurrentSkipListSet.

Let’s first consider an example where we use non-safe SortedSet first then we’ll use ConcurrentSkipListSet to address the issue.

    private static void nonSafeTreeSetOperation() throws InterruptedException {
        var numberSet = new TreeSet<Integer>();

        ExecutorService service = Executors.newFixedThreadPool(10);

        for (int i = 0; i < 20; i++) {
            int finalI = i;
            service.submit(() -> numberSet.add(finalI) );
        }

        service.shutdown();
        service.awaitTermination(10, TimeUnit.SECONDS);

        System.out.println("The set size: " + numberSet.size());
        System.out.println("The set: " + numberSet);
    }

When executing this code, you might see different results between executions:

Here are some possible outcomes:

Using non safe TreeSet in multi threaded code

Now, if we change TreeSet to ConcurrentSkipListSet, the problem is solved:

    private static void safeTreeSetOperation() throws InterruptedException {
        var numberSet = new ConcurrentSkipListSet<Integer>();

        ExecutorService service = Executors.newFixedThreadPool(10);

        for (int i = 0; i < 20; i++) {
            int finalI = i;
            service.submit(() -> numberSet.add(finalI) );
        }

        service.shutdown();
        service.awaitTermination(10, TimeUnit.SECONDS);

        System.out.println("The set size: " + numberSet.size());
        System.out.println("The set: " + numberSet);
    }

The output is consistent. There are always 20 elements in the list:

Using ConcurrentSkipListSet to handle SortedSet in concurrent code

Conclusion

As you can see, the SortedSet data structure adds more power to the Set interface. There is no order in a set. However, with SortedSet, you can have the items ordered in their natural order or you can specify a comparator to offer the order mechanism yourself.

You can find the code of this article here on Github.


Leave a Reply

Your email address will not be published.