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

![](https://cdn.hashnode.com/uploads/covers/637f189ed7d9bcd845996b4b/91eccee0-a15c-4bc1-8c18-66b9d98df9a2.png align="center")

![](https://cdn.hashnode.com/uploads/covers/637f189ed7d9bcd845996b4b/473d5d89-998b-4ecd-817e-bae8a8876049.png align="center")

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

![](https://cdn.hashnode.com/uploads/covers/637f189ed7d9bcd845996b4b/bd7e11aa-068e-49f5-9c7e-240854638e4d.png align="center")

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

![](https://cdn.hashnode.com/uploads/covers/637f189ed7d9bcd845996b4b/c0208701-5651-41a4-8523-27e534ca340e.png align="center")

* * *

## ConcurrentSkipListMap Structure

```java
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
    }
}
```

![](https://cdn.hashnode.com/uploads/covers/637f189ed7d9bcd845996b4b/fe878cf5-6703-48f4-ad1c-195f743a170c.png align="center")

* * *

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

```java
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
}
```

![](https://cdn.hashnode.com/uploads/covers/637f189ed7d9bcd845996b4b/a7d37da3-c9e8-436b-8a25-b259d0cb906e.png align="center")

* * *

## How put() Works — Insert with Coin Flips

![](https://cdn.hashnode.com/uploads/covers/637f189ed7d9bcd845996b4b/18d1f01a-2b0a-4dd9-9695-371afd1e80f2.png align="center")

### The Probabilistic Level Selection

```java
// 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
    

![](https://cdn.hashnode.com/uploads/covers/637f189ed7d9bcd845996b4b/c45ff1ff-8606-4b24-87b6-f99d3663e6dc.png align="center")

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

### Insert Example: Adding Key 15

![](https://cdn.hashnode.com/uploads/covers/637f189ed7d9bcd845996b4b/52fcad4e-9b4b-48ae-8b66-8c7ee9f2023d.png align="center")

* * *

## How remove() Works

Deletion uses a **marker node** technique to prevent races:

![](https://cdn.hashnode.com/uploads/covers/637f189ed7d9bcd845996b4b/2991a64d-2235-4c4b-b988-d9dbdb52e188.png align="center")

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:

```java
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`:

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

![](https://cdn.hashnode.com/uploads/covers/637f189ed7d9bcd845996b4b/3d206e93-9fb2-4e37-8f61-9f97b9a3ccd0.png align="center")

* * *

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

![](https://cdn.hashnode.com/uploads/covers/637f189ed7d9bcd845996b4b/68f9e806-1945-46e8-bf5d-966bc1e08068.png align="center")

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

```java
// ❌ 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

```java
// ❌ 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

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

* * *

## Summary

![](https://cdn.hashnode.com/uploads/covers/637f189ed7d9bcd845996b4b/42c56d7a-42bb-4021-9546-28ab1b726b70.png align="center")

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