Wann sollte ich ConcurrentSkipListMap verwenden?

79

In Java ConcurrentHashMapgibt es für eine bessere multithreadingLösung. Wann sollte ich dann verwenden ConcurrentSkipListMap? Ist es eine Redundanz?

Sind Multithreading-Aspekte zwischen diesen beiden häufig?

DKSRathore
quelle

Antworten:

79

Diese beiden Klassen unterscheiden sich in einigen Punkten.

ConcurrentHashMap garantiert nicht * die Laufzeit seines Betriebs als Teil seines Vertrags. Es ermöglicht auch das Optimieren für bestimmte Lastfaktoren (ungefähr die Anzahl der Threads, die es gleichzeitig ändern).

ConcurrentSkipListMap hingegen garantiert eine durchschnittliche O (log (n)) - Leistung bei einer Vielzahl von Vorgängen. Es wird auch keine Optimierung für die Parallelität unterstützt. ConcurrentSkipListMapEs gibt auch eine Reihe von Vorgängen, die ConcurrentHashMapdies nicht tun: Deckeingabe / Schlüssel, Etageingabe / Schlüssel usw. Es wird auch eine Sortierreihenfolge verwaltet, die andernfalls (mit erheblichem Aufwand) berechnet werden müsste, wenn Sie eine verwenden würden ConcurrentHashMap.

Grundsätzlich werden unterschiedliche Implementierungen für unterschiedliche Anwendungsfälle bereitgestellt. Wenn Sie eine schnelle Addition von Einzelschlüssel / Wert-Paaren und eine schnelle Suche nach Einzelschlüssel benötigen, verwenden Sie die HashMap. Wenn Sie eine schnellere Durchquerung in der Reihenfolge benötigen und sich die zusätzlichen Kosten für das Einfügen leisten können, verwenden Sie die SkipListMap.

* Obwohl ich davon ausgehe, dass die Implementierung in etwa den allgemeinen Hash-Map-Garantien für das Einfügen / Nachschlagen von O (1) entspricht; erneutes Hashing ignorieren

Kevin Montrose
quelle
OK. Log (n) ist in Ordnung, aber ist ConcurrentSkipListMap platzsparend?
DKSRathore
1
Überspringlisten sind notwendigerweise größer als Hashtables, aber die einstellbare Natur von ConcurrentHashMap ermöglicht es, eine Hashtable zu erstellen, die größer als die entsprechende ConcurrentSkipListMap ist. Im Allgemeinen würde ich erwarten, dass die Überspringliste größer ist, aber in der gleichen Größenordnung.
Kevin Montrose
"Es wird auch keine Optimierung für die Parallelität unterstützt" .. Warum? Was ist die Verbindung?
Pacerier
2
@Pacerier - Ich habe nicht gemeint, dass es das Tuning unterstützt, weil es gleichzeitig ist. Ich meine, es erlaubt Ihnen nicht, Parameter zu optimieren, die die gleichzeitige Leistung beeinflussen (während ConcurrentHashMap dies tut).
Kevin Montrose
@ KevinMontrose Ic, Sie meinten also "Es unterstützt auch keine Parallelitätsoptimierung."
Pacerier
17

Sortiert, navigierbar und gleichzeitig

Siehe überspringen Liste für eine Definition der Datenstruktur.

A ConcurrentSkipListMapspeichert die Mapin der natürlichen Reihenfolge seiner Schlüssel (oder einer anderen von Ihnen definierten Schlüsselreihenfolge). So wird es haben langsamer get/ put/ containsOperationen als eine HashMap, aber dies zu kompensieren unterstützt es die SortedMap, NavigableMapund ConcurrentNavigableMapSchnittstellen.

Jim Ferrans
quelle
7

