ConcurrentSkipListMap in Java

This post talks about the ConcurrentSkipListMap class from the java.util.concurrent package and the interface ConcurrentNavigableMap this class implements.

ConcurrentSkipListMap in Java

ConcurrentSkipListMap is a thread-safe, scalable Map that stores its elements in sorted manner. By default map is sorted according to the natural ordering of its keys, or by a Comparator provided at map creation time, depending on which constructor is used.

Java ConcurrentSkipListMap class implements a concurrent variant of SkipLists providing expected average log(n) time cost for the containsKey, get, put and remove operations and their variants. Insertion, removal, update, and access operations safely execute concurrently by multiple threads. ConcurrentSkipListMap was added in Java 1.6.


SkipList data structure

As per – 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 ConcurrentSkipListMap.

ConcurrentNavigableMap in Java

ConcurrentSkipListMap in Java implements the ConcurrentNavigableMap interface where ConcurrentNavigableMap extends ConcurrentMap and NavigableMap interfaces in turn.

  • ConcurrentMap– A Map providing thread safety and atomicity guarantees. So there are methods like putIfAbsent(), remove() where the action is performed atomically.
  • NavigableMap– A SortedMap extended with navigation methods returning the closest matches for given search targets. So it has methods like lowerEntry(K), floorEntry(K), lowerKey(K), floorKey(K), ceilingKey(K) for returning closest match to the passed key.

ConcurrentNavigableMap interface was added in Java 1.6.

Java ConcurrentSkipListMap constructors

  • ConcurrentSkipListMap()– Constructs a new, empty map, sorted according to the natural ordering of the keys.
  • ConcurrentSkipListMap(Comparator<? super K> comparator)– Constructs a new, empty map, sorted according to the specified comparator.
  • ConcurrentSkipListMap(Map<? extends K,? extends V> m)– Constructs a new map containing the same mappings as the given map, sorted according to the natural ordering of the keys.
  • ConcurrentSkipListMap(SortedMap<K,? extends V> m)– Constructs a new map containing the same mappings and using the same ordering as the specified sorted map.

ConcurrentSkipListMap Java example


As you can see the elements are sorted by their keys and natural ordering is used as no Comparator is passed while creating the ConcurrentSkipListMap.

ConcurrentSkipListMap doesn’t allow null

ConcurrentSkipListMap class in Java does not permit the use of null keys or values. Adding a null key or value results in NullPointerException being thrown.

For example- In the example code used above if you try to add null key result would be as follows.

Navigational methods in ConcurrentSkipListMap example


That’s all for the topic ConcurrentSkipListMap 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.