Understanding Java's ConcurrentSkipListMap: Overview, Principles, API, Source Analysis, and Example Usage

The series "Big Data Becoming a God" introduces the Java java.util.concurrent.ConcurrentSkipListMap class, a thread‑safe ordered hash table based on the skip‑list data structure, suitable for high‑concurrency scenarios.

1. Overview

ConcurrentSkipListMap differs from TreeMap in two main ways: it is thread‑safe, and it implements the map using a skip‑list rather than a red‑black tree.

A skip‑list is a probabilistic alternative to balanced trees; its insertion and deletion operations are simpler because they rely on random level selection.

2. Principles and Data Structure

The skip‑list consists of multiple levels, each acting as an index to speed up searches. The first level contains all elements, and each higher level contains a subset, providing increasingly larger jumps.

Search proceeds from the top‑most level, moving right until the next key would exceed the target, then dropping down a level and repeating until the element is found.

3. ConcurrentSkipListMap API

public ConcurrentSkipListMap();
public ConcurrentSkipListMap(Comparator<? super K> comparator);
public ConcurrentSkipListMap(Map<? extends K, ? extends V> m);
public ConcurrentSkipListMap(SortedMap<K, ? extends V> m);
Map.Entry<K,V> ceilingEntry(K key);
K ceilingKey(K key);
void clear();
ConcurrentSkipListMap<K,V> clone();
Comparator<? super K> comparator();
boolean containsKey(Object key);
boolean containsValue(Object value);
NavigableSet<K> descendingKeySet();
ConcurrentNavigableMap<K,V> descendingMap();
Set<Map.Entry<K,V>> entrySet();
boolean equals(Object o);
Map.Entry<K,V> firstEntry();
K firstKey();
Map.Entry<K,V> floorEntry(K key);
K floorKey(K key);
V get(Object key);
ConcurrentNavigableMap<K,V> headMap(K toKey);
ConcurrentNavigableMap<K,V> headMap(K toKey, boolean inclusive);
Map.Entry<K,V> higherEntry(K key);
K higherKey(K key);
boolean isEmpty();
NavigableSet<K> keySet();
Map.Entry<K,V> lastEntry();
K lastKey();
Map.Entry<K,V> lowerEntry(K key);
K lowerKey(K key);
NavigableSet<K> navigableKeySet();
Map.Entry<K,V> pollFirstEntry();
Map.Entry<K,V> pollLastEntry();
V put(K key, V value);
V putIfAbsent(K key, V value);
V remove(Object key);
V remove(Object key, Object value);
V replace(K key, V value);
boolean replace(K key, V oldValue, V newValue);
int size();
ConcurrentNavigableMap<K,V> subMap(K fromKey, K toKey);
ConcurrentNavigableMap<K,V> subMap(K fromKey, boolean fromInclusive, K toKey, boolean toInclusive);
ConcurrentNavigableMap<K,V> tailMap(K fromKey);
ConcurrentNavigableMap<K,V> tailMap(K fromKey, boolean inclusive);
Collection<V> values();

4. Source Code Analysis

4.1 Adding (put)

public V put(K key, V value) {
    if (value == null) throw new NullPointerException();
    return doPut(key, value, false);
}

The core insertion logic resides in doPut, which finds the predecessor node, creates a new node, links it at level 0, then randomly selects a level and inserts the node into higher levels.

4.2 Removing (remove)

public V remove(Object key) {
    return doRemove(key, null);
}

doRemove

locates the predecessor and target node, atomically nulls the node's value, unlinks it from the list, and cleans up index levels.

4.3 Getting (get)

public V get(Object key) {
    return doGet(key);
}
private V doGet(Object okey) {
    Comparable<? super K> key = comparable(okey);
    for (;;) {
        Node<K,V> n = findNode(key);
        if (n == null) return null;
        Object v = n.value;
        if (v != null) return (V)v;
    }
}

findNode

traverses the skip‑list similarly to the search algorithm described earlier.

5. Example Usage

The following demo starts two threads that concurrently insert entries into a ConcurrentSkipListMap and iterate over the map. When using ConcurrentSkipListMap the program runs without ConcurrentModificationException; using TreeMap would cause the exception.

import java.util.*;
import java.util.concurrent.*;

public class ConcurrentSkipListMapDemo1 {
    private static Map<String, String> map = new ConcurrentSkipListMap<>();
    public static void main(String[] args) {
        new MyThread("a").start();
        new MyThread("b").start();
    }
    private static void printAll() {
        Iterator<Map.Entry<String,String>> iter = map.entrySet().iterator();
        while (iter.hasNext()) {
            Map.Entry<String,String> e = iter.next();
            System.out.print("("+e.getKey()+", "+e.getValue()+"), ");
        }
        System.out.println();
    }
    private static class MyThread extends Thread {
        MyThread(String name) { super(name); }
        @Override public void run() {
            for (int i=1;i<=6;i++) {
                String val = Thread.currentThread().getName()+i;
                map.put(val, "0");
                printAll();
            }
        }
    }
}

Sample output shows interleaved entries from both threads, confirming the map's thread‑safety.