ConcurrentSkipListMap vs TreeMap for concurrent sorted access.

TreeMap is a red-black tree with no thread safety — sharing it across threads needs external locking. ConcurrentSkipListMap is a lock-free skip list designed for concurrent access from the ground up, and it's the JDK's only concurrent NavigableMap.

Side-by-side

Making TreeMap "concurrent" — and why it's not great

SortedMap<String, Integer> sm =
    Collections.synchronizedSortedMap(new TreeMap<>());

sm.put("k", 1);                   // synchronized on the wrapper
Integer v = sm.get("k");          // synchronized

// Iteration STILL requires manual synchronization
synchronized (sm) {
    for (var e : sm.entrySet()) { ... }
}

Every operation serializes on a single monitor — there's no concurrency, just thread safety. And the iteration gotcha is easy to forget: the per-method synchronized doesn't span hasNext() and next().

ConcurrentSkipListMap — what you actually want

ConcurrentNavigableMap<Long, Order> orders = new ConcurrentSkipListMap<>();

orders.put(System.nanoTime(), order);                      // lock-free
Map.Entry<Long, Order> oldest = orders.firstEntry();       // O(log n)
NavigableMap<Long, Order> recent =
    orders.tailMap(cutoff, true);                          // live view

orders.compute(key, (k, v) -> v == null ? new Order() : v.bumped()); // atomic

You get:

• Concurrent reads and writes with no global lock.
• Weakly consistent iteration — never throws CME, no manual sync needed.
• Atomic compound operations (putIfAbsent, compute, merge).
• Range views (subMap, headMap, tailMap) that are themselves thread-safe.

Why skip list, not a concurrent tree?

Balanced trees are hard to make lock-free — rebalancing touches many nodes atomically. Skip lists rebalance probabilistically (random level on insert), so writes only update a small number of forward pointers, each via CAS. This keeps the lock-free implementation tractable.

Cost summary