ConcurrentSkipListMap은 언제 사용해야합니까?

ConcurrentSkipListMap은 언제 사용해야합니까?

---

Java에서는 ConcurrentHashMap더 나은 multithreading솔루션이 있습니다. 그럼 언제 사용해야하나요 ConcurrentSkipListMap? 중복입니까?

이 두 가지 사이의 다중 스레딩 측면이 일반적입니까?

---

이 두 클래스는 몇 가지면에서 다릅니다.

ConcurrentHashMap 은 계약의 일부로 작업의 런타임을 보장하지 않습니다. 또한 특정로드 요소 (대략 동시에 수정하는 스레드 수)를 조정할 수 있습니다.

반면 ConcurrentSkipListMap 은 다양한 작업에서 평균 O (log (n)) 성능을 보장합니다. 또한 동시성을위한 튜닝을 지원하지 않습니다. ConcurrentSkipListMap또한 ConcurrentHashMapCeilingEntry / Key, floorEntry / Key 등 을 사용 하지 않는 여러 작업 이 있습니다. 또한 정렬 순서를 유지합니다. 그렇지 않으면 ConcurrentHashMap.

기본적으로 다양한 사용 사례에 대해 다른 구현이 제공됩니다. 빠른 단일 키 / 값 쌍 추가 및 빠른 단일 키 조회가 필요한 경우 HashMap. 더 빠른 순회 순회가 필요하고 삽입에 대한 추가 비용을 감당할 수있는 경우 SkipListMap.

_{* 구현이 O (1) 삽입 / 조회에 대한 일반적인 해시 맵 보장과 대략 일치한다고 생각하지만; 재해 싱 무시}

---

정렬, 탐색 및 동시

데이터 구조의 정의는 건너 뛰기 목록 을 참조하십시오 .

A ConcurrentSkipListMap는 Map키의 자연스러운 순서 (또는 사용자가 정의한 다른 키 순서)로를 저장합니다. 그래서 느린거야 get/ put/ contains(A)보다 작업을 HashMap하지만,이 상쇄 그것은 지원 SortedMap, NavigableMap및 ConcurrentNavigableMap인터페이스를.

---

성능면에서 skipList지도로 사용하는 경우-10 ~ 20 배 느려진 것으로 보입니다. 다음은 내 테스트 결과입니다 (Java 1.8.0_102-b14, win 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);
            }
        }
    }
}

---

워크로드를 기반으로 ConcurrentSkipListMap은 범위 쿼리가 필요한 경우 KAFKA-8802 에서와 같이 동기화 된 메서드를 사용하는 TreeMap보다 느릴 수 있습니다 .

---

ConcurrentHashMap : 다중 스레드 인덱스 기반 get / put을 원할 때 인덱스 기반 작업 만 지원됩니다. Get / Put은 O (1)입니다.

ConcurrentSkipListMap : 키별로 상위 / 하위 n 개 항목 정렬, 마지막 항목 가져 오기, 키별로 정렬 된 전체 맵 가져 오기 / 횡단 등과 같이 가져 오기 / 넣기보다 더 많은 작업을 수행합니다. 복잡성은 O (log (n))이므로 넣기 성능은 그렇지 않습니다. ConcurrentHashMap만큼 훌륭합니다. SkipList를 사용한 ConcurrentNavigableMap의 구현이 아닙니다.

요약하면 단순한 get 및 put이 아닌 정렬 된 기능이 필요한 맵에서 더 많은 작업을 수행하려는 경우 ConcurrentSkipListMap을 사용합니다.

---

그렇다면 언제 ConcurrentSkipListMap을 사용해야합니까?

(a) 키를 정렬 상태로 유지해야하거나 (b) 탐색 가능한 맵의 첫 번째 / 마지막, 헤드 / 테일 및 서브맵 기능이 필요한 경우.

ConcurrentHashMap클래스는 구현 ConcurrentMap으로 수행, 인터페이스를 ConcurrentSkipListMap. 그러나 당신은 또한의 행동하려는 경우 SortedMap와 NavigableMap사용을ConcurrentSkipListMap

ConcurrentHashMap

• ❌ 정렬 됨
• ❌ 탐색 가능
• ✅ 동시

ConcurrentSkipListMap

• ✅ 정렬 됨
• ✅ 탐색 가능
• ✅ 동시

다음은 MapJava 11과 함께 번들로 제공되는 다양한 구현 의 주요 기능을 안내하는 표 입니다.

Google GuavaMap 와 같은 다른 소스에서 다른 구현 및 유사한 데이터 구조를 얻을 수 있습니다 .

참고 URL : https://stackoverflow.com/questions/1811782/when-should-i-use-concurrentskiplistmap