What is a Java SortedSet?

A Java SortedSet is a subtype of the Set interface in Java that stores its elements in sorted order. But what is a Java SortedSet exactly, and how do Java SortedSets work?

What are Java SortedSets?

In computer science, a set is a fundamental data structure in which an element can be stored a maximum of one time. This condition distinguishes sets from other data structures such as arrays, which can store multiple instances of the same element.

Most implementations of the set data structure store elements in a way that makes lookup operations very fast. Thus, one of the most common use cases for sets is to check (very efficiently) for membership, i.e. whether an item is already present or has already been processed by the program.

The Java programming language implements the set data structure with the java.util.Set interface. In addition, there are multiple subclasses and subinterfaces of Java’s Set interface, including java.util.SortedSet.

According to the Java documentation, a SortedSet “provides a total ordering on its elements.” In some cases, the natural ordering is obvious, such as for SortedSets that contain integers. In other cases, the user will have to define a Comparator comparison function that describes how to compare two different elements.

How do Java SortedSets work?

The java.util.SortedSet interface defines the methods that must be part of any class that implements the interface. Below are some of the most important methods of Java SortedSets:

  • add(): Adds a new element to the set.
  • addAll(): Adds all of the specified elements to the set.
  • clear(): Removes all of the elements from the set.
  • first(): Returns the first element in the set.
  • headSet(): Given an element in the set, returns a subset whose elements are all less than the given element.
  • isEmpty(): Returns true if the set is empty.
  • iterator(): Returns an iterator that loops through all of the elements in the set in sorted order.
  • last(): Returns the last element in the set.
  • remove(): Removes the specified element from the set.
  • removeAll(): Removes all of the specified elements from the set.
  • size(): Returns the number of elements in the set.
  • subSet(): Given two elements in the set, returns a subset whose members are between these two elements.
  • tailSet(): Given an element in the set, returns a subset whose elements are all greater than the given element.

Because java.util.SortedSet is only an interface, it cannot be instantiated directly in Java. Instead, users need to instantiate one of the classes that implement the SortedSet interface, such as ConcurrentSkipListSet or TreeSet. The differences between these classes are as follows:

  • ConcurrentSkipListSet: A scalable, concurrent implementation of the SortedSet interface based on the ConcurrentSkipListMap class. The contains(), add(), and remove() operations all have O(log n) time complexity. 
  • TreeSet: An implementation of the SortedSet interface based on the TreeMap class for red-black trees. The contains(), add(), and remove() operations all have O(log n) time complexity. However, TreeSets are not synchronized and require external synchronization if multiple threads are accessing them concurrently.

Java SortedSets in Redis

Redis is an open-source, in-memory data structure store used to implement NoSQL key-value databases, caches, and message brokers. Sorted sets are one of the few built-in data structure types in Redis, as well as lists, sets, strings, and hashes.

In Redis, SortedSets are known as ZSETS and have a particular implementation: they store key-value pairs, with the keys being unique and the values being floating-point numbers. Redis also comes with functions such as ZADD, ZRANGE, and ZREM to make it easier to work with sorted sets in Redis.

While Redis sorted sets are a valuable addition to the project, the fact that they’re limited to key-value pairs (and that the values must be floating-point numbers) limits their utility. This is especially challenging for Java developers who are used to the richness of the Java standard library. To fix this issue and lower the Redis learning curve, many Java developers choose to install a third-party Java Redis client such as Redisson.

Redisson includes many familiar Java objects, collections, and constructs for Redis, including Java SortedSets, which are implemented in Redisson using the RSortedSet interface. Below is an example of how to use Java SortedSets in Redis with Redisson:

RSortedSet<Integer> set = redisson.getSortedSet("anySet");
set.trySetComparator(new MyComparator()); // set object comparator
set.add(3);
set.add(1);
set.add(2);

set.removeAsync(0);
set.addAsync(5);

Redisson also includes two variations on RSortedSet: the RLexSortedSet interface for working with strings, and the RScoredSortedSet, which sorts elements by a score that you define when inserting them into the set. Below is an example of how to use the RScoredSortedSet:

RScoredSortedSet<SomeObject> set = redisson.getScoredSortedSet("simple");

set.add(0.13, new SomeObject(a, b));
set.addAsync(0.251, new SomeObject(c, d));
set.add(0.302, new SomeObject(g, d));

set.pollFirst();
set.pollLast();

int index = set.rank(new SomeObject(g, d)); // get element index
Double score = set.getScore(new SomeObject(g, d)); // get element score
Similar terms