When should I use ConcurrentSkipListMap?
Solution 1
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
Solution 2
Sorted, navigable, and concurrent
See Skip List for a definition of the data structure.
A ConcurrentSkipListMap
stores the Map
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 HashMap
, but to offset this it supports the SortedMap
, NavigableMap
, and ConcurrentNavigableMap
interfaces.
Solution 3
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);
}
}
}
}
Solution 4
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.
Solution 5
Based on workloads ConcurrentSkipListMap could be slower than TreeMap with synchronized methods as in KAFKA-8802 if range queries are needed.
DKSRathore
I am a keen learner of anything related to programming, especially java, threading and data structures
Updated on July 06, 2020Comments
-
DKSRathore almost 4 years
In Java,
ConcurrentHashMap
is there for bettermultithreading
solution. Then when should I useConcurrentSkipListMap
? Is it a redundancy?Does multithreading aspects between these two are common?
-
DKSRathore over 14 yearsOk. Log(n) is fine but does ConcurrentSkipListMap is space efficient?
-
Kevin Montrose over 14 yearsSkip lists are necessarily larger than Hashtables, but the tunable nature of ConcurrentHashMap makes it possible to construct a Hashtable that is larger than the equivalent ConcurrentSkipListMap. In general, I'd expect the skip list to be larger but on the same order of magnitude.
-
Pacerier about 12 years"It also does not support tuning for concurrency's sake".. Why? What is the link?
-
Kevin Montrose about 12 years@Pacerier - I didn't mean it does support tuning because it's concurrent, I mean it doesn't allow you to tune parameters that influence it's concurrent performance (while ConcurrentHashMap does).
-
Pacerier about 12 years@KevinMontrose Ic, so you meant "It also does not support concurrency tuning."
-
abbas over 4 yearsI think ConcurrentSkipListMap should be compared to their non-concurrent counter part, the TreeMap.
-
yusong over 4 yearsThanks for sharing. I am justing thinking to replace TreeMap with ConcurrentSkipListMap in one of my project, so it is good to know this! Do you have more context about why ConcurrentSkipListMap is slower, and more detail about performance comparison?
-
Basil Bourque over 4 yearsAs abbas commented, comparing performance to ConcurrentHashMap seems silly. The purpose of ConcurrentSkipListMap is to (a) provide concurrency, and (b) maintain sort-order amongst the keys. ConcurrentHashMap does a, but not b. Comparing the 0-to-60 speed of a Tesla and a dump truck is senseless, as they serve different purposes.
-
Xtra Coder over 4 yearsWhile you don't know performance metrics you don't know which one is Tesla and which one is "dump truck" :) Also ... you do not know the price of "b" without metrics. Therefore - comparing performance is generally useful thing.
-
simgineer about 4 yearsMaybe add a comparison to tree map! :D
-
AnV over 3 yearsThis picture is awesome. Do you have similar pictures for some or all of normal and concurrent collections?
-
Basil Bourque over 3 years@Anv Thanks, making that chart took quite a bit of work. It is part of my presentation for Java user groups: A map to Java Maps. And, No, I’ve made just one other class diagram, for
String
related classes and interface. -
Robert over 2 yearsSkip lists are much more memory efficient. For me that's more important than a few milliseconds in lookups.
-
Robert over 2 yearsI find it odd that everyone likes to compare time complexity in the absence of required space. SkipLists are much more memory efficient (a point that I think is worth noting)
-
Alec over 2 yearsIt feels a little bit weird to benchmark the performance of a datastructure meant for concurrent access only single threaded. This would be more interesting with more threads (even just
-tc 1,2,4,8
to see performance with 1, 2, 4, 8 threads). I expect concurrent hashmap (even with the default config) would trounce concurrent skip list map, but the curve in vertical scalability could be interesting.