Java 什么时候应该使用 ConcurrentSkipListMap？

When should I use ConcurrentSkipListMap?

提问by DKSRathore

In Java, ConcurrentHashMapis there for better multithreadingsolution. Then when should I use ConcurrentSkipListMap? Is it a redundancy?

在 Java 中，ConcurrentHashMap是否有更好的multithreading解决方案。那我应该什么时候使用ConcurrentSkipListMap？是冗余吗？

Does multithreading aspects between these two are common?

这两者之间的多线程方面是否常见？

采纳答案by Kevin Montrose

These two classes vary in a few ways.

这两个类在几个方面有所不同。

ConcurrentHashMapdoes 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).

ConcurrentHashMap不保证*其操作的运行时间作为其合同的一部分。它还允许调整某些负载因子（粗略地说，同时修改它的线程数）。

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. ConcurrentSkipListMapalso has a number of operations that ConcurrentHashMapdoesn'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.

另一方面，ConcurrentSkipListMap保证了各种操作的平均 O(log(n)) 性能。它也不支持为了并发而进行调优。 ConcurrentSkipListMap还有一些没有的操作ConcurrentHashMap：ceilingEntry/Key、floorEntry/Key 等。它还维护一个排序顺序，否则如果您使用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.

基本上，为不同的用例提供了不同的实现。如果您需要快速单键/值对添加和快速单键查找，请使用HashMap. 如果您需要更快的有序遍历，并且可以负担额外的插入成本，请使用SkipListMap.

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

_{*虽然我希望实现大致符合 O(1) 插入/查找的一般哈希映射保证；忽略重新散列}

回答by Jim Ferrans

Sorted, navigable, and concurrent

排序、可导航和并发

See Skip Listfor a definition of the data structure.

有关数据结构的定义，请参阅跳过列表。

A ConcurrentSkipListMapstores the Mapin the natural order of its keys (or some other key order you define). So it'll have slower get/put/containsoperations than a HashMap, but to offset this it supports the SortedMap, NavigableMap, and ConcurrentNavigableMapinterfaces.

一个ConcurrentSkipListMap存储Map在它的键的自然顺序（或者你定义了其他一些重要的顺序）。因此，这将有慢get/ put/contains不是一个业务HashMap，而是来抵消这种支持的SortedMap，NavigableMap和ConcurrentNavigableMap接口。

回答by Xtra Coder

In terms of performance, skipListwhen 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)

在性能方面，skipList当用作 Map - 似乎慢 10-20 倍。这是我的测试结果（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.

除此之外 - 一对一比较真正有意义的用例。使用这两个集合实现上次最近使用的项目的缓存。现在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

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

这是 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);
            }
        }
    }
}

回答by spats

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

ConcurrentHashMap ：当你想要基于多线程索引的 get/put 时，只支持基于索引的操作。Get/Put 是 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.

ConcurrentSkipListMap ：不仅仅是获取/放置更多的操作，比如按键排序顶部/底部 n 项，获取最后一个条目，获取/遍历按键排序的整个地图等。复杂性是 O(log(n))，所以 put 性能不是和 ConcurrentHashMap 一样伟大。它不是 ConcurrentNavigableMap 与 SkipList 的实现。

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

总而言之，当您想要对需要排序功能的地图进行更多操作而不是简单的获取和放置时，请使用 ConcurrentSkipListMap。

回答by Anush

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

基于工作负载，如果需要范围查询，ConcurrentSkipListMap 可能比KAFKA-8802 中使用同步方法的 TreeMap 慢。

回答by Basil Bourque

Then when should I use ConcurrentSkipListMap?

那么我应该什么时候使用 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.

当您 (a) 需要对键进行排序，和/或 (b) 需要可导航地图的第一个/最后一个、头/尾和子地图功能时。

The ConcurrentHashMapclass implements the ConcurrentMapinterface, as does ConcurrentSkipListMap. But if you also want the behaviors of SortedMapand NavigableMap, use ConcurrentSkipListMap

本ConcurrentHashMap类实现了ConcurrentMap接口，一样ConcurrentSkipListMap。但是，如果您还想要SortedMapand的行为NavigableMap，请使用ConcurrentSkipListMap

ConcurrentHashMap

ConcurrentHashMap

• ? Sorted
• ? Navigable
• ? Concurrent

• ? 已排序
• ? 通航
• ? 同时

ConcurrentSkipListMap

ConcurrentSkipListMap

• ? Sorted
• ? Navigable
• ? Concurrent

• ? 已排序
• ? 通航
• ? 同时

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

下表指导您了解Map与 Java 11 捆绑在一起的各种实现的主要功能。单击/点击以进行缩放。

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

请记住，您可以Map从其他来源（例如Google Guava ）获取其他实现和类似的此类数据结构。