In Java ConcurrentHashMap
gibt es für eine bessere multithreading
Lösung. Wann sollte ich dann verwenden ConcurrentSkipListMap
? Ist es eine Redundanz?
Sind Multithreading-Aspekte zwischen diesen beiden häufig?
quelle
In Java ConcurrentHashMap
gibt es für eine bessere multithreading
Lösung. Wann sollte ich dann verwenden ConcurrentSkipListMap
? Ist es eine Redundanz?
Sind Multithreading-Aspekte zwischen diesen beiden häufig?
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. ConcurrentSkipListMap
Es gibt auch eine Reihe von Vorgängen, die ConcurrentHashMap
dies 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
Sortiert, navigierbar und gleichzeitig
Siehe überspringen Liste für eine Definition der Datenstruktur.
A
ConcurrentSkipListMap
speichert dieMap
in der natürlichen Reihenfolge seiner Schlüssel (oder einer anderen von Ihnen definierten Schlüsselreihenfolge). So wird es haben langsamerget
/put
/contains
Operationen als eineHashMap
, aber dies zu kompensieren unterstützt es dieSortedMap
,NavigableMap
undConcurrentNavigableMap
Schnittstellen.quelle
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); } } } }
quelle
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
ConcurrentHashMap
Klasse implementiert dieConcurrentMap
Schnittstelle ebenso wie sieConcurrentSkipListMap
. Aber wenn Sie auch das Verhalten vonSortedMap
und wollenNavigableMap
, verwenden SieConcurrentSkipListMap
ConcurrentHashMap
ConcurrentSkipListMap
Die folgende Tabelle führt Sie durch die Hauptfunktionen der verschiedenen
Map
mit Java 11 gebündelten Implementierungen. Klicken / tippen Sie zum Zoomen.Beachten Sie, dass Sie andere
Map
Implementierungen und ähnliche Datenstrukturen aus anderen Quellen wie Google Guava beziehen können .quelle
Basierend auf Workloads kann ConcurrentSkipListMap mit synchronisierten Methoden wie in KAFKA-8802 langsamer als TreeMap sein, wenn Bereichsabfragen erforderlich sind.
quelle
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.
quelle