ConcurrentSkipListMap

ConcurrentSkipListMap provides an alternative to ConcurrentHashMap for when you need a sorted (ordered) concurrent map. It uses a probabilistic “skip list” data structure for high performance without conventional locking.

Source Code #

View Source on GitHub

Implementation Mechanism #

A skip list is a linked list with several levels of indices. Each higher level has fewer nodes, which allows searching to “skip” large parts of the list. This provides average O(log n) time for most operations.

// Two-dimensionally linked skip list structure
static class Node<K,V> {
    final K key;
    volatile Object value;
    volatile Node<K,V> next;
    // ... 
}

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

Unlike TreeMap which uses a red-black tree and requires complex rebalancing with locks, ConcurrentSkipListMap is lock-free for most operations. It uses CAS to link and unlink nodes, which scales much better than a locked tree structure on multi-core systems.

Canonical Usage #

When to use: Use ConcurrentSkipListMap when you need a thread-safe sorted map (supporting ConcurrentNavigableMap) or when you need to perform range queries (e.g., subMap, headMap, tailMap).

Common Patterns:

• Range Scans: Finding all keys between A and B concurrently.
• Lowest/Highest Key: Efficiently finding the minimum or maximum element in a thread-safe way.

ConcurrentNavigableMap<Integer, String> sensorData = new ConcurrentSkipListMap<>();

// Get all data within a specific time range
Map<Integer, String> window = sensorData.subMap(1000, 2000);

// Find the earliest record
Map.Entry<Integer, String> earliest = sensorData.firstEntry();

Performance Trade-offs #

• Pros: Sorted by key. Lock-free scalability. Efficient range queries. Supports NavigableMap methods.
• Cons: Slower than ConcurrentHashMap for individual get() and put() operations due to its O(log n) search path. More memory allocation due to the multiple layers of index nodes.