Deep Dive (java.util.concurrent) - ConcurrentSkipListMap

"A sorted concurrent map that doesn't need a single lock for reads — powered by the probabilistic skip list."

ConcurrentSkipListMap is the concurrent equivalent of TreeMap. Where TreeMap uses a Red-Black tree with coarse locking, ConcurrentSkipListMap uses a skip list — a probabilistic data structure with O(log n) operations and lock-free reads.

---

What is a Skip List?

A skip list is a layered linked list where higher levels act as "express lanes" for faster searching. Think of it like a highway system:

Key properties:

• Level 0 (base) contains ALL elements in sorted order

• Higher levels are random subsets, each roughly half the size of the level below

• Expected height: O(log n) levels

• Search: Start at the top, go right until you overshoot, drop down one level, repeat

---

How a Skip List Works

Searching for Key = 20

Steps:

1. Start at HEAD, Level 3 → 25 is too big, drop to Level 2

2. Level 2: HEAD → 10 (smaller, advance) → 25 (too big, drop to Level 1)

3. Level 1: 10 → 20 (found!)

Total comparisons: 4 — much fewer than scanning all 12 elements.

Why O(log n)?

Each level is approximately half the size of the level below (by probabilistic construction). So searching is like a binary search, but on linked lists:

---

ConcurrentSkipListMap Structure

public class ConcurrentSkipListMap<K,V> extends AbstractMap<K,V>
        implements ConcurrentNavigableMap<K,V> {
    
    // Special header node
    private transient volatile HeadIndex<K,V> head;
    
    // The comparator, or null for natural ordering
    final Comparator<? super K> comparator;
    
    // Base-level node
    static final class Node<K,V> {
        final K key;
        volatile Object value;     // volatile for lock-free reads
        volatile Node<K,V> next;   // volatile for lock-free traversal
    }
    
    // Index node (higher-level express lane)
    static class Index<K,V> {
        final Node<K,V> node;      // Points to base-level node
        final Index<K,V> down;     // Lower level
        volatile Index<K,V> right; // Next at same level
    }
}

---

How get() Works — Lock-Free Read

get() is completely lock-free. It traverses the index levels and then the base level using only volatile reads:

public V get(Object key) {
    return doGet(key);
}

private V doGet(Object key) {
    // 1. Find the floor node using index levels
    Node<K,V> n = findNode(key);
    
    // 2. Check if the node actually matches
    if (n != null) {
        Object v = n.value;
        if (v != null)
            return (V) v;
    }
    return null;
}

private Node<K,V> findNode(Object key) {
    // Start from highest index level
    // Move right while next key < search key
    // Drop down when next key > search key
    // Repeat until base level
    // Then scan base level for exact match
}

---

How put() Works — Insert with Coin Flips

The Probabilistic Level Selection

// Simplified level generation
private int randomLevel() {
    int level = 0;
    int rnd = ThreadLocalRandom.current().nextInt();
    while ((rnd & 1) == 1) { // 50% chance per level
        level++;
        rnd >>>= 1;
    }
    return level;
}

The level of each new node is chosen by flipping a coin repeatedly:

• Level 0: 100% of nodes (everyone is in the base)

• Level 1: ~50% of nodes

• Level 2: ~25% of nodes

• Level 3: ~12.5% of nodes

• Level k: ~(1/2^k) of nodes

This is what makes skip lists "self-balancing" without rotations — the random level assignment statistically produces a balanced structure.

Insert Example: Adding Key 15

---

How remove() Works

Deletion uses a marker node technique to prevent races:

The three-phase removal:

