Soru ConcurrentSkipListMap'i ne zaman kullanmalıyım?


Java’da ConcurrentHashMap daha iyi için var multithreading çözüm. O zaman ne zaman kullanmalıyım? ConcurrentSkipListMap? Bu bir fazlalık mı?

Bu ikisi arasındaki çok iş parçacıklı yönleri yaygın mıdır?


62
2017-11-28 06:33


Menşei




Cevaplar:


Bu iki sınıf birkaç şekilde değişir.

ConcurrentHashMap sözleşmesinin bir parçası olarak faaliyetlerinin çalışma süresini garanti etmez. Aynı zamanda belirli yük faktörlerinin ayarlanmasını sağlar (kabaca aynı anda değiştiren iplik sayısı).

ConcurrentSkipListMapÖte yandan, çok çeşitli operasyonlarda ortalama O (log (n)) performansını garanti eder. Aynı zamanda eşzamanlılık uğruna ayarlamayı desteklemez. ConcurrentSkipListMap ayrıca bir dizi operasyona sahiptir ConcurrentHashMap yapmaz: ceilingEntry / Key, floorEntry / Key, vb. Ayrıca, bir tür kullanıyorsanız, aksi takdirde hesaplanması gereken bir sıralama düzenini (dikkate değer gider) korur ConcurrentHashMap.

Temel olarak, farklı kullanım durumları için farklı uygulamalar sağlanmıştır. Hızlı tek anahtar / değer çifti ekleme ve hızlı tek tuşla aramaya ihtiyacınız varsa, HashMap. Siparişte daha hızlı geçişe ihtiyacınız varsa ve ekleme için ek maliyeti kaldırabiliyorsanız, SkipListMap.

* Uygulamanın kabaca O (1) yerleştirme / aramanın genel karma harita garantileriyle uyumlu olmasını beklemesine rağmen; yeniden hasreti görmezden gelmek


59
2017-11-28 06:50



Tamam. Log (n) iyi ama ConcurrentSkipListMap alanı verimli mi? - DKSRathore
Atla listeleri zorunlu olarak Hashtables'den daha büyüktür, ancak ConcurrentHashMap'in ayarlanabilir yapısı eşdeğer ConcurrentSkipListMap'den daha büyük bir Hashtable oluşturulmasını mümkün kılar. Genel olarak, atlama listesinin daha büyük ama aynı büyüklükte olmasını beklerdim. - Kevin Montrose♦
"Aynı zamanda eşzamanlılığın uğruna ayarlamayı da desteklemiyor" .. Neden? Link nedir? - Pacerier
@Pacerier - Eşzamanlı olduğu için tuning'i desteklemediğini kastetmedim, yani eşzamanlı performansa (ConcurrentHashMap'in yaptığı gibi) etki eden parametreleri ayarlamanıza izin vermez. - Kevin Montrose♦
@KevinMontrose Ic, yani "eşzamanlılık ayarını da desteklemiyor" demek istediniz. - Pacerier


Görmek Liste atla Veri yapısının tanımı için. Bir ConcurrentSkipListMap Haritasını anahtarlarının doğal düzeninde (veya tanımladığınız başka bir tuş sırasını) saklar. Böylece bir HashMap'ten daha yavaş get / put / içerme işlemleri olacaktır, ancak bunu dengelemek için SortedMap ve NavigableMap arayüzlerini desteklemektedir.


12
2017-11-28 06:48





Performans açısından, skipList Harita olarak kullanıldığında - 10-20 kat daha yavaş görünür. İşte testlerimin sonucu (Java 1.8.0_102-b14, x32 kazan)

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

Ve buna ek olarak - bire-bir diğerini karşılaştırmanın gerçekten mantıklı olduğu bir durum. Bu koleksiyonların her ikisini de kullanarak son kullanılan ürünlerin önbelleğinin uygulanması. Artık skipList'in etkinliği, olayın daha şüpheli görünüyor.

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

İşte JMH için kod (çalıştırıldığı gibi 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);
            }
        }
    }
}

6
2017-09-15 08:53