wake-up-neo.com

Wann sollte ich ConcurrentSkipListMap verwenden?

In Java ist ConcurrentHashMap für eine bessere multithreading-Lösung vorhanden. Wann sollte ich dann ConcurrentSkipListMap verwenden? Ist es eine Redundanz?

Sind Multithreading-Aspekte zwischen diesen beiden häufig?

javaperformancemultithreadingmapconcurrenthashmap
64
DKSRathore

Diese beiden Klassen unterscheiden sich in einigen Punkten.

ConcurrentHashMap garantiert nicht * die Laufzeit seiner Operationen im Rahmen seines Vertrags. Außerdem können bestimmte Lastfaktoren angepasst werden (etwa die Anzahl der Threads, die gleichzeitig geändert werden).

ConcurrentSkipListMap garantiert andererseits eine durchschnittliche O(log(n)) Leistung bei einer Vielzahl von Operationen. Es unterstützt auch keine Abstimmung für die Parallelität. ConcurrentSkipListMap hat auch eine Reihe von Operationen, die ConcurrentHashMap nicht tut: ceilingEntry/Key, floorEntry/Key usw. Außerdem wird eine Sortierreihenfolge festgelegt, die andernfalls (mit erheblichem Aufwand) berechnet werden müsste, wenn Sie einen ConcurrentHashMap verwenden.

Grundsätzlich sind unterschiedliche Implementierungen für unterschiedliche Anwendungsfälle vorgesehen. Wenn Sie eine schnelle Hinzufügung eines einzelnen Schlüssel/Wert-Paares und eine schnelle Suche nach einem einzelnen Schlüssel benötigen, verwenden Sie HashMap. Wenn Sie einen schnelleren Durchlauf in der Reihenfolge benötigen und sich die zusätzlichen Kosten für das Einfügen leisten können, verwenden Sie SkipListMap.

* Obwohl ich erwarte, dass die Implementierung ungefähr mit den allgemeinen Hash-Karten-Garantien von O(1) Insertion/Lookup übereinstimmt; Ignorieren von erneutem Hashing

61
Kevin Montrose

Siehe Skip List für eine Definition der Datenstruktur. Eine ConcurrentSkipListMap speichert die Map in der natürlichen Reihenfolge ihrer Schlüssel (oder einer anderen von Ihnen definierten Schlüsselreihenfolge). Es hat also langsamere get/put/-Inhalte als eine HashMap, aber um dies auszugleichen, werden die Schnittstellen SortedMap und NavigableMap unterstützt.

14
Jim Ferrans

In Bezug auf die Leistung scheint skipList when als Map verwendet zu werden - scheint 10-20 mal langsamer zu sein. Hier ist das Ergebnis meiner Tests (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

Und zusätzlich dazu - Use-Case, bei dem der Vergleich eines Menschen wirklich sinnvoll ist. Implementierung des Cache der zuletzt verwendeten Elemente mithilfe dieser beiden Sammlungen. Die Effizienz der skipList scheint nun zweifelhafter zu sein.

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

Hier ist der Code für JMH (ausgeführt als 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);
            }
        }
    }
}
6
Xtra Coder

Basierend auf Workloads kann ConcurrentSkipListMap langsamer sein als TreeMap mit synchronisierten Methoden wie in KAFKA-8802 , wenn Bereichsabfragen erforderlich sind.

1
Anurag Sharma

ConcurrentHashMap: Wenn Sie multithreadbasiertes get/put verwenden möchten, werden nur indexbasierte Operationen unterstützt. Get/Put sind von O (1)

ConcurrentSkipListMap: Mehr Operationen als nur get/put, wie oberste/unterste n Elemente nach Schlüssel sortiert, letzte Eingabe abrufen, ganze Karte nach Schlüssel sortieren/durchsuchen usw. Komplexität ist O (log (n)), also Put-Leistung nicht so gut wie ConcurrentHashMap. Es ist keine Implementierung von ConcurrentNavigableMap mit SkipList.

Zusammenfassend können Sie ConcurrentSkipListMap verwenden, wenn Sie mehr Operationen auf der Karte durchführen möchten, für die sortierte Features erforderlich sind, als nur einfaches Abrufen und Einfügen.

0
spats