In Bezug auf die Leistung, skipList wenn als Karte verwendet - 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 - ein Anwendungsfall, bei dem ein Vergleich untereinander wirklich Sinn macht. Implementierung des Caches der zuletzt verwendeten Elemente unter Verwendung dieser beiden Sammlungen. Jetzt scheint die Effizienz von skipList 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);
            }
        }
    }
}
Xtra Coder
quelle
1
Ich denke, ConcurrentSkipListMap sollte mit ihrem nicht gleichzeitigen Gegenstück, der TreeMap, verglichen werden.
Abbas
1
Wie abbas kommentierte, erscheint es albern, die Leistung mit ConcurrentHashMap zu vergleichen. Der Zweck von ConcurrentSkipListMap besteht darin, (a) Parallelität bereitzustellen und (b) die Sortierreihenfolge zwischen den Schlüsseln beizubehalten. ConcurrentHashMap macht a, aber nicht b. Der Vergleich der Geschwindigkeit von 0 bis 60 eines Tesla und eines Muldenkippers ist sinnlos, da sie unterschiedlichen Zwecken dienen.
Basil Bourque
Obwohl Sie keine Leistungsmetriken kennen, wissen Sie nicht, welche Tesla und welche "Muldenkipper" ist :) Außerdem ... kennen Sie den Preis von "b" ohne Metriken nicht. Daher ist es im Allgemeinen nützlich, die Leistung zu vergleichen.
Xtra Coder
Vielleicht einen Vergleich zur Baumkarte hinzufügen! : D
Simgineer
3

Wann sollte ich dann ConcurrentSkipListMap verwenden?

Wenn Sie (a) die Schlüssel sortiert halten müssen und / oder (b) die ersten / letzten, Kopf / Schwanz- und Submap-Funktionen einer navigierbaren Karte benötigen.

Die ConcurrentHashMapKlasse implementiert die ConcurrentMapSchnittstelle ebenso wie sie ConcurrentSkipListMap. Aber wenn Sie auch das Verhalten von SortedMapund wollen NavigableMap, verwenden SieConcurrentSkipListMap

ConcurrentHashMap

  • ❌ Sortiert
  • ❌ Navigierbar
  • ✅ Gleichzeitig

ConcurrentSkipListMap

  • ✅ Sortiert
  • ✅ Navigierbar
  • ✅ Gleichzeitig

Die folgende Tabelle führt Sie durch die Hauptfunktionen der verschiedenen Mapmit Java 11 gebündelten Implementierungen. Klicken / tippen Sie zum Zoomen.

Tabelle der Kartenimplementierungen in Java 11 zum Vergleich ihrer Funktionen

Beachten Sie, dass Sie andere MapImplementierungen und ähnliche Datenstrukturen aus anderen Quellen wie Google Guava beziehen können .

Basil Bourque
quelle
1

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

Anurag Sharma
quelle
Danke für das Teilen. Ich denke gerade daran, TreeMap in einem meiner Projekte durch ConcurrentSkipListMap zu ersetzen, also ist es gut, das zu wissen! Haben Sie mehr Kontext darüber, warum ConcurrentSkipListMap langsamer ist, und mehr Details zum Leistungsvergleich?
Yusong
0

ConcurrentHashMap: Wenn Sie ein indexbasiertes Get / Put mit mehreren Threads wünschen, werden nur indexbasierte Operationen unterstützt. Get / Put sind von O (1)

ConcurrentSkipListMap: Mehr Operationen als nur get / put, wie sortierte obere / untere n Elemente nach Schlüssel, letzten Eintrag abrufen, ganze Karte nach Schlüssel sortiert abrufen / durchlaufen, die Komplexität ist von O (log (n)), also ist die Put-Leistung nicht so großartig wie ConcurrentHashMap. Es ist keine Implementierung von ConcurrentNavigableMap mit SkipList.

Zusammenfassend lässt sich sagen, dass Sie ConcurrentSkipListMap verwenden, wenn Sie mehr Operationen auf der Karte ausführen möchten, für die sortierte Funktionen erforderlich sind, anstatt nur einfach abzurufen und zu platzieren.

Gamaschen
quelle