ConcurrentSkipListMap: Thread-Safe Sorted Map

ConcurrentSkipListMap: Thread-Safe Sorted Map

Before We Start — What You Need to Know

You already know HashMap (fast key-value lookups) and TreeMap (sorted key-value pairs). But neither is thread-safe. ConcurrentHashMap gives you a thread-safe hash map — but what if you need your keys sorted and the map thread-safe at the same time?

Enter ConcurrentSkipListMap — a lock-free, thread-safe, sorted map built on one of the coolest data structures in computer science: the skip list.

You should know: what a Map is, why TreeMap keeps keys sorted, and how CAS (Compare-And-Swap) works from the Atomic Operations lesson.

What is it? (The Analogy)

Imagine you're looking up a word in a physical dictionary. You don't start at page 1 and read every entry — that's a linked list, and it's painfully slow. Instead, you use the guide words at the top of each page to skip ahead: "Is my word before or after 'Kangaroo'?" This gets you to the right page in just a few jumps.

A skip list works exactly like this. It's a linked list with "express lanes" on top:

• Level 0 (ground level): A regular sorted linked list containing ALL elements.
• Level 1: An "express lane" that contains *some* elements, letting you skip over big chunks.
• Level 2: An even faster express lane with fewer elements.
• Top level: Maybe just a few elements — like the chapter dividers in a dictionary.

When searching, you start at the top level and "drop down" when you've gone too far. It's like a highway exit system: start on the interstate, exit to a state highway, exit to a local road, and you're at your destination. Average time complexity: O(log n) — same as a balanced tree, but without rotations!

The "concurrent" part: skip lists are naturally suited for lock-free algorithms because inserting or deleting a node only requires updating a few pointers, which can be done with CAS operations.

The Problem It Solves

Here's what goes wrong when you try to use a TreeMap with multiple threads:

1import java.util.TreeMap;
2
3// BROKEN: TreeMap is NOT thread-safe!
4class BrokenLeaderboard {
5    private final TreeMap<Integer, String> scores = new TreeMap<>();
6
7    // Thread 1 calls this
8    public void updateScore(String player, int score) {
9        scores.put(score, player);  // NOT thread-safe!
10    }
11
12    // Thread 2 calls this
13    public String getTopPlayer() {
14        // lastEntry() reads the tree structure
15        // while Thread 1 is modifying it — CRASH!
16        var entry = scores.lastEntry();
17        return entry != null ? entry.getValue() : "nobody";
18    }
19
20    // Thread 3 calls this
21    public void removePlayer(int score) {
22        scores.remove(score);  // Concurrent modification!
23    }
24}

What goes wrong?

• TreeMap uses a Red-Black tree internally. Insertions and deletions trigger tree rotations — restructuring of multiple nodes.
• If Thread 1 is rotating nodes while Thread 2 is traversing the tree, Thread 2 can follow a stale pointer and crash (NullPointerException) or loop infinitely.
• ConcurrentModificationException if you iterate while modifying.

You could wrap it in Collections.synchronizedSortedMap(), but that uses a single global lock — brutal for performance.

How it works — Step by Step

1. The structure: A ConcurrentSkipListMap maintains multiple levels of linked lists. Each entry appears at level 0 and has a random chance of being "promoted" to higher levels.
2. Search: Start at the highest level. Move forward as long as the next node's key is less than your target. When the next key is too big, drop down one level and continue. This gives O(log n) search.
3. Insert: Search for the insertion point. Insert the new node at level 0. Then, flip a coin: heads means promote to the next level (insert there too). Keep flipping until you get tails. On average, each element appears in ~2 levels.
4. Delete: Mark the node as logically deleted (using CAS on a marker), then physically unlink it from each level. The two-phase approach prevents lost updates.
5. Concurrency: All operations use CAS on the "next" pointers — no locks. Multiple threads can insert, delete, and search simultaneously.

Level 3: HEAD -----------------------> 50 -----------> null
Level 2: HEAD ---------> 25 --------> 50 --------> 75 -> null
Level 1: HEAD -> 10 -> 25 -> 30 -> 50 -> 60 -> 75 -> 90 -> null
Level 0: HEAD -> 10 -> 20 -> 25 -> 30 -> 40 -> 50 -> 60 -> 70 -> 75 -> 80 -> 90 -> null

