How SkipList Powers Java’s ConcurrentSkipListMap – A Deep Dive

Introduction

In Java, the common key‑value structures are HashMap and TreeMap. Both have drawbacks: HashMap offers O(1) access but needs extra work for ordering, while TreeMap (a red‑black tree) provides ordered keys at the cost of more complex locking.

SkipList Overview

A SkipList is a probabilistic, layered linked list that maintains elements in sorted order. Each level is a subset of the level below, and a random coin‑flip decides how many levels a newly inserted node occupies, achieving O(log n) search, insertion and deletion on average.

SkipList Features

Multiple levels generated by a random process.

Each level is an ordered singly‑linked list.

The bottom level (Level 1) contains all elements.

If an element appears in Level i, it also appears in all lower levels.

Each node stores two pointers: next (right) and down (to the lower level).

Search

Starting from the highest HeadIndex, the algorithm moves right while the next node’s key is less than the target, then moves down. This reduces the number of comparisons dramatically compared with a plain linked list.

Insertion

Insertion consists of three steps:

Find the predecessor node using findPredecessor.

Create a new Node for the key‑value pair and link it with a CAS operation.

Determine the node’s level by repeatedly shifting a random integer (coin‑flip). If the level exceeds the current maximum, a new HeadIndex layer is created.

After the node is linked at the bottom level, index nodes are created for each level up to the chosen level and spliced into the corresponding index lists.

Deletion

Deletion simply sets the node’s value to null. Subsequent searches or updates detect the null value and invoke unlink to physically remove the node from the index layers.

ConcurrentSkipListMap Implementation

ConcurrentSkipListMap

is a lock‑free, thread‑safe map built on top of a SkipList. It defines three internal classes:

static final class Node<K,V> {
    final K key;
    volatile Object value;
    volatile ConcurrentSkipListMap.Node<K,V> next;
    // constructors and CAS helpers omitted for brevity
}

static final class Index<K,V> {
    final ConcurrentSkipListMap.Node<K,V> node;
    final Index<K,V> down;
    volatile Index<K,V> right;
    // constructors omitted
}

static final class HeadIndex<K,V> extends Index<K,V> {
    final int level; // height of this head
    HeadIndex(Node<K,V> node, Index<K,V> down, Index<K,V> right, int level) {
        super(node, down, right);
        this.level = level;
    }
}

Initialization

private void initialize() {
    keySet = null;
    entrySet = null;
    values = null;
    descendingMap = null;
    randomSeed = seedGenerator.nextInt() | 0x0100; // ensure non‑zero
    head = new HeadIndex<>(new Node<K,V>(null, BASE_HEADER, null), null, null, 1);
}

Finding the Predecessor

private Node<K,V> findPredecessor(Object key, Comparator<? super K> cmp) {
    if (key == null) throw new NullPointerException();
    for (Index<K,V> q = head, r = q.right, d;;) {
        if (r != null) {
            Node<K,V> n = r.node;
            int c = cpr(cmp, key, n.key);
            if (c > 0) { q = r; r = r.right; continue; }
            if (c == 0) return n; // exact match
        }
        if ((d = q.down) == null) return q.node; // reached bottom
        q = d; r = q.right;
    }
}

Put Operation

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

private V doPut(K key, V value, boolean onlyIfAbsent) {
    // 1. Find predecessor
    // 2. Insert new Node with CAS
    // 3. Randomly choose level using ThreadLocalRandom
    // 4. Build Index nodes and splice them into each level
    // 5. If level > current head level, create new HeadIndex layers
    // (full source omitted for brevity)
}

Get Operation

public V get(Object key) {
    if (key == null) throw new NullPointerException();
    return doGet(key);
}

private V doGet(Object key) {
    // Similar traversal as findPredecessor, but returns the value
    // Skips nodes whose value is null (already deleted)
}

Remove Operation

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

private V doRemove(Object key, Object value) {
    // Locate node, CAS its value to null, then unlink from index layers
    // If a level becomes empty, tryReduceLevel() removes the empty HeadIndex
}

Size Operation

public int size() {
    long count = 0;
    for (Node<K,V> n = findFirst(); n != null; n = n.next) {
        if (n.getValidValue() != null) ++count;
    }
    return count >= Integer.MAX_VALUE ? Integer.MAX_VALUE : (int)count;
}

Conclusion

The ConcurrentSkipListMap combines the simplicity of SkipList with lock‑free techniques such as CAS and random level generation, providing a concurrent, ordered map with O(log n) performance. Understanding SkipList fundamentals makes the source code of ConcurrentSkipListMap much easier to follow.