Quando devo usar ConcurrentSkipListMap?

Question

Em Java, ConcurrentHashMap está lá para uma melhor solução multithreading. Então, quando eu deveria usar ConcurrentSkipListMap? É uma redundância?

O multithreading aspectos entre esses dois são comuns?

Answer 1

Estas duas classes variam em alguns aspectos.

ConcurrentHashMap faz não garante * o tempo de execução de suas operações como parte de seu contrato. Também permite o ajuste para determinados factores de carga (aproximadamente, o número de segmentos simultaneamente modificando-a).

ConcurrentSkipListMap , na por outro lado, garante média O (() N log) desempenho numa ampla variedade de operações. Ele também não suporta ajuste pelo amor de concorrência. ConcurrentSkipListMap também tem uma série de operações que ConcurrentHashMap não: ceilingEntry / Key, floorEntry / Key, etc. Além disso, mantém uma ordem de classificação, que de outra forma teria de ser calculado (às custas notável) se você estivesse usando um ConcurrentHashMap <. / p>

Basicamente, diferentes implementações são fornecidos para diferentes casos de uso. Se você precisa rápida adição de chave / valor único par e pesquisa de uma única tecla rápida, use o HashMap. Se você precisar de mais rápida travessia em ordem, e pode pagar o custo extra para a inserção, utilize o SkipListMap.

_{* Apesar de esperar que a aplicação é mais ou menos em linha com o hash-mapa gerais garantias de O (1) de inserção / pesquisa; ignorando re-hash}

Answer 2

Saltar a lista para a definição da estrutura de dados. lojas A ConcurrentSkipListMap Mapa na ordem natural das suas chaves (ou alguma outra ordem da chave que você definir). Então ele vai ter mais lento get / put / contém operações que um HashMap, mas para compensar isso, ele suporta as interfaces SortedMap e NavigableMap.

Answer 3

Em termos de desempenho, skipList quando é usado como Mapa - parece ser 10-20 vezes mais lento. Aqui está o resultado dos meus testes (Java 1.8.0_102-b14, vitória 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

E, adicionalmente, para que - caso de uso de onde comparando um-para-um outro realmente faz sentido. Implementação do cache de itens de última usados ??recentemente usando ambas as coleções. Agora eficiência do skipList parece ser evento mais duvidosa.

MyBenchmark.hashMap_put1000_lru      avgt    5  0.032 ?  0.001   s/op
MyBenchmark.skipListMap_put1000_lru  avgt    5  3.332 ?  0.124   s/op

Aqui está o código para JMH (executado como 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

ConcurrentHashMap: quando vc quiser operações baseadas base em índice multithreaded get / colocar apenas de índice são suportados. Get / Put são de O (1)

ConcurrentSkipListMap: Mais do que apenas operações get / put, como top ordenada / inferior n itens por chave, obter última entrada, buscar / travessia mapa inteiro classificado por chave etc. A complexidade é de O (log (n)), para colocar desempenho não é tão grande quanto ConcurrentHashMap. It't uma implementação de ConcurrentNavigableMap com SkipList.

Para resumir uso ConcurrentSkipListMap quando você quer fazer mais operações no mapa da exigência de características ordenadas em vez de obter apenas simples e de venda.