When should I use ConcurrentSkipListMap?
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
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.
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 UnitsMyBenchmark.hasMap_get avgt 5 0.015 ? 0.001 s/opMyBenchmark.hashMap_put avgt 5 0.029 ? 0.004 s/opMyBenchmark.skipListMap_get avgt 5 0.312 ? 0.014 s/opMyBenchmark.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/opMyBenchmark.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); }}@Benchmarkpublic 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); } }}@Benchmarkpublic 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); } }}@Benchmarkpublic 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); } }}@Benchmarkpublic 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); } }}@Benchmarkpublic 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()); } } }}@Benchmarkpublic 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); } } }}