ConcurrentSkipListSet in Java

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.

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.

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

Output

Couple of things to note here-

  1. Elements are stored in sorted order.
  2. 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.

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.

Output

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


You may also like

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.