Searching for 60: Start at Level 3 -> go to 50 -> can't go further (null) -> drop to Level 2 -> go to 75 -> too far! -> drop to Level 1 -> 50 -> 60 -> FOUND!

Let's Build It Together

Let's build a real-time game leaderboard where players' scores change constantly:

1import java.util.concurrent.ConcurrentSkipListMap;
2import java.util.concurrent.ConcurrentHashMap;
3import java.util.Map;
4import java.util.NavigableMap;
5
6public class GameLeaderboard {
7
8    // ConcurrentSkipListMap keeps scores sorted automatically!
9    // Key: negative score (so highest score comes FIRST)
10    // Value: player name
11    // We use negative scores because the map sorts ascending,
12    // but we want descending (highest first).
13    private final ConcurrentSkipListMap<Long, String> scoreBoard =
14        new ConcurrentSkipListMap<>();
15
16    // Track each player's current score for updates
17    private final ConcurrentHashMap<String, Long> playerScores =
18        new ConcurrentHashMap<>();
19
20    /**
21     * Update a player's score. Thread-safe, lock-free!
22     */
23    public void updateScore(String player, long newScore) {
24        // Remove old entry (if exists)
25        Long oldScore = playerScores.put(player, newScore);
26        if (oldScore != null) {
27            scoreBoard.remove(-oldScore, player); // CAS-based removal
28        }
29        // Add new entry with negated score for descending order
30        scoreBoard.put(-newScore, player);
31    }
32
33    /**
34     * Get the top N players — uses the sorted nature of skip list!
35     */
36    public void printTopPlayers(int n) {
37        System.out.println("=== TOP " + n + " LEADERBOARD ===");
38        int rank = 1;
39        // firstEntry(), pollFirstEntry(), etc. are all thread-safe
40        for (Map.Entry<Long, String> entry : scoreBoard.entrySet()) {
41            if (rank > n) break;
42            long score = -entry.getKey(); // Un-negate to show real score
43            System.out.println("#" + rank + " " + entry.getValue()
44                             + " — " + score + " pts");
45            rank++;
46        }
47    }
48
49    /**
50     * Get all players with scores in a range — this is where
51     * ConcurrentSkipListMap shines vs ConcurrentHashMap!
52     */
53    public NavigableMap<Long, String> getPlayersInRange(long minScore,
54                                                         long maxScore) {
55        // subMap gives a VIEW of the map within the range
56        // Thread-safe and reflects real-time changes!
57        return scoreBoard.subMap(-maxScore, true, -minScore, true);
58    }
59
60    /**
61     * Get the current leader — O(log n) and thread-safe
62     */
63    public String getCurrentLeader() {
64        Map.Entry<Long, String> first = scoreBoard.firstEntry();
65        return first != null ? first.getValue() : "No players yet";
66    }
67
68    /**
69     * Get a player's rank (position in sorted order)
70     */
71    public int getPlayerRank(String player) {
72        Long score = playerScores.get(player);
73        if (score == null) return -1;
74        // headMap returns all entries with keys LESS than the given key
75        // Since we negate scores, this counts players with higher scores
76        return scoreBoard.headMap(-score).size() + 1;
77    }
78
79    public static void main(String[] args) throws InterruptedException {
80        GameLeaderboard leaderboard = new GameLeaderboard();
81
82        // Simulate 5 players earning points concurrently
83        Thread[] threads = new Thread[5];
84        String[] players = {"Alice", "Bob", "Charlie", "Diana", "Eve"};
85
86        for (int i = 0; i < 5; i++) {
87            final int idx = i;
88            threads[i] = new Thread(() -> {
89                long score = 0;
90                for (int round = 0; round < 100; round++) {
91                    score += (long) (Math.random() * 10);
92                    leaderboard.updateScore(players[idx], score);
93                    try { Thread.sleep(10); } catch (InterruptedException e) {
94                        Thread.currentThread().interrupt();
95                    }
96                }
97            }, "Player-" + players[i]);
98            threads[i].start();
99        }
100
101        // Meanwhile, a display thread shows the leaderboard periodically
102        Thread display = new Thread(() -> {
103            for (int i = 0; i < 5; i++) {
104                try { Thread.sleep(200); } catch (InterruptedException e) {
105                    Thread.currentThread().interrupt();
106                }
107                leaderboard.printTopPlayers(3);
108                System.out.println();
109            }
110        });
111        display.start();
112
113        for (Thread t : threads) t.join();
114        display.join();
115
116        System.out.println("\nFINAL LEADERBOARD:");
117        leaderboard.printTopPlayers(5);
118    }
119}

