データ構造ステップ編-ジャンプテーブル

配列やチェーンテーブルの検索操作の時間的複雑さはO(N)であり,データ量が大きい場合には非常に時間がかかることはよく知られている.配列については,まず並べ替え,次いで二分探索を用いることで,時間複雑度をO(logn)に低減できるが,秩序配列の挿入はO(N)レベルの動作である.チェーンテーブルの挿入は比較的優れていますが、二分検索を使用して高速クエリーを検索することはできません.チェーンテーブルのように迅速にデータを挿入し、二分検索のようなクエリーアルゴリズムをサポートするデータ構造はありますか?答えは肯定的だ.William Pugh教授が1990年に発表した論文「Skip Lists:A Probabilistic Alternative to Balanced Trees」で提案したジャンプテーブルは、このような興味深いデータ構造である.
ジャンプテーブルの構造
ホップテーブルの核心思想は、インデックス層を構築することによってチェーンテーブルの検索経路を短縮し、迅速な検索の目的を達成することである.チェーンテーブルの各ノードから1つの確立1次インデックスを抽出し、2つの1次インデックスから1つの確立2次インデックスを抽出すると、緑のノードがインデックスを表す下図のような構造が得られます.
William Pughの論文では,上の図に示すように,各カラムインデックスは同じkeyを有し,1つの配列を用いて表される配列とチェーンテーブルの組合せを用いてホップテーブルを実現した.純粋なチェーンテーブルの形式でジャンプテーブルを実現することもでき、下図に示すようにジャンプテーブルの原理を理解するのに役立つと思います.
ジャンプテーブルの検索
ホップテーブルの検索は、上位レベルのインデックスから下位レベルの検索を開始する必要があります.各レベルの検索方法は通常のチェーンテーブルと同じで、後続ノードのキーワードが検索キーワードより大きい場合、このレベルの検索を終了し、次のレベルに入って検索を継続します.次の図は、赤い部分が検索のパスであるジャンプテーブル検索キーワード22のプロセスを示している.上図から直感的に分かるように,ホップテーブルの探索は二分探索と同様であり,その時間的複雑さもO(logn)であることを簡単に証明してみよう.
ホップテーブルにN個のデータノード(キーワード)があり、m個の下位インデックス(またはデータノード)ごとに1個を上位インデックスとして抽出すると仮定すると、
一級索引の数
二次索引の数
三次索引の数
このように、レベルiのインデックスの数
最上位インデックスの数
インデックスの最大レベル
レイヤーごとの検索回数
だからジャンプテーブルの検索回数
mは定数であるため,ホップテーブルの探索時間の複雑さはO(logn)である.
ホップテーブルの多層インデックス構造は、その検索方法を非常に柔軟かつ強力にします.例えば、keyが存在しない場合は、このkeyに隣接するnearKeyが何なのかを知る必要があります.これはホップテーブルで簡単に実現できます.

keyよりも小さく、最もkeyに近いキーワードlowerKeyを検索します.上図のように、後続ノードがkey以上である場合、現在のノードに直接戻ると

になります.

keyよりも大きく、最もkeyに近いキーワードhigherKeyを検索します.上図のように、後続ノードがkeyより大きい場合、直接後続ノードに戻ると

になります.
ジャンプテーブルはまた、キーワード区間[fromKey, toKey]を簡単に検索することができる.これはB+ツリーと似ている.まずfromKeyを検索し、チェーンテーブルを後ろに遍歴し、toKey以下のデータをすべて取り出すだけでよい.
ジャンプテーブルの挿入
これまで、本明細書で説明したのは理想的な状態のホップテーブルであり、実際には、複雑で非効率なため、ホップテーブルのm個の低レベルインデックスごとに高度なインデックスを確立することは厳密ではない.だからWilliam Pughは彼の論文の中でランダムアルゴリズムを採用して新しいノードごとにランダムにインデックスを確立して、以下は私がJavaで実現したバージョンです.

int randomLevel(int m, int maxLevel) {
    ThreadLocalRandom r = ThreadLocalRandom.current();
    int level = 1;
    while (r.nextInt(m) == 0 && level <  maxLevel)
        level++;
    return level;
}

このランダムアルゴリズムにより、i番目のインデックスを生成する確率は、従って、各レイヤのインデックスの数が、前述したインデックスレイヤの性質に合致することを保証することができる.Doug Leaの大物はJavaのConcurrentSkipListMapでもう一つのよりクールなランダムアルゴリズムの実現方式を用い,ランダム数の末尾が連続して1の桁数をインデックスの等級として用い,明らかにこの方式でi級インデックスを生成する確率は,コードが以下に示す.

int rn = ThreadLocalRandom.current().nextInt();
//            0 ，     ，    4 node      
if ((rn & 0x80000001) == 0) {
    int level = 1;
    //          rn     1   
    while (((rn >>>= 1) & 1) != 0)
        level++;
}

ランダム関数でランダムなインデックス・レベルを生成した後、新しいインデックス・カラムを作成し、各レイヤの新しいインデックスを前駆インデックスの後ろにリンクします.ランダム・レベルが現在のホップ・テーブルの最大インデックス・レベルより大きい場合は、新しいインデックスを追加する必要があります.下の図に示すように、赤い破線の矢印は、再構築されたリンクを示しています.
ジャンプテーブルの削除
ホップテーブルの削除操作は比較的簡単で、削除したキーワードを先に照会し、インデックスレイヤでキーワードに一致した場合、すべてのインデックスとデータノードを下に削除し、インデックスに一致していない場合は、データノードを削除するだけでよい.インデックスを削除した後に検出する必要がある点に注意してください.現在のレイヤのHEADインデックスの後続インデックスがNILであれば、このレイヤにインデックスがないことを示し、このインデックスレイヤを削除する必要があります.下の図に示すように、赤い矢印は再構築されたリンクを示します.
ホップテーブルの実装
ジャンプテーブルの実現はAVLツリー、赤黒ツリーなどのバランス二叉木に比べてずっと簡単で、William Pughの論文「Skip Lists:A Probabilistic Alternative to Balanced Trees」では配列とチェーンテーブルを使ってジャンプテーブルを実現する偽コードを提供しており、Javaバージョンの純チェーンテーブルで実現されたジャンプテーブルを書き、私のGitHubにアップロードしました.興味のある方はご覧ください.開発でホップテーブルを使用する必要がある場合は、java.util.concurrent.ConcurrentSkipListMapは強力な実装であり、スレッドが安全です.
転載先:https://juejin.im/post/5cdc38236fb9a0322d04ac7b