· 開発

スキップリスト：コイン投げで決めたレベルが 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段下りる

探索はリストの現在の最大レベルから始めます。次のノードのキーが探すキーより小さければ右へ進み、そうでなければ1レベル下ります。レベル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 より小さくないので止まり、1つ進んで 19 を確かめます。

通ったノードは 6, 9, 17 です。レベル1だけをたどれば、3 から 17 まで6つのノードを通っていました。ノード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] のポインタを新ノードに向け、新ノードのポインタを元の次のノードに向ければ挿入は終わりです。削除は逆につなぎ替え、最上位のレベルが空になればリストのレベルを下げます。どちらでも書き換えるのはそのノードの前後のポインタだけで、報告書の言葉で言えば局所的な変更で済みます。

Pugh は、要素数の上限を N として MaxLevel を log_{1/p} N にするよう勧めています。p = 1/2 なら、要素 2³² 個までは MaxLevel = 32 が適切だと書いています。

「期待」O(log n) が意味すること

Cookbook は、探索・挿入・削除の期待コストを O(log n) としています。最悪のケースを防ぐ仕組みはありません。レベルの出方が悪く、たとえばすべてのノードがレベル1なら、探索はただの連結リストをたどるのと同じです。報告書の分析では、そうした配置はまれです。

これには前提があります。利用者が要素のレベルを見られないことです。レベルを知る利用者なら、レベル1以外の要素をすべて削除して最悪の実行時間を意図的に作れる、と報告書自身が例に挙げています。また、同じデータ構造では操作ごとに運が引き直されるわけではありません。同じ要素を続けて2回探すと、2回ともまったく同じ時間がかかります。あるキーの探索が一度遅かったなら、リストが変わるまでずっと遅いままです。

Cookbook は比較回数の確率的な上界を求め、その期待値を 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) 時間で見つけられます。ただし探索に参照の局所性がなければ、そのオーバーヘッドで全体が遅くなりうると書かれています。
  • 分割と連結：あるキーを境に2つのリストに分ける操作と、前のリストの最後のキーが後ろのリストの最初のキー以下のときに2つをつなぐ操作は、期待 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 の Cookbook のアルゴリズムは並行アクセスを扱っておらず、並行保守の方法は別の報告書（「Concurrent Maintenance of Skip Lists」）で扱うと書かれています。Java のドキュメントが約束しているのは上の時間コストと並行時の動作で、内部の実装方法はこの記事では扱っていません。

参照した報告書とドキュメント

ドキュメントは2026年10月14日に確認しました。

ブログへ