[Java] ConcurrentSkipListMap

ConcurrentSkipListMap, java.util.concurrent.ConcurrentSkipListMap, skip list map, 동시성 정렬 맵

정의

java.util.concurrent.ConcurrentSkipListMap<K,V> 는 Skip List 기반의 thread-safe 정렬 Map. TreeMap 의 동시성 버전.

ConcurrentHashMap 과의 결정적 차이: 정렬 순서를 유지 + NavigableMap 인터페이스 구현 (floor, ceiling, subMap 등).

Skip List 는 평균 O(log n) 의 균형 트리 대체 자료구조. 락 없이 동시 수정이 가능한 알고리즘이 잘 알려져 있어 동시성 구현에 적합.

시각화

Skip List 의 구조

Level 3: head ─────────────────────► 25 ─────────► null
Level 2: head ────────► 10 ────────► 25 ──► 40 ──► null
Level 1: head ─► 5 ──► 10 ──► 17 ──► 25 ──► 40 ──► null
Level 0: head ─► 5 ──► 10 ──► 17 ──► 25 ──► 33 ── 40 ─► null
                                            ↑
                                    실제 데이터 lane

• 각 노드가 확률적으로 여러 레벨에 포함
• 상위 레벨은 “스킵 인덱스” 처럼 작용해 O(log n) 검색
• 새 노드 삽입 시 동전 던지듯 레벨 결정 (1/2 확률로 한 레벨씩 위로)

복잡도

작업	평균	최악
get, put, remove	O(log n)	O(n) (매우 드뭄, 동전이 다 같은 면)
firstKey, lastKey	O(1)	O(1)
containsKey	O(log n)
순회	O(n)
size()	O(n)	약함

사용 예

시간순 정렬된 동시성 맵

ConcurrentNavigableMap<Instant, Event> log = new ConcurrentSkipListMap<>();

// Producer thread
log.put(Instant.now(), event);

// Consumer thread
NavigableMap<Instant, Event> recent = log.tailMap(Instant.now().minusSeconds(60));
recent.forEach((t, e) -> process(e));

Range 쿼리 + 동시성

ConcurrentNavigableMap<Integer, String> levels = new ConcurrentSkipListMap<>();
levels.put(0, "free");
levels.put(100, "basic");
levels.put(1000, "premium");

// 어느 등급에 해당하는지
String tier = levels.floorEntry(user.points()).getValue();

ConcurrentHashMap vs ConcurrentSkipListMap

항목	ConcurrentHashMap	ConcurrentSkipListMap
get/put 시간	O(1) 평균	O(log n)
순서	없음	정렬
Range 쿼리	✗	✓ (subMap 등)
floor / ceiling	✗	✓
동시성 메커니즘	CAS + 버킷 sync	lock-free skip list

순서가 중요하지 않으면 ConcurrentHashMap, 정렬/범위 쿼리가 필요하면 ConcurrentSkipListMap.

참고

• Object
• Iterable
• Collection
• Map
• TreeMap
• ConcurrentHashMap
• ConcurrentSkipListSet
• Non-Blocking
• William Pugh, “Skip Lists: A Probabilistic Alternative to Balanced Trees” (CACM 1990)