Concurrent Skip List Set은 언제 도움이 됩니까?

Concurrent Skip List Set은 언제 도움이 됩니까?

방금 Java 6 API에서 이 데이터 구조를 봤는데 언제 유용한 리소스가 될지 궁금합니다.나는 scjp 시험을 위해 공부하고 있는데, Kathy Sierra의 책에 나와 있는 모의고사 문제를 봤지만, 그것이 다루어지지 않았다.

ConcurrentSkipListSet 및 ConcurrentSkipListMap은 여러 스레드에서 액세스할 정렬된 컨테이너가 필요한 경우에 유용합니다.이들은 기본적으로 동시 코드용 TreeMap 및 TreeSet과 동등합니다.

JDK 6의 실장은 IBM의 Maged Michael이 작성한 고성능 다이내믹 록프리 해시 테이블 및 목록 기반 세트를 기반으로 합니다.이것에 의해, 비교 및 스왑(CAS) 조작을 사용해 스킵 리스트의 많은 조작을 아토믹하게 실장할 수 있는 것을 알 수 있습니다.이것들은 잠금장치가 되어 있지 않기 때문에, 당신은 그 오버헤드에 대해 걱정할 필요가 없습니다.synchronized(대부분의 조작에 대해서) 이러한 클래스를 사용하는 경우.

현재 Java에는 Red-Black 트리 기반의 Map/Set 동시 구현이 없습니다.문헌을 조금 훑어보니 동시 RB 트리가 건너뛰기 목록을 능가하는 성능을 보인 몇 개의 논문을 발견했지만, 이러한 테스트의 대부분은 트랜잭션 메모리에서 수행되었으며, 현재 주요 아키텍처에서는 하드웨어에서 지원되지 않습니다.

JDK가 스킵 리스트를 사용한 것은 실장이 유명하고 잠금 프리화가 간단하고 (CAS를 사용하여) 휴대성이 높기 때문이라고 생각합니다.해명하고 싶은 사람 있으면 말씀하세요.궁금해요.

스킵 리스트는 정렬된 리스트로 로그(n) 퍼포먼스로 효율적으로 변경할 수 있습니다.그런 면에서 보면 TreeSet과 비슷해요.하지만 Concurrent Tree Set은 없습니다.스킵 리스트는 매우 구현하기 쉽다고 들었기 때문에 아마 그 이유일 것입니다.

어쨌든, 동시, 정렬 및 효율적인 세트가 필요한 경우 ConcurrentSkipListSet을 사용할 수 있습니다.

여러 스레드에서 동시에 안전하게 액세스할 수 있는 세트가 필요할 때 유용합니다.또한 일관성이 약하여 적절한 성능을 제공합니다. 세트를 통해 반복하는 동안 삽입을 안전하게 수행할 수 있지만 반복자가 삽입을 볼 수 있다는 보장은 없습니다.

ConcurrentSkipListMap은 자가 성장 캐시에 대한 복제 계층을 구현해야 할 때 훌륭한 발견이었습니다.Map 측면에서는 캐시를 구현하고 기본 List 측면에서는 캐시에 개체가 나타나는 순서를 추적할 수 있습니다.이 목록의 "건너뛰기" 측면은 목록의 한 지점에서 개체를 제거하고 캐시에서 교체될 때 개체를 끝까지 범핑할 수 있도록 했습니다.

언급URL : https://stackoverflow.com/questions/1904439/when-is-a-concurrentskiplistset-useful