ConcurrentSkipListMap and ConcurrentSkipListSet?

• ConcurrentSkipListMap – thread-safe sorted map backed by a skip list, O(log n) access.
• NavigableMap API – firstKey, lastKey, ceilingKey, floorKey, subMap, headMap, tailMap.
• Skip list – layered linked list: bottom layer sorted, upper layers are express lanes for logarithmic search.
• Lock-free – uses CAS on node links instead of a global lock.
• ConcurrentSkipListSet – the sorted set built on the same structure.
• Decision – choose over ConcurrentHashMap only when you need sorted keys or range queries.

What is ConcurrentSkipListMap?

A thread-safe sorted map that keeps keys in natural or custom comparator order, backed by a skip list data structure that provides O(log n) access for get, put, and remove.

package com.bank.trading;

import java.math.BigDecimal;
import java.util.concurrent.ConcurrentSkipListMap;

public class OrderBookDemo {
    public static void main(String[] args) {
        ConcurrentSkipListMap<BigDecimal, Order> asks = new ConcurrentSkipListMap<>();
        asks.put(new BigDecimal("2450.50"), new Order("ORD-1", 100));
        asks.put(new BigDecimal("2448.00"), new Order("ORD-2", 200));
        asks.put(new BigDecimal("2451.75"), new Order("ORD-3", 50));
        System.out.println("Best ask: " + asks.firstKey()); // 2448.00
    }
}

What navigation methods does it support?

ConcurrentSkipListMap implements NavigableMap, providing rich sorted-access methods.

BigDecimal bestAsk = asks.firstKey();  // lowest price: 2448.00
BigDecimal worstAsk = asks.lastKey();  // highest price: 2451.75

// Nearest key at or above a target price
Map.Entry<BigDecimal, Order> nearest = asks.ceilingEntry(new BigDecimal("2449"));
// Returns 2450.50 entry (first at or above 2449)

// Nearest key at or below a target price
Map.Entry<BigDecimal, Order> floor = asks.floorEntry(new BigDecimal("2449"));
// Returns 2448.00 entry (first at or below 2449)

// Live sorted view of all orders in a price band
var band = asks.subMap(
    new BigDecimal("2400"), true,   // inclusive lower
    new BigDecimal("2500"), false); // exclusive upper
// Returns a live NavigableMap view: changes to asks are reflected

How does a skip list work internally?

The bottom layer holds all elements in sorted order as a linked list. Each element is promoted to higher express lanes with decreasing probability (typically 50%). A search starts at the top-left, moves right until the next node overshoots, drops down one level, and repeats. This gives O(log n) search time with O(n) space.

How is concurrency achieved?

Insertions and deletions use compare-and-swap on individual node links rather than a global lock. This means multiple threads can modify different parts of the skip list simultaneously. Iterators are weakly consistent: they never throw ConcurrentModificationException but may or may not reflect changes made after the iterator was created.

When do you choose ConcurrentSkipListMap over ConcurrentHashMap?

| Feature | ConcurrentHashMap | ConcurrentSkipListMap |
|---------|------------------|-----------------------|
| Lookup time | O(1) average | O(log n) |
| Ordering | None | Sorted by key |
| Range queries | Not supported | subMap, headMap, tailMap |
| Nearest-key | Not supported | ceilingKey, floorKey |
| Lock-free reads | Yes | Yes |
| Memory overhead | Lower | Higher (skip list layers) |
| Iteration order | Undefined | Sorted |

Choose the skip list only when the domain needs sorted iteration, range scans, or nearest-key lookups. For pure key-value lookups, ConcurrentHashMap is always faster.

How is it used in a banking order book?

At National Bank of India, the equity order book keeps two ConcurrentSkipListMaps: one for asks (buy orders sorted by ascending price) and one for bids (sell orders sorted by descending price using a reversed comparator). The best ask is asks.firstKey() and the best bid is bids.firstKey(). Price-band queries for market surveillance are a single subMap call.

package com.bank.trading;

import java.math.BigDecimal;
import java.util.concurrent.ConcurrentSkipListMap;
import java.util.Comparator;

public class OrderBook {
    private final ConcurrentSkipListMap<BigDecimal, Order> asks =
        new ConcurrentSkipListMap<>();
    private final ConcurrentSkipListMap<BigDecimal, Order> bids =
        new ConcurrentSkipListMap<>(Comparator.reverseOrder());

    public BigDecimal getBestAsk() { return asks.firstKey(); }
    public BigDecimal getBestBid() { return bids.firstKey(); }
    public BigDecimal getSpread() { return getBestAsk().subtract(getBestBid()); }
}

What are common mistakes?

Using ConcurrentSkipListMap when you do not need ordering wastes performance. O(log n) is slower than O(1) for every operation. Another mistake is assuming that compound operations (check-then-act) are atomic. Individual operations are thread-safe, but if (!map.containsKey(k)) map.put(k, v) is not atomic. Use putIfAbsent() instead.

What are common interview follow-up questions?

• How does the skip list compare to a balanced tree? Both give O(log n) but skip lists are easier to make lock-free because they use linked-list modifications rather than tree rotations.
• What is ConcurrentSkipListSet used for? It is a NavigableSet backed by ConcurrentSkipListMap. Used when you need a sorted, concurrent set.
• How does the probabilistic layer promotion work? Each new node is promoted with a fixed probability (typically 0.5) at each level. On average, the structure has O(log n) levels.