ConcurrentSkipListMap is a thread-safe, sorted Map in java.util.concurrent that keeps its keys in natural order or in the order of a Comparator, and lets many threads read and write it at the same time without locks. It is the concurrent counterpart of TreeMap and implements ConcurrentNavigableMap.
We use a ConcurrentSkipListMap when shared data must stay sorted, for example a leaderboard that game servers update in parallel, price levels in an order book or jobs ordered by their run time, and when threads need range queries such as “all keys above 80”.
The following example stores player scores and runs the most common navigation calls on them.
ConcurrentSkipListMap<Integer, String> scores = new ConcurrentSkipListMap<>();
scores.put(70, "bob");
scores.put(95, "lokesh");
scores.put(82, "alex");
String all = scores.toString(); // "{70=bob, 82=alex, 95=lokesh}"
Integer atLeast80 = scores.ceilingKey(80); // 82
String top = scores.lastEntry().getValue(); // "lokesh"
NavigableMap<Integer, String> passed = scores.tailMap(80, true); // {82=alex, 95=lokesh}
Map.Entry<Integer, String> lowest = scores.pollFirstEntry(); // 70=bob, also removed
int left = scores.size(); // 2Notice that the keys come back sorted although we added them out of order, and that pollFirstEntry() reads and removes the smallest entry in one atomic step. We look at the features of the class, the skip list behind it, the constructors and navigation methods, and how it compares with ConcurrentHashMap and TreeMap.
1. Features of ConcurrentSkipListMap
The class has been in the JDK since Java 6. It extends AbstractMap and implements ConcurrentNavigableMap, so it is a SortedMap, a NavigableMap and a ConcurrentMap at once. Since Java 21, it is also a SequencedMap through SortedMap. Its main properties cover ordering, cost, locking and iteration.
- Keys are sorted by their natural order, or by the Comparator passed to the constructor.
- The methods get(), put(), remove() and containsKey() take expected average O(log n) time.
- Threads read and write concurrently without locking the map, using compare-and-swap operations.
- Iterators and views are weakly consistent, so they never throw ConcurrentModificationException.
- A null key or value throws a NullPointerException.
- Entries returned by methods such as firstEntry() are snapshots that do not support setValue().
Bulk operations such as putAll(), equals() and clear() are not atomic, so a thread that iterates during a putAll() can see only some of the new entries.
2. What is a Skip List?
A skip list is a sorted linked list with extra levels of express links that skip over many nodes, so a search can jump ahead instead of visiting every node. The bottom level links all entries in key order. Each higher level links a random subset of the nodes from the level below, about half of them per level.
A search starts at the top level and moves right while the next key is smaller than the target. When the next key is too large, the search drops one level and continues. With about half the nodes on each level, the search visits a few nodes per level and needs about log n levels, which gives the expected O(log n) cost. A plain linked list needs O(n) steps for the same search.
A balanced tree, as used by TreeMap, reaches the same cost but rebalances many nodes on insert, which is hard to do without locks. A skip list inserts a node by updating a few links at each level, and each link changes with one compare-and-swap operation. That property makes skip lists the usual choice for lock-free sorted maps. Skip lists were introduced by William Pugh in 1990.
3. Map Initialization
The class has four constructors. The default one sorts keys by their natural order, and the others take a Comparator, a Map to copy or a SortedMap whose comparator the new map keeps.
ConcurrentSkipListMap<Integer, String> natural = new ConcurrentSkipListMap<>(); // natural order
ConcurrentSkipListMap<Integer, String> highFirst = new ConcurrentSkipListMap<>(Comparator.reverseOrder()); // reverse order
ConcurrentSkipListMap<Integer, String> copied = new ConcurrentSkipListMap<>(Map.of(2, "b", 1, "a")); // {1=a, 2=b}
ConcurrentSkipListMap<String, Integer> sameOrder = new ConcurrentSkipListMap<>(new TreeMap<>(String.CASE_INSENSITIVE_ORDER)); // keeps the comparatorKeys added in any order come back sorted. With a reversed comparator, the largest key comes first, which suits a leaderboard where the best score should be at the top.
ConcurrentSkipListMap<Integer, String> leaderboard = new ConcurrentSkipListMap<>(Comparator.reverseOrder());
leaderboard.put(70, "bob");
leaderboard.put(95, "lokesh");
leaderboard.put(82, "alex");
String ranking = leaderboard.toString(); // "{95=lokesh, 82=alex, 70=bob}"Two keys that the comparator considers equal are one key, so a second put() replaces the value. A comparator on scores alone loses players with the same score, and a tie-breaker such as Comparator.comparingInt(Score::points).thenComparing(Score::player) keeps them apart.
4. Useful Operations
Besides the standard Map methods, the class offers the navigation methods of NavigableMap. Each one is safe to call while other threads add and remove keys.
4.1. Floor and Ceiling Keys
Four methods find the closest key to a given key. Each method returns null when no such key exists, and each has a variant ending in Entry that returns the whole mapping.
| Method | Returns | For key 3 in {1, 2, 4, 5} | For key 4 in {1, 2, 4, 5} |
|---|---|---|---|
| lowerKey(k) | Greatest key strictly less than k | 2 | 2 |
| floorKey(k) | Greatest key less than or equal to k | 2 | 4 |
| ceilingKey(k) | Least key greater than or equal to k | 4 | 4 |
| higherKey(k) | Least key strictly greater than k | 4 | 5 |
When the key is missing, floor equals lower and ceiling equals higher. When the key exists, floor and ceiling return the key itself, while lower and higher return its neighbors.
ConcurrentSkipListMap<Integer, String> map = new ConcurrentSkipListMap<>(Map.of(1, "a", 2, "b", 4, "d", 5, "e"));
Integer ceil3 = map.ceilingKey(3); // 4
Integer higher3 = map.higherKey(3); // 4
Integer ceil4 = map.ceilingKey(4); // 4
Integer higher4 = map.higherKey(4); // 5
Integer floor0 = map.floorKey(0); // null, no smaller key
Integer firstKey = map.firstKey(); // 1
Integer lastKey = map.lastKey(); // 54.2. Head Map and Tail Map
The methods headMap(), tailMap() and subMap() return a range of the map. The ranges are live views, not copies, so they show later changes to the map, and a put() through a view writes to the map. A boolean argument decides whether the boundary key belongs to the range.
ConcurrentSkipListMap<Integer, String> grades = new ConcurrentSkipListMap<>(Map.of(1, "a", 2, "b", 3, "c", 4, "d", 5, "e"));
ConcurrentNavigableMap<Integer, String> head = grades.headMap(3); // {1=a, 2=b}
ConcurrentNavigableMap<Integer, String> tail = grades.tailMap(3); // {3=c, 4=d, 5=e}
ConcurrentNavigableMap<Integer, String> middle = grades.subMap(2, true, 4, true); // {2=b, 3=c, 4=d}
grades.put(0, "z");
String headNow = head.toString(); // "{0=z, 1=a, 2=b}", the view is live
String outOfRange = tail.put(1, "x"); // IllegalArgumentException: key out of range4.3. Polling the First and Last Entries
The methods pollFirstEntry() and pollLastEntry() remove and return the smallest or largest entry in one atomic step. Two threads that poll at the same time never get the same entry, which makes the map a sorted work queue where each key is taken once.
ConcurrentSkipListMap<Integer, String> jobs = new ConcurrentSkipListMap<>(Map.of(30, "report", 10, "backup", 20, "email"));
Map.Entry<Integer, String> next = jobs.pollFirstEntry(); // 10=backup
Map.Entry<Integer, String> last = jobs.pollLastEntry(); // 30=report
String remaining = jobs.toString(); // "{20=email}"4.4. Descending and Sequenced Views
The method descendingMap() returns a view in reverse key order, and Java 21 added reversed() from the sequenced collections API, which returns the same kind of view. Ascending views and their iterators are faster than descending ones. The methods putFirst() and putLast() throw an UnsupportedOperationException, because the comparator decides the position of every key.
ConcurrentSkipListMap<Integer, String> ranks = new ConcurrentSkipListMap<>(Map.of(1, "a", 2, "b", 3, "c"));
NavigableMap<Integer, String> desc = ranks.descendingMap(); // {3=c, 2=b, 1=a}
SequencedMap<Integer, String> reversed = ranks.reversed(); // {3=c, 2=b, 1=a}
Map.Entry<Integer, String> firstEntry = ranks.firstEntry(); // 1=a
String front = ranks.putFirst(0, "z"); // UnsupportedOperationException
String changed = firstEntry.setValue("x"); // UnsupportedOperationExceptionThe last line shows that entries from firstEntry() are read-only snapshots. To change a value, we call put(), replace() or merge() on the map.
5. Comparison with Other Maps
A ConcurrentSkipListMap combines the sorted order of a TreeMap with the thread safety of a ConcurrentHashMap. The right choice depends on whether we need order, concurrency or both.
5.1. Difference between ConcurrentHashMap and ConcurrentSkipListMap
A ConcurrentHashMap finds a key in constant time on average, so it is faster for plain lookups by key. A ConcurrentSkipListMap needs O(log n) per lookup and keeps the keys sorted, which ConcurrentHashMap cannot do.
| Feature | ConcurrentHashMap | ConcurrentSkipListMap |
|---|---|---|
| Data structure | Hash table | Skip list |
| Key order | None | Sorted by natural order or Comparator |
| get() and put() | O(1) average | O(log n) expected average |
| Range and nearest-key queries | Not available | headMap(), ceilingKey() and more |
| Keys need | hashCode() and equals() | Comparable or a Comparator |
| Writes | Lock on one bucket | Lock-free |
| null keys or values | Rejected | Rejected |
5.2. Difference between TreeMap and ConcurrentSkipListMap
A TreeMap has the same sorted API, but it is not thread-safe. Sharing a TreeMap between threads without a lock corrupts its tree, and wrapping it with Collections.synchronizedSortedMap() lets only one thread use it at a time.
| Feature | TreeMap | ConcurrentSkipListMap |
|---|---|---|
| Since | Java 1.2 | Java 6 |
| Data structure | Red-black tree | Skip list |
| Thread-safe | No | Yes, lock-free |
| Iterators | Fail-fast, throw ConcurrentModificationException | Weakly consistent, never throw |
| null values | Allowed | Rejected |
| Single-threaded speed | Faster, no concurrency overhead | Slower per operation |
In single-threaded code, a TreeMap is the better choice. As soon as several threads write to the same sorted map, a ConcurrentSkipListMap replaces the TreeMap plus lock, and readers no longer wait for writers.
6. Keeping an Order Book Sorted Across Threads
A trading app keeps the open sell orders of one stock, grouped by price, and many threads add and cancel orders at the same time. The app needs the lowest price to show the best offer, and the total quantity at each price level. A ConcurrentSkipListMap with prices in cents as keys and quantities as values gives both without any lock in our code.
ConcurrentSkipListMap<Integer, Integer> asks = new ConcurrentSkipListMap<>();
try (ExecutorService pool = Executors.newFixedThreadPool(4)) {
pool.submit(() -> asks.merge(10_150, 200, Integer::sum));
pool.submit(() -> asks.merge(10_120, 50, Integer::sum));
pool.submit(() -> asks.merge(10_150, 100, Integer::sum));
pool.submit(() -> asks.merge(10_200, 500, Integer::sum));
}
int bestPrice = asks.firstKey(); // 10120
int qtyAt10150 = asks.get(10_150); // 300
NavigableMap<Integer, Integer> upTo10150 = asks.headMap(10_150, true); // {10120=50, 10150=300}
asks.computeIfPresent(10_120, (price, qty) -> qty - 50 == 0 ? null : qty - 50);
int newBest = asks.firstKey(); // 10150The merge() call adds quantity to a price level atomically, and computeIfPresent() removes the level when its quantity drops to zero, because a null result removes the entry. A ConcurrentHashMap would store the same data, but finding the best price would mean scanning every key.
We choose ConcurrentSkipListMap when threads share data that must stay sorted, and ConcurrentHashMap for everything else.
7. ConcurrentSkipListMap FAQs
The sorted concurrent map is often confused with its hash-based sibling, so most questions compare the two.
7.1. Is ConcurrentSkipListMap faster than ConcurrentHashMap?
No, not for lookups by key. A ConcurrentHashMap needs constant time on average, while a ConcurrentSkipListMap needs O(log n). The skip list is the faster choice only when the code needs sorted keys, ranges or the smallest and largest key, because a hash map would have to sort or scan its keys for those.
7.2. Is ConcurrentSkipListMap lock-free?
Yes. It uses compare-and-swap operations on node links instead of locks, so a thread never blocks while another thread is inside a method. Bulk operations such as putAll() and clear() are not atomic as a whole.
7.3. Are headMap() and tailMap() snapshots?
No. They are live views backed by the map, as section 4.2 shows, so they reflect later changes. To freeze a range, we copy it, for example with new TreeMap<>(map.headMap(k)). Only the single entries returned by methods such as firstEntry() are snapshots.
7.4. Does ConcurrentSkipListMap allow null keys or values?
No. Both throw a NullPointerException, because a null return value from get() must mean that the key is absent, which other threads could change between two calls.
7.5. Is there a sorted concurrent Set?
Yes. The class ConcurrentSkipListSet is built on a ConcurrentSkipListMap and has the same ordering, navigation methods and thread safety for single elements.
8. Conclusion
A ConcurrentSkipListMap keeps its keys sorted while many threads read and write it without locks. It uses a skip list with expected O(log n) operations, rejects null, and its iterators and range views are weakly consistent live views.
The navigation methods, pollFirstEntry() and the descending and sequenced views make it a good fit for leaderboards, order books and time-ordered work. For lookups by key alone, a ConcurrentHashMap is faster, and in single-threaded code a TreeMap is simpler. Other sorted and concurrent collections are listed in the Java Collections guide.
9. References
- ConcurrentSkipListMap Javadoc (Java 25)
- ConcurrentNavigableMap Javadoc (Java 25)
- JEP 431, Sequenced Collections
- William Pugh, Skip Lists, a Probabilistic Alternative to Balanced Trees (1990)
Happy Learning !!
