· 개발

스킵 리스트: 동전 던지기로 정한 레벨이 O(log n) 검색을 만드는 방식

정렬된 연결 리스트에 무작위 레벨의 포인터를 더하면 검색이 왜 기대 O(log n)이 될까요? Pugh의 보고서에 실린 알고리즘, '기대' 시간의 범위, Java ConcurrentSkipListMap 문서가 약속하는 것을 정리했습니다.

개발알고리즘자료구조

3, 6, 7, 9, 12, 17, 19, 21, 25, 26이 정렬된 연결 리스트에서 19를 찾으려면 앞에서부터 3, 6, 7, 9, 12, 17을 차례로 지나야 합니다. 배열이라면 이진 탐색으로 가운데를 바로 짚겠지만, 연결 리스트는 다음 노드로 가는 포인터밖에 없습니다.

스킵 리스트는 일부 노드에 멀리 건너뛰는 포인터를 더 달아 이 문제를 풉니다. 어느 노드에 몇 개를 달지는 동전 던지기로 정합니다. 아래 내용은 William Pugh의 기술 보고서 「A Skip List Cookbook」(1989년 7월, 1990년 6월 개정)과 Java SE 25 API 문서를 기준으로 합니다.

노드마다 레벨이 있다

스킵 리스트의 노드에는 레벨이 있고, 레벨은 그 노드가 가진 전방 포인터의 개수입니다. 노드의 i번째 포인터는 레벨이 i 이상인 다음 노드를 가리킵니다. 리스트 끝에는 어떤 키보다 큰 키를 가진 NIL이 있어 모든 레벨이 거기서 끝납니다.

처음 예의 키에 레벨을 붙이면 이런 모양이 됩니다. 레벨은 설명을 위해 직접 정한 값입니다.

level 4  H  -------> 6  -------------------------------------------------> NIL
level 3  H  -------> 6  -------------------------------------> 25 -------> NIL
level 2  H  -------> 6  -------> 9  -------> 17 -------------> 25 -------> NIL
level 1  H  -> 3  -> 6  -> 7  -> 9  -> 12 -> 17 -> 19 -> 21 -> 25 -> 26 -> NIL

H는 헤더입니다. 헤더는 최대 레벨(MaxLevel)만큼 포인터를 가지고, 아직 쓰지 않는 높은 레벨의 포인터는 NIL을 가리킵니다.

검색: 오른쪽으로 가다가 막히면 한 칸 아래로

검색은 리스트의 현재 최대 레벨에서 시작합니다. 다음 노드의 키가 찾는 키보다 작으면 오른쪽으로 가고, 그렇지 않으면 한 레벨 내려갑니다. 레벨 1에서도 더 갈 수 없으면 찾는 키가 있다면 바로 다음 노드에 있습니다.

x := 헤더
for i := 최대 레벨 downto 1
    while x의 i번째 다음 노드의 키 < 찾는 키
        x := x의 i번째 다음 노드
x := x의 1번째 다음 노드
x의 키 = 찾는 키이면 x의 값을 반환, 아니면 실패

위 그림에서 19를 찾으면 이렇게 움직입니다.

  1. 레벨 4: 헤더 다음 6은 19보다 작으니 6으로 갑니다. 6 다음은 NIL이라 내려갑니다.
  2. 레벨 3: 6 다음 25는 19보다 크니 내려갑니다.
  3. 레벨 2: 9, 17로 갑니다. 17 다음 25는 크니 내려갑니다.
  4. 레벨 1: 17 다음 19는 19보다 작지 않으니 멈추고, 한 칸 나아가 19를 확인합니다.

거쳐 간 노드는 6, 9, 17이고, 레벨 1만 따라갔다면 3부터 17까지 여섯 노드를 지났을 것입니다. 노드 10개짜리 예라서 차이가 작지만, 높은 레벨의 노드가 듬성듬성 있어 위에서 큰 폭으로 건너뛰는 구조입니다.

삽입과 삭제: 찾은 뒤 이어 붙이기

삽입과 삭제도 같은 검색을 합니다. 다른 점은 각 레벨에서 내려가기 직전에 서 있던 노드를 update[i]에 적어 두는 것입니다. 검색이 끝나면 update[i]는 넣거나 뺄 위치의 왼쪽에서 레벨 i 이상인 가장 오른쪽 노드입니다.

새 노드의 레벨은 아래 함수로 정합니다.

randomLevel()
    lvl := 1
    while random() < p and lvl < MaxLevel
        lvl := lvl + 1
    return lvl

p = 1/2이면 노드의 50%는 레벨 1, 25%는 레벨 2, 12.5%는 레벨 3이 됩니다. 레벨은 리스트에 원소가 몇 개 있는지와 상관없이 정해집니다. 그다음 레벨 1부터 새 레벨까지 update[i]의 포인터를 새 노드로 돌리고, 새 노드의 포인터가 원래 다음 노드를 가리키게 하면 끝입니다. 삭제는 반대로 이어 붙이고, 가장 높은 레벨이 비면 리스트의 레벨을 낮춥니다. 어느 쪽이든 바꾸는 포인터는 그 노드 앞뒤뿐이라, 논문 표현대로 국소적인 수정으로 끝납니다.

MaxLevel은 원소 수의 상한 N에 맞춰 log_{1/p} N으로 잡으라고 Pugh는 권합니다. p = 1/2이면 원소 2³²개까지는 MaxLevel = 32로 충분하다고 적었습니다.

‘기대’ O(log n)이 뜻하는 것

