What are ConcurrentSkipListMap and ConcurrentSkipListSet, and when would you use them?

## The need Sometimes you need a thread-safe collection that also keeps its elements **sorted** and supports **range queries** ("give me every key from 100 to 200", "the smallest key ≥ x"). `ConcurrentHashMap` is thread-safe but unordered, and `TreeMap`/`TreeSet` are sorted but *not* thread-safe. The JDK fills the gap with **ConcurrentSkipListMap** (sorted map) and **ConcurrentSkipListSet** (sorted set, internally backed by a skip-list map). ## Key terms (from scratch) - **Sorted / NavigableMap**: a map whose keys are kept in a defined order, exposing navigation methods like `firstKey()`, `lastKey()`, `ceilingKey(k)` (smallest key ≥ k), `floorKey(k)` (largest key ≤ k), and range *views* like `headMap`, `tailMap`, `subMap`. - **Natural ordering / Comparator**: keys are ordered either by their own `compareTo` (natural ordering) or by a `Comparator` you pass to the constructor. - **Red-black tree**: the balanced binary search tree that backs `TreeMap`. Balancing requires rotations that touch several nodes at once, which is hard to do concurrently without coarse locking. - **Skip list**: an alternative ordered structure. Picture a base linked list of all nodes in sorted order, with several *express* linked lists stacked on top, each skipping over more nodes (like express vs local subway lines). To search, you start at the top express lane and drop down a level whenever the next node would overshoot the target, ending at the right spot. A node's height is chosen randomly (probabilistically), which keeps the structure balanced *on average* with expected **O(log n)** search/insert/delete — without the global rebalancing rotations a tree needs. ## Why a skip list for concurrency The whole point is that a skip list is dramatically easier to make **lock-free** than a balanced tree. Inserts and deletes touch only a few `next` pointers along the search path and can be done with **CAS** operations, with no whole-tree rotation. So `ConcurrentSkipListMap` achieves scalable concurrent access (many threads reading and writing) without a global lock — that is why the JDK chose a skip list instead of a concurrent red-black tree. ## Properties and gotchas - **Interfaces**: they implement `ConcurrentNavigableMap` / `ConcurrentNavigableSet`, so all the navigation and range operations are available and thread-safe, and range views (`subMap`, etc.) are live, concurrent sub-views. - **No null keys/values** (a key of `null` can't be ordered). - **Weakly consistent iterators**: they reflect some state at/after creation, never throw `ConcurrentModificationException`, and don't promise a snapshot. - **`size()` is not constant-time and is an estimate**: like other non-blocking collections, it may traverse and is only approximate under concurrent modification — don't rely on it for control flow. - **Performance**: expected O(log n) operations (vs O(1) average for hash maps). Comparisons are done via the key's `compareTo`/`Comparator`, so an inconsistent or expensive comparator hurts correctness/performance. ## ConcurrentHashMap vs ConcurrentSkipListMap — choosing - Need only key→value lookups, no ordering? Use **ConcurrentHashMap** — O(1) average, faster. - Need keys kept **sorted**, or need **range / nearest-key** queries (ceiling/floor/headMap/subMap), concurrently? Use **ConcurrentSkipListMap**. The ordering costs you the jump from O(1) to O(log n). Typical uses: concurrent leaderboards or time-ordered event indexes (range scans by timestamp), priority-by-key structures, or any place you'd want a thread-safe `TreeMap`.