Java ConcurrentSkipListSet With Examples

ConcurrentSkipListSet in Java is a sorted set just like TreeSet but it is also scalable and concurrent so ConcurrentSkipListSet is thread-safe and can be accessed by multiple threads safely.

In ConcurrentSkipListSet operations like add and remove are done atomically using compare and swap (CAS). These are lock-free so overhead of synchronization is not there.

ConcurrentSkipListSet was added in Java 6 and it is part of java.util.concurrent package.

Table of contents

SkipList data structure
Java ConcurrentSkipListSet - A sorted set
ConcurrentSkipListSet internal data structure
Java ConcurrentSkipListSet constructors
ConcurrentSkipListSet Java example
Nulls are not allowed in ConcurrentSkipListSet
Navigational methods in ConcurrentSkipListSet example

SkipList data structure

As per https://en.wikipedia.org/wiki/Skip_list - Skip list is a data structure that allows fast search within an ordered sequence of elements. Fast search is made possible by maintaining a linked hierarchy of subsequences, with each successive subsequence skipping over fewer elements than the previous one.

As you can see for faster search skip list requires elements to be in an ordered sequence, that is why elements are sorted in the Java ConcurrentSkipListSet.

Java ConcurrentSkipListSet - A sorted set

ConcurrentSkipListSet class in Java implements NavigableSet interface which in turn extends the SortedSet interface. So, ConcurrentSkipListSet is a sorted set with navigation methods reporting closest matches for given search targets.

The elements of the ConcurrentSkipListSet are kept sorted according to their natural ordering, or by a Comparator provided at set creation time, depending on which constructor is used.

ConcurrentSkipListSet internal data structure

Just like other Set implementations use the equivalent Map implementation for storing elements, ConcurrentSkipListSet also uses ConcurrentSkipListMap internally. Each constructor of ConcurrentSkipListSet creates an instance of ConcurrentSkipListMap and use that for its operations.

Java ConcurrentSkipListSet constructors

ConcurrentSkipListSet()- Constructs a new, empty set that orders its elements according to their natural ordering.
ConcurrentSkipListSet(Collection<? extends E> c)- Constructs a new set containing the elements in the specified collection, that orders its elements according to their natural ordering.
ConcurrentSkipListSet(Comparator<? super E> comparator)- Constructs a new, empty set that orders its elements according to the specified comparator.
ConcurrentSkipListSet(SortedSet s)- Constructs a new set containing the same elements and using the same ordering as the specified sorted set.

ConcurrentSkipListSet Java example

import java.util.Iterator;
import java.util.NavigableSet;
import java.util.concurrent.ConcurrentSkipListSet;

public class SkipSetDemo {
  public static void main(String[] args) {
    NavigableSet<String> carSet = new ConcurrentSkipListSet<String>();
    carSet.add("Audi");
    carSet.add("Jaguar");
    carSet.add("BMW");
    carSet.add("Mini Cooper");
    carSet.add("BMW");
    Iterator<String> itr = carSet.iterator();
    while(itr.hasNext()){
      System.out.println("Value -  " + itr.next());
    }
  }
}

Output

Value -  Audi
Value -  BMW
Value -  Jaguar
Value -  Mini Cooper

Couple of things to note here-

Elements are stored in sorted order.
Even if “BMW” is added twice it’s inserted only once, ConcurrentSkipListSet being a Set implementation doesn’t allow duplicate elements.

Nulls are not allowed in ConcurrentSkipListSet

ConcurrentSkipListSet in Java doesn’t allows null values.

If you add the statement- carSet.add(null); in the previous example it will result in following error.

Exception in thread "main" java.lang.NullPointerException
at java.base/java.util.concurrent.ConcurrentSkipListMap.doPut(ConcurrentSkipListMap.java:597)
at java.base/java.util.concurrent.ConcurrentSkipListMap.putIfAbsent(ConcurrentSkipListMap.java:1788)
at java.base/java.util.concurrent.ConcurrentSkipListSet.add(ConcurrentSkipListSet.java:242)
at com.knpcode.SkipSetDemo.main(SkipSetDemo.java:14)

Navigational methods in ConcurrentSkipListSet example

Since ConcurrentSkipListSet implements NavigableSet interface so it has navigation methods reporting closest matches for given search targets. Here we have an example showing some of the navigation methods.

public class SkipSetDemo {
  public static void main(String[] args) {
    NavigableSet<Integer> numSet = new ConcurrentSkipListSet<Integer>();
    numSet.add(1);
    numSet.add(2);
    numSet.add(5);
    numSet.add(8);
    numSet.add(10);
    numSet.add(16);

    System.out.println("** Ceiling method Example **");
    //Returns the least element in this set greater than or equal to the 
    //given element
    int num = numSet.ceiling(9);
    System.out.println("num- " + num);

    System.out.println("** Floor method Example **");
    //Returns the greatest element in this set less than or equal to the 
    //given element
    num = numSet.floor(9);
    System.out.println("num- " + num);

    System.out.println("** Lower method Example **");
    //Returns the greatest element in this set strictly less than the given element
    num = numSet.lower(10);
    System.out.println("num- " + num);
  }
}

Output

** Ceiling method Example **
num- 10
** Floor method Example **
num- 8
** Lower method Example **
num- 8

That's all for the topic Java ConcurrentSkipListSet With Examples. If something is missing or you have something to share about the topic please write a comment.

You may also like

KnpCode

October 8, 2022