Wann sollte ich ConcurrentSkipListMap verwenden?

Question

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

Sind Multithreading-Aspekte zwischen diesen beiden häufig?

Answer 1

Diese beiden Klassen unterscheiden sich in einigen Punkten.

ConcurrentHashMap garantiert nicht * die Laufzeit seiner Operationen als Teil seines Vertrags. Es ermöglicht auch das Abstimmen für bestimmte Ladefaktoren (ungefähr die Anzahl von Threads, die es gleichzeitig modifizieren).

ConcurrentSkipListMap, garantiert andererseits eine durchschnittliche O (log (n)) - Leistung bei einer Vielzahl von Operationen. Es unterstützt auch nicht die Abstimmung aus Gründen der Gleichzeitigkeit. ConcurrentSkipListMap hat auch eine Reihe von Operationen, die ConcurrentHashMap nicht: ceilingEntry/Key, floorEntry/Key, etc. Es unterhält auch eine Sortierreihenfolge, die andernfalls (mit erheblichen Kosten) berechnet werden müsste, wenn Sie eine ConcurrentHashMap verwenden würden.

Grundsätzlich werden verschiedene Implementierungen für verschiedene Anwendungsfälle bereitgestellt. Verwenden Sie HashMap, wenn Sie eine schnelle Einzelschlüssel/Wert-Paar-Addition und schnelle Einzelschlüssel-Suche benötigen. Wenn Sie eine schnellere Traversierung 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 erwarte die Implementierung ist in etwa im Einklang mit den allgemeinen Hash-Karte garantiert von O (1) Insertion/Lookup; Ignorieren Re-Hashing}

Answer 2

Eine Definition der Datenstruktur finden Sie unter Skip List. Eine ConcurrentSkipListMap speichert die Map in der natürlichen Reihenfolge ihrer Schlüssel (oder einer anderen Schlüsselreihenfolge, die Sie definieren). Es wird also langsamere get/put/contains Operationen als eine HashMap haben, aber um dies auszugleichen, unterstützt es die Schnittstellen SortedMap und NavigableMap.

Answer 3

In Bezug auf die Leistung, skipList wenn als Map verwendet wird - scheint, 10-20 Mal langsamer sein. Hier ist das Ergebnis meiner Tests (Java 1.8.0_102-b14 gewinnen 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 zu, dass - verwendungs ​​Fall, in dem Vergleich eine Eins-zu-ein anderer wirklich Sinn macht. Implementierung des Caches der zuletzt verwendeten Elemente unter Verwendung dieser beiden Sammlungen. Die Effizienz von skipList scheint nun zweifelhafter zu sein. Hier

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

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); 
      } 
     } 
    } 
}