Sorted, navigable, and concurrent

See Skip List for a definition of the data structure.

A ConcurrentSkipListMap stores the Map0 in the natural order of its keys (or some other key order you define). So it'll have slower get/put/contains operations than a Map1, but to offset this it supports the Map2, Map3, and Map4 interfaces.

These two classes vary in a few ways.

ConcurrentHashMap does not guarantee* the runtime of its operations as part of its contract. It also allows tuning for certain load factors (roughly, the number of threads concurrently modifying it).

ConcurrentSkipListMap, on the other hand, guarantees average O(log(n)) performance on a wide variety of operations. It also does not support tuning for concurrency's sake. ConcurrentSkipListMap also has a number of operations that ConcurrentHashMap doesn't: ceilingEntry/Key, floorEntry/Key, etc. It also maintains a sort order, which would otherwise have to be calculated (at notable expense) if you were using a ConcurrentHashMap.

Basically, different implementations are provided for different use cases. If you need quick single key/value pair addition and quick single key lookup, use the HashMap. If you need faster in-order traversal, and can afford the extra cost for insertion, use the SkipListMap.

_{*Though I expect the implementation is roughly in line with the general hash-map guarantees of O(1) insertion/lookup; ignoring re-hashing}

In terms of performance, skipList when is used as Map - appears to be 10-20 times slower. Here is the result of my tests (Java 1.8.0_102-b14, win x32)

Benchmark                    Mode  Cnt  Score    Error  Units
MyBenchmark.hasMap_get       avgt    5  0.015 ?  0.001   s/op
MyBenchmark.hashMap_put      avgt    5  0.029 ?  0.004   s/op
MyBenchmark.skipListMap_get  avgt    5  0.312 ?  0.014   s/op
MyBenchmark.skipList_put     avgt    5  0.351 ?  0.007   s/op

And additionally to that - use-case where comparing one-to-another really makes sense. Implementation of the cache of last-recently-used items using both of these collections. Now efficiency of skipList looks to be event more dubious.

MyBenchmark.hashMap_put1000_lru      avgt    5  0.032 ?  0.001   s/op
MyBenchmark.skipListMap_put1000_lru  avgt    5  3.332 ?  0.124   s/op

Here is the code for JMH (executed as java -jar target/benchmarks.jar -bm avgt -f 1 -wi 5 -i 5 -t 1)

static final int nCycles = 50000;
static final int nRep = 10;
static final int dataSize = nCycles / 4;
static final List<String> data = new ArrayList<>(nCycles);
static final Map<String,String> hmap4get = new ConcurrentHashMap<>(3000, 0.5f, 10);
static final Map<String,String> smap4get = new ConcurrentSkipListMap<>();


static {
// prepare data
List<String> values = new ArrayList<>(dataSize);
for( int i = 0; i < dataSize; i++ ) {
values.add(UUID.randomUUID().toString());
}
// rehash data for all cycles
for( int i = 0; i < nCycles; i++ ) {
data.add(values.get((int)(Math.random() * dataSize)));
}
// rehash data for all cycles
for( int i = 0; i < dataSize; i++ ) {
String value = data.get((int)(Math.random() * dataSize));
hmap4get.put(value, value);
smap4get.put(value, value);
}
}


@Benchmark
public void skipList_put() {
for( int n = 0; n < nRep; n++ ) {
Map<String,String> map = new ConcurrentSkipListMap<>();


for( int i = 0; i < nCycles; i++ ) {
String key = data.get(i);
map.put(key, key);
}
}
}


@Benchmark
public void skipListMap_get() {
for( int n = 0; n < nRep; n++ ) {
for( int i = 0; i < nCycles; i++ ) {
String key = data.get(i);
smap4get.get(key);
}
}
}


@Benchmark
public void hashMap_put() {
for( int n = 0; n < nRep; n++ ) {
Map<String,String> map = new ConcurrentHashMap<>(3000, 0.5f, 10);


for( int i = 0; i < nCycles; i++ ) {
String key = data.get(i);
map.put(key, key);
}
}
}


@Benchmark
public void hasMap_get() {
for( int n = 0; n < nRep; n++ ) {
for( int i = 0; i < nCycles; i++ ) {
String key = data.get(i);
hmap4get.get(key);
}
}
}


@Benchmark
public void skipListMap_put1000_lru() {
int sizeLimit = 1000;


for( int n = 0; n < nRep; n++ ) {
ConcurrentSkipListMap<String,String> map = new ConcurrentSkipListMap<>();


for( int i = 0; i < nCycles; i++ ) {
String key = data.get(i);
String oldValue = map.put(key, key);


if( (oldValue == null) && map.size() > sizeLimit ) {
// not real lru, but i care only about performance here
map.remove(map.firstKey());
}
}
}
}


@Benchmark
public void hashMap_put1000_lru() {
int sizeLimit = 1000;
Queue<String> lru = new ArrayBlockingQueue<>(sizeLimit + 50);


for( int n = 0; n < nRep; n++ ) {
Map<String,String> map = new ConcurrentHashMap<>(3000, 0.5f, 10);


lru.clear();
for( int i = 0; i < nCycles; i++ ) {
String key = data.get(i);
String oldValue = map.put(key, key);


if( (oldValue == null) && lru.size() > sizeLimit ) {
map.remove(lru.poll());
lru.add(key);
}
}
}
}

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.

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

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 ConcurrentMap0, 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.