쿡북은 검색, 삽입, 삭제의 기대 비용을 O(log n)이라고 적습니다. 최악의 경우를 막는 장치는 없습니다. 레벨이 나쁘게 나오면, 예를 들어 모든 노드가 레벨 1이면 검색은 그냥 연결 리스트를 따라가는 것과 같습니다. 논문은 이런 배치는 드물다고 분석합니다.

여기에는 전제가 하나 붙습니다. 사용자가 노드의 레벨을 볼 수 없어야 합니다. 레벨을 아는 사용자라면 레벨 1이 아닌 원소를 전부 지워 최악의 실행 시간을 일부러 만들 수 있다고 논문이 직접 예로 듭니다. 또 같은 자료구조에서 연산마다 운이 새로 정해지는 것도 아닙니다. 같은 원소를 두 번 검색하면 두 번 모두 정확히 같은 시간이 걸립니다. 어떤 키가 한 번 느리게 나왔다면, 그 리스트가 바뀌기 전까지는 계속 느립니다.

쿡북은 비교 횟수의 확률적 상한을 구하고, 그 기댓값을 L(n)/p + 1/(1−p) + 1로 계산합니다. 여기서 L(n) = log_{1/p} n입니다. 논문의 표 2에 정리된 값은 다음과 같습니다.

p 검색 비용의 평균 원소당 평균 포인터 수
1/2 2 lg n + 3 2
1/4 2 lg n + 7/3 1⅓

p = 1/2에 n = 2²⁰(1,048,576)을 넣으면 2 × 20 + 3 = 43입니다. 실측값이 아니라 상한의 기댓값을 계산한 숫자입니다. p를 1/4로 낮추면 이 기댓값은 거의 그대로이면서 원소당 포인터가 2개에서 1⅓개로 줄어듭니다. 같은 표에서 p = 1/4의 분산은 6 lg n − 68/9 − 16/n으로, p = 1/2의 2 lg n − 4/n보다 큽니다. 공간을 아끼는 대신 검색 시간이 더 고르지 않게 됩니다.

키 말고 위치로도 다룰 수 있다

쿡북의 제목이 말하듯 이 보고서의 주제는 기본 연산 다음의 응용입니다. 몇 가지만 옮기면 이렇습니다.

  • 검색 핑거: 마지막으로 본 위치의 update 벡터를 다음 연산까지 유지하면, 거리 k만큼 떨어진 원소를 찾는 데 기대 O(log k) 시간이 걸립니다. 다만 검색에 지역성이 없으면 이 관리 비용 때문에 전체가 느려질 수 있다고 적었습니다.
  • 분할과 연결: 한 키를 기준으로 두 리스트로 나누거나, 앞 리스트의 마지막 키가 뒤 리스트의 첫 키 이하일 때 둘을 잇는 연산이 기대 O(log n)입니다.
  • 위치로 찾기: 포인터마다 건너뛰는 원소 수(fDistance)를 함께 저장하면 “k번째 원소”를 같은 방식으로 찾고, k번째 뒤에 넣거나 k번째를 지울 수 있습니다.
  • 중복 키: 삽입이 항상 새 노드를 넣도록 바꾸면 중복을 허용합니다. 이때 검색은 가장 최근에 넣은 것을 찾고, 삭제도 가장 최근 것부터 지웁니다.

Java의 ConcurrentSkipListMap이 약속하는 것

Java 표준 라이브러리에는 스킵 리스트로 만든 정렬 맵과 정렬 집합이 있습니다. Java SE 25 문서 기준으로 정리합니다.

ConcurrentSkipListMap은 스킵 리스트의 동시성 변형을 구현하며, containsKey, get, put, remove와 그 변형에 기대 평균 log(n) 시간을 제공한다고 적혀 있습니다. 여러 스레드가 삽입, 삭제, 갱신, 조회를 동시에 해도 안전합니다. 키는 자연 순서나 생성 때 받은 Comparator로 정렬됩니다. 문서에 적힌 주의점은 이렇습니다.

  • 이터레이터와 스플리터레이터는 약한 일관성(weakly consistent)만 보장합니다.
  • 오름차순 뷰와 그 이터레이터가 내림차순보다 빠릅니다.
  • putAll, equals, toArray, containsValue, clear 같은 일괄 연산은 원자적이라는 보장이 없습니다. putAll과 동시에 도는 이터레이터는 추가된 원소 중 일부만 볼 수 있습니다.
  • containsValue는 맵 크기에 비례하는 시간이 걸리고, 실행 중에 맵이 바뀌면 결과가 부정확할 수 있습니다.
  • null 키와 값은 넣을 수 없습니다. null 반환을 원소가 없다는 뜻과 구별할 수 없기 때문입니다.

ConcurrentSkipListMap을 바탕으로 만든 ConcurrentSkipListSet의 문서는 size가 대부분의 컬렉션과 달리 상수 시간 연산이 아니라고 경고합니다. 현재 원소 수를 알려면 원소를 순회해야 하고, 순회 중에 집합이 바뀌면 부정확한 값을 돌려줄 수 있습니다. 반복문 조건에 size()를 넣는 습관이 있다면 이 컬렉션에서는 다시 볼 만합니다.

자료구조 자체의 성질과 이 API가 약속하는 범위는 따로 봐야 합니다. Pugh의 쿡북에 실린 알고리즘에는 동시 접근 처리가 들어 있지 않고, 동시 유지보수 방법은 별도 보고서(「Concurrent Maintenance of Skip Lists」)에서 다룬다고 적혀 있습니다. Java 문서가 약속하는 것은 위의 시간 비용과 동시성 동작이고, 내부 구현 방식은 이 글에서 다루지 않았습니다.

참고한 보고서와 문서

문서는 2026년 10월 14일에 확인했습니다.

블로그로