Then when should I use ConcurrentSkipListMap?

When you (a) need to keep keys sorted, and/or (b) need the first/last, head/tail, and submap features of a navigable map.

The ConcurrentHashMap class implements the ConcurrentMap interface, as does ConcurrentSkipListMap. But if you also want the behaviors of SortedMap and NavigableMap, use ConcurrentSkipListMap

ConcurrentHashMap

• ❌ Sorted
• ❌ Navigable
• ✅ Concurrent

ConcurrentSkipListMap

• ✅ Sorted
• ✅ Navigable
• ✅ Concurrent

Here is table guiding you through the major features of the various Map implementations bundled with Java 11. Click/tap to zoom.

Keep in mind that you can obtain other Map implementations, and similar such data structures, from other sources such as Google Guava.

Based on workloads ConcurrentSkipListMap could be slower than TreeMap with synchronized methods as in KAFKA-8802 if range queries are needed.

ConcurrentHashMap : when u want multithreaded index based get/put, only index based operations are supported. Get/Put are of O(1)

ConcurrentSkipListMap : More operations than just get/put, like sorted top/bottom n items by key, get last entry, fetch/traverse whole map sorted by key etc. Complexity is of O(log(n)), So put performance is not as great as ConcurrentHashMap. It't an implementation of ConcurrentNavigableMap with SkipList.

To summarize use ConcurrentSkipListMap when you want to do more operations on map requiring sorted features rather than just simple get and put.