1. Logical deletion: CAS value to null (readers immediately see it's gone)

2. Marker: Append a marker node to prevent splitbrain

3. Physical unlink: Remove node and marker from linked list

---

NavigableMap Operations

Like TreeMap, ConcurrentSkipListMap implements NavigableMap with full range operations:

ConcurrentSkipListMap<Integer, String> map = new ConcurrentSkipListMap<>();
map.put(10, "ten");
map.put(20, "twenty");
map.put(30, "thirty");
map.put(40, "forty");

// Navigation — all O(log n)
map.firstKey();      // 10
map.lastKey();       // 40
map.floorKey(25);    // 20 (greatest ≤ 25)
map.ceilingKey(25);  // 30 (smallest ≥ 25)
map.lowerKey(30);    // 20 (strictly less)
map.higherKey(30);   // 40 (strictly greater)

// Range views — thread-safe!
ConcurrentNavigableMap<Integer, String> sub = map.subMap(15, 35);
// {20=twenty, 30=thirty} — concurrent view!

ConcurrentNavigableMap<Integer, String> desc = map.descendingMap();
// {40=forty, 30=thirty, 20=twenty, 10=ten}

---

ConcurrentSkipListSet

Just like HashSet wraps HashMap, ConcurrentSkipListSet wraps ConcurrentSkipListMap:

public class ConcurrentSkipListSet<E> extends AbstractSet<E>
        implements NavigableSet<E> {
    
    private final ConcurrentNavigableMap<E, Object> m;
    
    public ConcurrentSkipListSet() {
        m = new ConcurrentSkipListMap<E, Object>();
    }
    
    public boolean add(E e) {
        return m.putIfAbsent(e, Boolean.TRUE) == null;
    }
}

A thread-safe, sorted set with O(log n) operations.

---

ConcurrentSkipListMap vs ConcurrentHashMap

Feature	ConcurrentSkipListMap	ConcurrentHashMap
Ordering	✅ Sorted by key	❌ No ordering
get/put/remove	O(log n)	O(1) average
Range operations	✅ subMap/headMap/tailMap	❌ None
Navigation	✅ floor/ceiling/first/last	❌ None
Memory	Higher (index nodes)	Lower
Null keys	❌ Not allowed	❌ Not allowed
Null values	❌ Not allowed	❌ Not allowed
Iterator	Weakly consistent, sorted	Weakly consistent, unordered
Best for	Sorted concurrent data	General concurrent map

---

ConcurrentSkipListMap vs TreeMap

Feature	ConcurrentSkipListMap	TreeMap
Thread-safe	✅ Lock-free reads	❌ Not thread-safe
Read performance	O(log n) lock-free	O(log n) with lock needed
Write performance	O(log n) with CAS	O(log n) with exclusive lock
Structure	Skip list (probabilistic)	Red-Black tree (deterministic)
Balancing	Random levels (stochastic)	Rotations (guaranteed)
Memory	Higher (multiple index levels)	Lower (parent/left/right/color)
Worst case	O(n) theoretically (astronomically unlikely)	O(log n) guaranteed

Why skip list for concurrency? Red-Black tree rotations modify multiple pointers atomically (parent, child, sibling) — very hard to do lock-free. Skip list insertions only modify a single next pointer at each level — perfect for CAS.

---

Common Pitfalls

Pitfall 1: Expecting HashMap Performance

// ❌ ConcurrentSkipListMap is O(log n), not O(1)
// If you don't need sorting, use ConcurrentHashMap instead

// HashMap:  1M operations → ~1M ns = ~1ms
// SkipList: 1M operations → ~20M ns = ~20ms (log₂(1M) ≈ 20)

Pitfall 2: Non-Comparable Keys Without Comparator

// ❌ ClassCastException!
ConcurrentSkipListMap<Object, String> map = new ConcurrentSkipListMap<>();
map.put(new Object(), "value"); // Object doesn't implement Comparable!

// ✅ Provide a Comparator or use Comparable keys
ConcurrentSkipListMap<String, String> map = new ConcurrentSkipListMap<>();

Pitfall 3: Null Keys and Values

// ❌ NullPointerException — neither null keys nor null values!
ConcurrentSkipListMap<String, String> map = new ConcurrentSkipListMap<>();
map.put(null, "value");    // NPE!
map.put("key", null);      // NPE!

---

Summary

The one-liner: ConcurrentSkipListMap is a lock-free sorted concurrent map using a probabilistic skip list structure — achieving O(log n) thread-safe operations with full navigation support, making it the only concurrent sorted Map in the JDK.