Khi nào tôi nên sử dụng ConcurrentSkipListMap?

Question

Trong Java, ConcurrentHashMap có giải pháp tốt hơn là multithreading. Khi nào tôi nên sử dụng ConcurrentSkipListMap? Nó là một sự thừa?

Các khía cạnh đa luồng giữa hai tính năng này có phổ biến không?

Answer 1

Hai lớp này thay đổi theo một vài cách.

ConcurrentHashMap không đảm bảo * thời gian chạy của các hoạt động của nó như là một phần của hợp đồng. Nó cũng cho phép điều chỉnh cho một số yếu tố tải (khoảng, số lượng các chủ đề đồng thời sửa đổi nó). Mặt khác,

ConcurrentSkipListMap đảm bảo hiệu suất O (log (n)) trung bình trên nhiều hoạt động khác nhau. Nó cũng không hỗ trợ điều chỉnh vì lợi ích của đồng thời. ConcurrentSkipListMap cũng có một số hoạt động mà ConcurrentHashMap không: trầnEntry/Key, floorEntry/Key, vv Nó cũng duy trì một thứ tự sắp xếp, mà nếu không sẽ phải được tính toán (với chi phí đáng chú ý) nếu bạn đang sử dụng một ConcurrentHashMap.

Về cơ bản, các triển khai khác nhau được cung cấp cho các trường hợp sử dụng khác nhau. Nếu bạn cần thêm một cặp khóa/giá trị nhanh và tìm kiếm khóa đơn nhanh, hãy sử dụng HashMap. Nếu bạn cần truyền tải theo thứ tự nhanh hơn và có thể trả thêm chi phí để chèn, hãy sử dụng SkipListMap.

_{* Mặc dù tôi hy vọng việc triển khai gần như phù hợp với bảo đảm bản đồ băm chung của O (1) chèn/tra cứu; bỏ qua re-hashing}

Answer 2

Xem Skip List để biết định nghĩa cấu trúc dữ liệu. Một ConcurrentSkipListMap lưu trữ Bản đồ theo thứ tự các khóa của nó (hoặc một số thứ tự quan trọng khác mà bạn xác định). Vì vậy, nó sẽ có các hoạt động get/put/contains chậm hơn một HashMap, nhưng để bù đắp nó, nó hỗ trợ các giao diện SortedMap và NavigableMap.

Answer 3

Về hiệu suất, skipList khi được sử dụng làm Bản đồ - có vẻ chậm hơn 10-20 lần. Dưới đây là kết quả của các xét nghiệm của tôi (Java 1.8.0_102-b14, giành chiến thắng 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 

Và thêm vào đó - sử dụng hợp cụ thể mà so sánh một-một thực sự có ý nghĩa. Triển khai bộ nhớ cache của các mục gần đây nhất được sử dụng bằng cả hai bộ sưu tập này. Bây giờ hiệu quả của skipList dường như là sự kiện đáng ngờ hơn.

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

Đây là mã cho JMH (thực hiện như 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); 
      } 
     } 
    } 
}