What Happens Under the Hood

Here's what happens when you insert a key-value pair into ConcurrentSkipListMap:

1. Find the insertion position: Starting from the highest level, traverse forward and down (like the dictionary analogy) until you find the two nodes between which the new key belongs at level 0.

1. Insert at level 0 using CAS: Create a new node. Use compareAndSet on the predecessor's "next" pointer to swing it from the old successor to the new node. If the CAS fails (another thread inserted between the same two nodes), retry from step 1.

1. Determine the node's height: Use a random number generator to decide how many levels this node should participate in. This is the probabilistic part — each additional level has a 50% chance (like flipping a coin).

1. Link at higher levels: For each additional level, CAS the new node into the skip list at that level. This is also done with CAS, so no locks.

1. Deletion is two-phase: First, CAS-mark the node as "logically deleted" (by setting a special marker on its next pointer). Then, physically unlink it from each level. The marker prevents other threads from inserting after a deleted node, which could cause lost inserts.

Why not a tree? Balanced trees (like Red-Black trees) require rotations that touch multiple nodes simultaneously. Making rotations lock-free is extremely difficult. Skip lists only modify "next" pointers, which are perfect targets for CAS. That's why Java chose a skip list for its concurrent sorted map instead of a concurrent tree.

When to Use vs When NOT to Use

Common Mistakes & Gotchas

• **Using ConcurrentSkipListMap when you don't need sorting.** If you just need thread-safe key-value access without ordering, ConcurrentHashMap is significantly faster (O(1) vs O(log n)).
• **Forgetting that keys must be Comparable.** The map needs to sort keys. Either the key class must implement Comparable, or you must provide a Comparator at construction.
• **Relying on size() for accuracy.** size() traverses the entire bottom level and counts — it's O(n) and may not reflect concurrent modifications happening during the traversal.
• Confusing NavigableMap methods. Know the difference: floorEntry(key) returns the entry with the largest key <= key, lowerEntry(key) returns strictly < key, ceilingEntry(key) returns >= key, higherEntry(key) returns > key.
• Not understanding the memory overhead. Each node has pointers for each level it appears in. On average, each node uses ~2x the memory of a simple linked list node.

Interview Tip

If asked *"How would you implement a real-time leaderboard?"*, ConcurrentSkipListMap is the star answer. Explain: (1) it keeps scores sorted for O(log n) rank lookups, (2) it supports efficient range queries (subMap for "show players ranked 10-20"), (3) it's lock-free so reads don't block writes, and (4) iterators are weakly consistent so you can display the board while updates happen. Compare it with ConcurrentHashMap (no sorting) and Collections.synchronizedSortedMap(new TreeMap<>()) (global lock, terrible concurrency).

Quick Quiz

1. Why did Java choose a skip list instead of a balanced tree for its concurrent sorted map? (Hint: think about what CAS can and can't do efficiently.)

1. If you have 1 million entries in a ConcurrentSkipListMap, approximately how many levels would the tallest node have? (Hint: think about coin flips.)

1. You need a thread-safe sorted *set* (no values, just keys). What should you use?

Summary — Key Takeaways

• **ConcurrentSkipListMap** is a thread-safe, lock-free, sorted map based on the skip list data structure.
• It provides O(log n) search, insert, and delete — and supports range queries (subMap, headMap, tailMap) that ConcurrentHashMap cannot.
• Internally, it uses CAS on linked-list pointers instead of locks, making it highly concurrent.
• Use it when you need sorted + concurrent — leaderboards, time-series data, priority routing. If you don't need sorting, stick with ConcurrentHashMap.