Java ConcurrentSkipListMap With Examples

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 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 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

public class SkipMapDemo {
  public static void main(String[] args) {
    // Creating ConcurrentSkipListMap
    ConcurrentNavigableMap<String, String> cityTemperatureMap = new ConcurrentSkipListMap<String, String>();

    // Storing elements
    cityTemperatureMap.put("Delhi", "24");
    cityTemperatureMap.put("Mumbai", "32");
    cityTemperatureMap.put("Chennai", "35");
    cityTemperatureMap.put("Bangalore", "22" );
    cityTemperatureMap.put("Kolkata", "28");

    Set<Map.Entry<String, String>> cityTempSet = cityTemperatureMap.entrySet();
    cityTempSet.forEach((m)->System.out.println("key " + m.getKey() 
				 + " value " + m.getValue()));
  }
}

Output

key Bangalore value 22
key Chennai value 35
key Delhi value 24
key Kolkata value 28
key Mumbai value 32

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.

cityTemperatureMap.put(null, "28");

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.put(ConcurrentSkipListMap.java:1345)

Navigational methods in ConcurrentSkipListMap example

public class SkipMapDemo {

  public static void main(String[] args) {
    // Creating ConcurrentSkipListMap
    ConcurrentNavigableMap<Integer, String> numberMap = new ConcurrentSkipListMap<Integer, String>();

    // Storing elements
    numberMap.put(1, "ONE");
    numberMap.put(2, "TWO");
    numberMap.put(5, "FIVE");
    numberMap.put(8, "EIGHT" );
    numberMap.put(10, "TEN");
    numberMap.put(16, "SIXTEEN");

    System.out.println("** reverse order view of the map **");

    //Returns a reverse order view of the mappings
    ConcurrentNavigableMap<Integer, String> reverseNumberMap = numberMap.descendingMap();

    Set<Map.Entry<Integer, String>> numSet = reverseNumberMap.entrySet();
    numSet.forEach((m)->System.out.println("key " + m.getKey() 
         + " value " + m.getValue()));
    System.out.println("** First entry in the the map **");
    //Returns a key-value mapping associated with the least key in this map
    Map.Entry<Integer, String> mapEntry = numberMap.firstEntry();
    System.out.println("key " + mapEntry.getKey() + " value " + mapEntry.getValue());

    System.out.println("** Floor entry Example **");
    //Returns a key-value mapping associated with the greatest key less than or equal to the given key
    mapEntry = numberMap.floorEntry(7);
    System.out.println("key " + mapEntry.getKey()  + " value " + mapEntry.getValue());

    System.out.println("** Ceiling entry Example **");
    //Returns a key-value mapping associated with the least key greater than or equal to the given key
    mapEntry = numberMap.ceilingEntry(7);
    System.out.println("key " + mapEntry.getKey()  + " value " + mapEntry.getValue());
  }
}

Output

** reverse order view of the map **
key 16 value SIXTEEN
key 10 value TEN
key 8 value EIGHT
key 5 value FIVE
key 2 value TWO
key 1 value ONE
** First entry in the the map **
key 1 value ONE
** Floor entry Example **
key 5 value FIVE
** Ceiling entry Example **
key 8 value EIGHT

Related Posts

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