متى يجب استخدام ConcurrentSkipListMap?

Question

في جاوة ، ConcurrentHashMap هل هناك أفضل multithreading الحل.ثم متى يجب استخدام ConcurrentSkipListMap?هل هو التكرار?

هل خاصية تعدد الجوانب بين هذين مشتركة ؟

Answer 1

اثنين من هذه الفئات تختلف في عدد قليل من الطرق.

ConcurrentHashMap لا يضمن* وقت التشغيل من العمليات كجزء من العقد.كما يسمح ضبط بعض عوامل الحمولة (تقريبا عدد من المواضيع بالتزامن تعديله).

ConcurrentSkipListMap, من ناحية أخرى ، وضمانات متوسط O(log(n)) الأداء على مجموعة واسعة من العمليات.كما أنها لا تدعم ضبط التزامن الله. ConcurrentSkipListMap لديها أيضا عدد من العمليات التي ConcurrentHashMap لا:ceilingEntry/مفتاح floorEntry/مفتاح, الخ.كما يحافظ على الترتيب ، التي من شأنها أن خلاف ذلك يجب أن تكون محسوبة (في ملحوظة حساب) إذا كنت تستخدم ConcurrentHashMap.

في الأساس, تطبيقات مختلفة يتم توفير استخدام مختلف الحالات.إذا كنت بحاجة إلى واحدة سريعة على مفتاح/قيمة زوج إضافة واحدة سريعة على مفتاح البحث ، استخدام HashMap.إذا كنت بحاجة أسرع في النظام اجتياز, و يستطيعون تحمل تكلفة اضافية على الإدراج ، استخدام SkipListMap.

_{*على الرغم من أنني أتوقع التنفيذ هو تقريبا في خط مع العامة تجزئة الخريطة ضمانات O(1) الإدراج/بحث;تجاهل إعادة تجزئة}

Answer 2

قائمة تخطي للحصول على تعريف بنية البيانات. A ConcurrentSkipListMap مخازن خريطة في النظام الطبيعي للمفاتيح (أو بعض النظام الرئيسيين الآخرين لك تحديد). لذلك سوف يكون أبطأ الحصول على / وضع / يحتوي على العمليات من HashMap، ولكن لتعويض هذا أنه يدعم واجهات SortedMap وNavigableMap.

Answer 3

وعلى صعيد الأداء، skipList عندما يتم استخدام خريطة - يبدو أن 10-20 مرات أبطأ. هنا هو نتيجة لبلدي التجارب (جافا 1.8.0_102-B14، والفوز بسرعة 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

وبالإضافة إلى ذلك إلى أن - استخدام الحالة التي يكون فيها مقارنة واحدة إلى أخرى يجعل حقا معنى. تنفيذ ذاكرة التخزين المؤقت من المواد المستخدمة آخر في الآونة الأخيرة باستخدام كل من هذه المجموعات. الآن كفاءة skipList يتطلع إلى أن يكون الحدث أكثر مشكوك فيها.

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

وهنا هو رمز للJMH (أعدم كما 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: عندما اردت مؤشرات المؤشر على أساس الحصول على / وضع، يتم دعم عمليات فقط مؤشر القائمة. الحصول على / ضع ذات O (1)

وConcurrentSkipListMap: مزيد من العمليات من مجرد الحصول على / وضع، مثل فرزها أعلى / أسفل ن العناصر بواسطة مفتاح، والحصول على الإدخال الأخير، جلب / اجتياز الخريطة كلها مرتبة حسب رئيسيا الخ التعقيد هي من O (سجل (ن))، لذا وضعت أداء ليست كبيرة كما ConcurrentHashMap. It't لتنفيذ ConcurrentNavigableMap مع SkipList.

لتلخيص استخدام ConcurrentSkipListMap عندما تريد أن تفعل المزيد من العمليات على الخريطة تتطلب ميزات فرزها وليس مجرد الحصول بسيطة وضعت.