什么时候应该使用ConcurrentSkipListMap？
在Java中， ConcurrentHashMap有更好的multithreading解决scheme。 那么我应该什么时候使用ConcurrentSkipListMap ？ 这是冗余吗？
这两者之间的multithreading方面是否共同？
这两个类别在几个方面有所不同。
ConcurrentHashMap不保证其操作的运行时作为其合约的一部分。 它还允许调整某些加载因子（粗略地说，同时修改它的线程数）。
另一方面， ConcurrentSkipListMap保证在各种操作上的平均O（log（n））性能。 它也不支持为并发而调整。 ConcurrentSkipListMap还有一些ConcurrentHashMap不支持的操作：ceilingEntry / Key，floorEntry / Key等。它还保持sorting顺序，如果使用的是ConcurrentHashMap ，则sorting顺序必须被计算（值得注意）。
基本上，针对不同的使用情况提供了不同的实现。 如果您需要快速单键/值对添加和快速单键查找，请使用HashMap 。 如果您需要更快的顺序遍历，并且可以承担额外的插入成本，请使用SkipListMap 。
*虽然我期望的实现大致符合O（1）插入/查找的一般哈希映射保证; 忽略重新哈希
有关数据结构的定义，请参见跳过列表 。 ConcurrentSkipListMap按照其键的自然顺序（或您定义的其他键顺序）存储Map。 所以它比getHashMap有更慢的get / put / contains操作，但是为了抵消它，它支持SortedMap和NavigableMap接口。
在性能方面，当skipList用作Map时，似乎慢了10-20倍。 这是我testing的结果（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
除此之外 – 在一对一比较的情况下真的很有意义。 使用这两个集合实现最近使用的项目的caching。 现在SkipList的效率看起来更可疑。
MyBenchmark.hashMap_put1000_lru avgt 5 0.032 ? 0.001 s/op MyBenchmark.skipListMap_put1000_lru avgt 5 3.332 ? 0.124 s/op
这里是JMH的代码（执行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); } } } }
