我什么时候应该使用ConcurrentSkipListMap？

Question

在 Java 中，ConcurrentHashMap 提供了更好的多线程解决方案。那么什么时候应该使用ConcurrentSkipListMap呢？是不是冗余？

这两者之间的多线程方面是否共同？

Answer 1

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

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

另一方面，ConcurrentSkipListMap，保证各种操作的平均 O(log(n)) 性能。它也不支持并发调整。 ConcurrentSkipListMap 还具有许多 ConcurrentHashMap 没有的操作：ceilingEntry/Key、floorEntry/Key 等。它还维护排序顺序，否则必须是如果您使用 ConcurrentHashMap，则计算（花费大量费用）。

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

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

Answer 2

排序、可导航和并发

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

< code>ConcurrentSkipListMap 存储 Map 按照其键的自然顺序（或您定义的其他键顺序）。因此，它的 get/put/contains 操作比 HashMap，但为了抵消它支持SortedMap，NavigableMap 和 ConcurrentNavigableMap 接口。

Answer 3

那么什么时候应该使用ConcurrentSkipListMap？

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

ConcurrentHashMap 类实现 ConcurrentMap 接口，ConcurrentSkipListMap。但如果您还想要 SortedMap 和 NavigableMap，使用 ConcurrentSkipListMap

ConcurrentHashMap

• ❌ 已排序
• ❌ 可导航
• ✅ 并发

ConcurrentSkipListMap

• ✅ 已排序
• ✅ 可导航
• ✅ 并发

这是一个表格，指导您了解各种 Map 与 Java 11 捆绑在一起的实现。单击/点击进行缩放。

请记住，您可以获得其他 Map 实现以及类似的数据结构，来自其他来源，例如 Google Guava。

Answer 4

在性能方面，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

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

Answer 5

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

Answer 6

ConcurrentHashMap ：当您想要基于多线程索引的 get/put 时，仅支持基于索引的操作。 Get/Put 的复杂度为 O(1)

ConcurrentSkipListMap ：不仅仅是 get/put 的更多操作，例如按键排序顶部/底部 n 个项目、获取最后一个条目、获取/遍历按键排序的整个映射等。复杂度为 O(log( n)), 所以put性能不如ConcurrentHashMap。它不是带有 SkipList 的 ConcurrentNavigableMap 的实现。

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