Quando dovrei usare ConcurrentSkipListMap?

Question

In Java, ConcurrentHashMap è disponibile per una migliore soluzione multithreading . Quindi quando devo usare ConcurrentSkipListMap ? È una ridondanza?

Gli aspetti multithreading tra questi due sono comuni?

Answer 1

Queste due classi variano in alcuni modi.

ConcurrentHashMap non garantisce * la durata delle sue operazioni come parte del suo contratto. Inoltre, consente di ottimizzare determinati fattori di carico (approssimativamente, il numero di thread che lo modificano contemporaneamente).

ConcurrentSkipListMap , sul d'altra parte, garantisce prestazioni O (log (n)) medie su un'ampia varietà di operazioni. Inoltre, non supporta l'ottimizzazione per motivi di concorrenza. ConcurrentSkipListMap ha anche una serie di operazioni che ConcurrentHashMap non esegue: ceilingEntry / Key, floorEntry / Key, ecc. Mantiene anche un ordinamento, che altrimenti dovrebbe essere calcolato (a spese notevoli) se si utilizzava un ConcurrentHashMap .

Fondamentalmente, sono previste diverse implementazioni per diversi casi d'uso. Se hai bisogno di aggiungere rapidamente una chiave singola / coppia di valori e una rapida ricerca della chiave singola, usa HashMap . Se hai bisogno di un attraversamento in ordine più rapido e puoi permetterti il ??costo aggiuntivo per l'inserimento, usa la SkipListMap .

_{* Anche se mi aspetto che l'implementazione sia più o meno in linea con le garanzie generali di hash-map relative all'inserzione / ricerca di O (1); ignorando il re-hashing}

Answer 2

Vedi Skip List per una definizione della struttura dei dati. Una ConcurrentSkipListMap memorizza la mappa nell'ordine naturale delle sue chiavi (o in qualche altro ordine di chiavi definito). Quindi avrà operazioni get / put / contiene più lente di una HashMap, ma per compensare ciò supporta le interfacce SortedMap e NavigableMap.

Answer 3

In termini di prestazioni, skipList quando viene usato come Mappa - sembra essere 10-20 volte più lento. Ecco il risultato dei miei test (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

E in aggiunta a ciò - caso d'uso in cui il confronto tra loro ha davvero senso. Implementazione della cache degli ultimi elementi utilizzati di recente utilizzando entrambe queste raccolte. Ora l'efficienza di skipList sembra essere l'evento più incerto.

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

Ecco il codice per JMH (eseguito come 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 vuoi get / put basato su indice multithread, sono supportate solo operazioni basate su indice. Ottieni / Put sono di O (1)

ConcurrentSkipListMap: più operazioni oltre al semplice get / put, come l'ordinamento in alto / in basso di n elementi per chiave, ottieni l'ultima voce, recupera / attraversa l'intera mappa ordinata per chiave ecc. La complessità è di O (log (n)), quindi metti le prestazioni non sono eccezionali come ConcurrentHashMap. Non è un'implementazione di ConcurrentNavigableMap con SkipList.

Per riassumere usa ConcurrentSkipListMap quando vuoi fare più operazioni sulla mappa che richiedono funzionalità ordinate piuttosto che semplicemente prendere e mettere.