我什么时候应该使用ConcurrentSkipListMap？

Question

在Java中,ConcurrentHashMap是否有更好的multithreading解决方案.那我ConcurrentSkipListMap什么时候应该用？这是一种冗余吗？

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

Answer 1

这两个类别在某些方面有所不同.

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

另一方面,ConcurrentSkipListMap保证了各种操作的平均O(log(n))性能.它也不支持为并发调整. ConcurrentSkipListMap也有一些操作是ConcurrentHashMap不会:如果你使用的是ceilingEntry /关键,floorEntry /钥匙等,这也保持了排序顺序,否则必须被计算(在显着的费用)ConcurrentHashMap.

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

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

Answer 2

有关数据结构的定义,请参见跳过列表.ConcurrentSkipListMap以其键的自然顺序(或您定义的其他键顺序)存储Map.因此它比HashMap具有更慢的get/put/contains操作,但为了抵消它,它支持SortedMap和NavigableMap接口.

Answer 3

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

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

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

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

ConcurrentHashMap

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

ConcurrentSkipListMap

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

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

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