Concurrent Skip List Map은 언제 사용해야 합니까?

Concurrent Skip List Map은 언제 사용해야 합니까?

로는 ConcurrentHashMap 나은 것을 하는가?multithreading 언제로 하면 좋을까요?ConcurrentSkipListMap★★★★★★★★★★★★?

이 두 가지 사이의 멀티스레딩 측면은 공통적인가요?

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

ConcurrentHashMap은 계약의 일부로 작업 실행 시간을 보장*하지 않습니다.또한 특정 로드 팩터(대략적으로 동시에 수정하는 스레드 수)를 조정할 수 있습니다.

한편 ConcurrentSkipListMap은 다양한 동작에서 평균 O(log(n) 성능을 보장합니다.또한 동시성을 위해 튜닝을 지원하지 않습니다. ConcurrentSkipListMap 에는 는, 서, 수, 수, 수, 수, 수, 수, 수, 수, also, also, also, also, also, also, also also,ConcurrentHashMapCeiling Entry/Key, floor Entry/Key」는 유지합니다.그 의 경우는, 「Ceiling Entry/Key」를 사용하고 있는 (주요한 .ConcurrentHashMap.

기본적으로 사용 사례에 따라 다른 구현이 제공됩니다. 키의 빠른 및 "/" 를 하십시오.HashMap 빠른 할 수 를 SkipListMap.

_{* O(1) 삽입/룩업의 일반적인 해시 맵 보증과 거의 일치할 것으로 예상되지만 재해시를 무시합니다.}

정렬, 탐색 및 동시 실행

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

A은(는) 키의 자연스러운 순서(또는 사용자가 정의한 다른 키 순서)로 저장합니다.그래서 더 느려질 거야get/put/contains를 초과하는 동작이지만 이를 오프셋하기 위해 , 및 인터페이스를 지원합니다.

그럼 ConcurrentSkipListMap은 언제 사용해야 하나요?

(a) 키를 정렬할 필요가 있는 경우 및 (b) 네비게이션 가능한 맵의 첫 번째/마지막, 헤드/테일 및 서브맵 기능이 필요한 경우.

클래스는 인터페이스를 구현합니다.다만, 및 의 동작도 필요한 경우는, 을 사용해 주세요.

ConcurrentHashMap

• ❌ 정렬됨
• ❌ 네비게이션 가능
• ✅ 동시

ConcurrentSkipListMap

• ✅ 정렬됨
• ✅ 네비게이션 가능
• ✅ 동시

Java 11에 번들된 다양한 구현의 주요 기능에 대해 설명합니다.클릭하여 확대/축소합니다.

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

퍼포먼스 면에서는skipList가 Map으로 사용되는 경우 - 10~20배 느린 것으로 나타납니다.테스트 결과입니다(Java 1.8.0_102-b14, win x 32).

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

또, 1대 1의 비교가 정말로 의미가 있는 사용 사례도 있습니다.이 두 컬렉션을 모두 사용하여 최근에 사용한 항목의 캐시 구현.이제 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);
            }
        }
    }
}

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

ConcurrentHashMap : 멀티스레드 인덱스 기반의 get/put이 필요한 경우 인덱스 기반의 조작만 지원됩니다.Get/Put은 O(1)입니다.

Concurrent Skip List Map : 키별로 정렬된 상위/하위n개 항목, 마지막 항목 가져오기, 키별로 정렬된 전체 맵 가져오기/이동 등 단순한 가져오기/퍼트 이상의 작업을 수행합니다.복잡도는 O(log(n))이기 때문에 Concurrent Hash Map만큼 높은 성능은 아닙니다.Skip List를 사용한 Concurrent Navigable Map의 구현이 아닙니다.

요약하면 단순한 get and put이 아니라 정렬된 기능이 필요한 맵에서 더 많은 작업을 수행할 경우 Concurrent Skip List Map을 사용합니다.

언급URL : https://stackoverflow.com/questions/1811782/when-should-i-use-concurrentskiplistmap