मुझे ConcurrentSkipListMap का उपयोग कब करना चाहिए?

Question

जावा में, ConcurrentHashMap बेहतर multithreading समाधान के लिए है। तो मुझे ConcurrentSkipListMap का उपयोग कब करना चाहिए? क्या यह एक अनावश्यकता है?

क्या इन दोनों के बीच बहुसंख्यक पहलू आम हैं?

Answer 1

ये दो वर्ग कुछ तरीकों से भिन्न होते हैं।

ConcurrentHashMap इसकी अनुबंध के हिस्से के रूप में * इसके संचालन के रनटाइम की गारंटी नहीं देता है। यह कुछ लोड कारकों के लिए ट्यूनिंग की अनुमति देता है (लगभग, धागे की संख्या समवर्ती रूप से इसे संशोधित करने)।

ConcurrentSkipListMap, दूसरी ओर, विभिन्न प्रकार के संचालनों पर औसत ओ (लॉग (एन)) प्रदर्शन की गारंटी देता है। यह समवर्तीता के लिए ट्यूनिंग का भी समर्थन नहीं करता है। ConcurrentSkipListMap में कई ऑपरेशन भी हैं जो ConcurrentHashMap नहीं है: ceilingEntry/key, floorEntry/key, आदि। यह एक सॉर्ट ऑर्डर भी बनाए रखता है, जो अन्यथा गणना की जाती है (उल्लेखनीय व्यय) यदि आप ConcurrentHashMap का उपयोग कर रहे थे।

असल में, विभिन्न उपयोग मामलों के लिए विभिन्न कार्यान्वयन प्रदान किए जाते हैं। यदि आपको त्वरित एकल कुंजी/मूल्य जोड़ी जोड़ और त्वरित एकल कुंजी लुकअप की आवश्यकता है, तो HashMap का उपयोग करें। यदि आपको तेजी से इन-ऑर्डर ट्रैवर्सल की आवश्यकता है, और सम्मिलन के लिए अतिरिक्त लागत का भुगतान कर सकते हैं, तो SkipListMap का उपयोग करें।

_{* हालांकि मुझे उम्मीद है कि कार्यान्वयन ओ (1) सम्मिलन/लुकअप की सामान्य हैश-मैप गारंटी के अनुरूप है; री-हैशिंग}

Answer 2

डेटा संरचना की परिभाषा के लिए Skip List देखें। एक ConcurrentSkipListMap मानचित्र को अपनी चाबियों के प्राकृतिक क्रम में संग्रहीत करता है (या आपके द्वारा परिभाषित कुछ अन्य महत्वपूर्ण क्रम)। तो इसमें हैश मैप की तुलना में धीमे/रखे/संचालन शामिल होंगे, लेकिन इसे ऑफसेट करने के लिए यह सॉर्टेड मैप और नेविगैबल मैप इंटरफेस का समर्थन करता है।

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