¿Cuándo debo usar ConcurrentSkipListMap?

Question

En Java, ConcurrentHashMap está ahí para una mejor solución multithreading . Entonces, ¿cuándo debo usar ConcurrentSkipListMap ? ¿Es una redundancia?

¿Son comunes los aspectos de subprocesamiento múltiple entre estos dos?

Answer 1

Estas dos clases varían de varias maneras.

ConcurrentHashMap does no garantiza * el tiempo de ejecución de sus operaciones como parte de su contrato. También permite ajustar ciertos factores de carga (aproximadamente, el número de subprocesos que lo modifican simultáneamente).

ConcurrentSkipListMap , en el Por otro lado, garantiza el rendimiento promedio de O (log (n)) en una amplia variedad de operaciones. Tampoco admite ajustes por simultaneidad. ConcurrentSkipListMap también tiene una serie de operaciones que ConcurrentHashMap no: ceilingEntry / Key, floorEntry / Key, etc. También mantiene un orden de clasificación, que de otro modo tendría que ser calculado (a un costo notable) si estaba utilizando un ConcurrentHashMap .

Básicamente, se proporcionan diferentes implementaciones para diferentes casos de uso. Si necesita una adición rápida de un par de clave / valor y una búsqueda rápida de una sola clave, use el HashMap . Si necesita un recorrido en orden más rápido y puede pagar el costo adicional para la inserción, use el SkipListMap .

_{* Aunque espero que la implementación esté más o menos en línea con las garantías generales de hash-map de inserción / búsqueda de O (1); ignorando el nuevo hash}

Answer 2

Consulte Skip List para obtener una definición de la estructura de datos. Un ConcurrentSkipListMap almacena el Mapa en el orden natural de sus teclas (o algún otro orden de teclas que defina). Por lo tanto, tendrá operaciones de obtención / colocación / contención más lentas que un HashMap, pero para compensar esto es compatible con las interfaces SortedMap y NavigableMap.

Answer 3

En términos de rendimiento, skipList cuando se usa como Map - parece ser 10-20 veces más lento. Aquí está el resultado de mis pruebas (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

Y además de eso, el caso de uso donde comparar uno a otro realmente tiene sentido. Implementación de la memoria caché de los últimos elementos utilizados recientemente utilizando ambas colecciones. Ahora la eficacia de skipList parece ser un evento más dudoso.

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

Aquí está el código para JMH (ejecutado 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: cuando desea get / put basado en índices multiproceso, solo se admiten operaciones basadas en índices. Get / Put son de O (1)

ConcurrentSkipListMap: más operaciones que solo get / put, como n elementos superiores / inferiores ordenados por clave, obtener la última entrada, buscar / recorrer todo el mapa ordenado por clave, etc. La complejidad es de O (log (n)), así que ponga El rendimiento no es tan bueno como ConcurrentHashMap. No es una implementación de ConcurrentNavigableMap con SkipList.

Para resumir, use ConcurrentSkipListMap cuando desee realizar más operaciones en el mapa que requieran entidades ordenadas en lugar de simplemente obtener y colocar.