Wann soll ich ConcurrentSkipListMap verwenden?

Question

In Java ist ConcurrentHashMap es für eine bessere multithreading Lösung. Dann wann sollte ich verwenden ConcurrentSkipListMap? Ist es eine Redundanz?

Ist Multithreading Aspekte zwischen diesen beiden sind gemeinsam?

Answer 1

Diese beiden Klassen unterscheiden sich in ein paar Möglichkeiten.

ConcurrentHashMap tut garantiert nicht * die Laufzeit ihrer Tätigkeit im Rahmen ihres Auftrags. Es ermöglicht auch Tuning für bestimmte Belastungsfaktoren (etwa die Anzahl der Threads es gleichzeitig zu ändern).

ConcurrentSkipListMap , auf dem Andererseits seits~~POS=HEADCOMP gewährleistet durchschnittliche O (log (n)) Leistung auf einer Vielzahl von Operationen. Es unterstützt auch keine Abstimmung für Concurrency willen. ConcurrentSkipListMap hat auch eine Reihe von Operationen, die ConcurrentHashMap nicht:. ceilingEntry / Key, floorEntry / Key, etc. Es unterhält auch eine Sortierreihenfolge, die sonst berechnet werden muß (bei bemerkenswertem Aufwand), wenn Sie eine ConcurrentHashMap wurden mit

Grundsätzlich verschiedene Implementierungen für verschiedene Anwendungsfälle zur Verfügung gestellt. Wenn Sie schnell einzelne Schlüssel / Wert-Paar Addition und schnell einzelne Schlüsselsuche benötigen, verwenden Sie die HashMap. Wenn Sie schneller in Ordnung Traversal benötigen, und können die zusätzlichen Kosten für das Einsetzen leisten, verwenden Sie die SkipListMap.

_{* Obwohl ich erwarte, dass die Umsetzung in etwa im Einklang mit den allgemeinen Hash-Karte Garantien von O (1) Einfügen / Nachschlag; Ignorieren Re-Hashing}

Answer 2

Siehe überspringen Liste für eine Definition der Datenstruktur. Ein ConcurrentSkipListMap speichert die Karte in der natürlichen Ordnung des Schlüssels (oder eine andere Taste, um Sie definieren). So wird es haben langsamer get / put / enthält Operationen als eine HashMap, aber zu dieser Offset es unterstützt die SortedMap und NavigableMap Schnittstellen.

Answer 3

In Bezug auf Leistung, skipList, wenn sie als Karte verwendet wird - erscheint 10-20 mal langsamer. 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 dieser - Use-Case, wo man zu einem anderen wirklich Sinn macht zu vergleichen. Implementierung des Cache der letzten zuletzt verwendeten Elemente dieser beiden Sammlungen verwenden. Jetzt Effizienz von skiplist sieht Ereignis mehr fragwürdig.

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

Answer 4

ConcurrentHashMap: wenn u multithreaded Index basierend get / put wollen, nur indexbasierte Operationen werden unterstützt. Get / Put sind von O (1)

ConcurrentSkipListMap: Mehr Operationen als nur erhalten / put, wie sortierte oben / unten n Artikel von Schlüssel, letzten Eintrag bekommen, Abruf- / Traverse ganze Karte nach Schlüssel usw. Komplexität sortiert von O (log (n)), also setzen Leistung ist nicht so groß wie ConcurrentHashMap. It't eine Implementierung von ConcurrentNavigableMap mit skiplist.

Verwendung ConcurrentSkipListMap Zusammengefasst, wenn Sie möchten mehr Operationen auf der Karte tun erfordert sortierte Funktionen und nicht nur einfach erhalten und setzen.