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?
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
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.
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);
}
}
}
}
Basierend auf Workloads kann ConcurrentSkipListMap langsamer sein als TreeMap mit synchronisierten Methoden wie in KAFKA-8802 , wenn Bereichsabfragen erforderlich sind.
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.