詳解Java中跳躍表的原理和實現

2022-12-27 14:00:54

一、跳躍表的引入

對有序順序表可以採用二分查詢，查詢的時間複雜度為O (logn)，插入、刪除的時間複雜度為 O(n )。但是對有序連結串列不可以採用二分查詢，查詢、插入和刪除的時間複雜度均為O (n)。

有序連結串列如下圖所示，若查詢 8，則必須從第 1 個節點開始，依次比較 8 次才能查詢成功。

如何利用連結串列的有序性來提高查詢效率？如何在一個有序連結串列中進行二分查詢？若增加一級索引，把奇數位序作為索引，則如下圖所示，若查詢 8，則可以先從索引進行比較，依次比較 1、3、5、7、9，8 比 7 大但比 9 小，7 向下一層，繼續向後比較，比較 6 次即可查詢成功。

若再增加一級索引，把索引層的奇數位序作為索引，則如下圖所示，若查詢 7，則可以先從索引開始比較，依次 1、5、9，7 比 5 大但比 9 小，5 向下一層，繼續向後比較，比較 4 次即可查詢成功。

在增加兩級索引後，若查詢 5，則比較兩次即可查詢成功；若查詢比 5 大的數，則以 5 為界向後查詢；若查詢比 5 小的數，則以 5 為界向前查詢。這就是一個可進行二分查詢的有序連結串列。

二、演演算法分析

若有 n 個元素，則增加 h 級索引後的資料結構如下圖所示。

1.時間複雜度

底層包含所有元素（n個），即 2^(h +1)=n ，索引層數 h=logn-1。搜尋時，首先在頂層索引中進行查詢，然後二分搜尋，最多從頂層搜尋到底層，最多 O(logn) 層，因此查詢的時間複雜度為 O(logn)。

2.空間複雜度

增加索引需要一些輔助空間，那麼索引一共有多少個節點呢？從上圖中可以看出，每層索引的節點之和都為 2+2^2 +…+2^h =2^(h +1)-2=n-2，因此空間複雜度為 O(n )。實際上，索引節點並不是原節點的複製，只是附加了一些指標建立索引。以上正是跳躍表的實現原理。

三、跳躍表介紹

跳躍表（Skip list）是有序連結串列的擴充套件，簡稱跳錶，它在原有的有序連結串列上增加了多級索引，通過索引來實現快速查詢，實質上是一種可以進行二分查詢的有序連結串列。

實際上，跳躍表並不是簡單地通過奇偶次序建立索引的，而是通過隨機技術實現的，因此也可以說它是一種隨機化的資料結構。假如跳躍表每一層的晉升概率都是 1/2，則最理想的索引就是在原始連結串列中每隔一個元素抽取一個元素作為一級索引。其實在原始連結串列中隨機選擇 n/2 個元素作為一級索引也可以，因為隨機選擇的元素相對均勻，對查詢效率來講影響不大。當原始連結串列中元素數量足夠大且抽取足夠隨機時，得到的索引是均勻的。因此隨機選擇 n/2 個元素作為一級索引，隨機選擇 n/4 個元素作為二級索引，隨機選擇 n/8 個元素作為三級索引，以此類推，一直到頂層索引。我們可以通過索引來提升跳躍表的查詢效率。

跳躍表不僅可以提高搜尋效能，還可以提高插入和刪除操作的效能。平衡二叉查詢樹在進行插入、刪除操作後需要多次調整平衡，而跳躍表完全依靠隨機技術，其效能和平衡二叉查詢樹不相上下，但是原理非常簡單。跳躍表是一種效能比較優秀的動態資料結構，Redis 中的有序集合 Sorted Set 和 LevelDB 中的 MemTable 都是採用跳躍表實現的。

四、跳躍表的實現

1.資料結構定義

在每個節點都可以設定向右、向下指標，當然，也可以附加向左、向上指標，構建四聯表。通過四聯表可以快速地在四個方向存取前驅和後繼。在此僅設定向右指標，在每個節點都定義一個後繼指標陣列，通過層次控制向下存取。

2.查詢

在跳躍表中查詢元素 x ，需要從最上層索引開始逐層查詢，演演算法步驟如下。

（1）從最上層 Sh 的頭節點開始。

（2）假設當前位置為 p ，p 的後繼節點的值為 y ，若 x=y，則查詢成功；若 x>y ，則 p 向後移一個位置，繼續查詢；若 x<y ，則 p 向下移動一個位置，繼續查詢。

（3）若到達底層還要向下移動，則查詢失敗。

例如，跳躍表如下圖所示，在表中查詢元素 36，則先從頂層的頭節點開始，比 20 大，向後為空，p 向下移動到第 2 層；比下一個元素 50 小，p 向下移動到第 1 層；比下一個元素 30 大，p 向右移動；比下一個元素 50 小，p 向下移動到第 0 層；與下一個元素 36 比較，查詢成功。

3.插入

在跳躍表中插入一個元素時，相當於在某一個位置插入一個高度為 level 的列。插入的位置可以通過查詢確定，而插入列的高度可以採用隨機化決策確定。

隨機化獲取插入元素的層次：

① 初始時 lay=0，可設定晉升概率P為 0.5 或 0.25。

② 利用隨機函數產生 0～1的亂數 r。

④ 若 r 小於 P 且 lay 小於最大層次，則 lay+1；否則返回 lay，作為新插入元素的高度。

在跳躍表中插入元素的演演算法步驟如下。

（1）查詢插入位置，在查詢過程中用 updata[i] 記錄經過的每一層的最大節點位置。

（2）採用隨機化策略得到插入層次 lay。

（3）建立新節點，將高度為 lay 的列插入 updata[i] 之後。

例如，跳躍表如下圖所示，在表中插入元素 32。首先在跳躍表中查詢 32，然後確定插入位置。在查詢過程中用 updata[i] 記錄經過的每一層的最大節點位置；假設隨機化得到的層次為 2，則 i 為 0～2，將新節點插入 updata[i] 之後。

4.刪除

在跳躍表中刪除一個元素，相當於刪除這個元素所在的列。

演演算法步驟：

（1）查詢該元素，在查詢過程中用 updata[i] 記錄經過的每一層的最大節點位置，實際上是待刪除節點在每一層的前一個元素的位置。若查詢失敗，則退出。

（2）利用 updata[i] 將該元素整列刪除。

（3）若有多餘空鏈，則刪除空鏈。

例如，跳躍表如下圖所示，在表中刪除元素 20。首先在跳躍表中查詢 20，在查詢過程中用 updata[i] 記錄經過的每一層的最大節點位置；然後利用 updata[i] 將每層的 20 節點刪除。

刪除 20 所在的列後，最上層的鏈為空鏈，則刪除空鏈，跳躍表的層次減 1。

五、實戰

1.程式碼

package com.platform;
 
import java.util.Scanner;
 
public class SkipList {
    private static int INF = 0x7fffffff;
    private static float P = 0.5f;
    private static int MAX_LEVEL = 16;
 
    static class Node {
        int val;
        Node forward[] = new Node[MAX_LEVEL];
    }
 
 
    Node head = new Node();
    Node updata[] = new Node[MAX_LEVEL];
 
    public SkipList() {
        for (int i = 0; i < updata.length; i++) {
            updata[i] = new Node();
        }
    }
 
    void Init() {
        level = 0;
        head = new Node();
        for (int i = 0; i < MAX_LEVEL; i++)
            head.forward[i] = null;
        head.val = -INF;
    }
 
    // 隨機產生插入元素高度
    static int RandomLevel() {
        int lay = 0;
        while ((float) Math.random() < P && lay < MAX_LEVEL - 1)
            lay++;
        return lay;
    }
 
    Node Find(int val) {//查詢最接近val的元素
        Node p = head;
        for (int i = level; i >= 0; i--) {
            while (p.forward[i] != null && p.forward[i].val < val)
                p = p.forward[i];
            updata[i] = p;//記錄搜尋過程中各級走過的最大節點位置
        }
        return p;
    }
 
    void Insert(int val) {
        Node p, s;
        int lay = RandomLevel();
        System.out.printf("lay=%dn", lay);
        if (lay > level) //要插入的層 > 現有層數
            level = lay;
        p = Find(val); //查詢
        s = new Node();//建立一個新節點
        s.val = val;
        for (int i = 0; i < MAX_LEVEL; i++)
            s.forward[i] = null;
        for (int i = 0; i <= lay; i++) {//插入操作
            s.forward[i] = updata[i].forward[i];
            updata[i].forward[i] = s;
        }
    }
 
    void Delete(int val) {
        Node p = Find(val);
        if (p.forward[0] != null && p.forward[0].val == val) {
            System.out.printf("%dn", p.forward[0].val);
            for (int i = level; i >= 0; i--) { // 刪除操作
                if (updata[i].forward[i] != null && updata[i].forward[i].val == val)
                    updata[i].forward[i] = updata[i].forward[i].forward[i];
            }
            while (level > 0 && head.forward[level] == null) // 刪除空鏈
                level--;
        }
    }
 
    void print(int i) { // 遍歷
        Node p = head.forward[i];
        if (p == null) return;
        while (p != null) {
            System.out.printf("%d  ", p.val);
            p = p.forward[i];
        }
        System.out.printf("n");
    }
 
    void printall() { // 遍歷所有層
        for (int i = level; i >= 0; i--) {
            System.out.printf("level %d:  ", i);
            print(i);
        }
    }
 
    void show() {
        System.out.printf("Please select:n");
        System.out.printf("-----------------------------n");
        System.out.printf("     1:  插入n");
        System.out.printf("     2:  刪除n");
        System.out.printf("     3:  查詢n");
        System.out.printf("     4:  遍歷n");
        System.out.printf("     5:  遍歷所有層n");
        System.out.printf("     0:  退出n");
        System.out.printf("-----------------------------n");
    }
 
    int level;
 
    public static void main(String[] args) {
        Scanner sn = new Scanner(System.in);
        SkipList skipList = new SkipList();
        skipList.Init();
        int n, x;
        skipList.show();
        while (true){
            n = sn.nextInt();
            switch (n) {
                case 1:
                    x = sn.nextInt();
                    skipList.Insert(x);
                    break;
                case 2:
                    x = sn.nextInt();
                    skipList.Delete(x);
                    break;
                case 3:
                    x = sn.nextInt();
                    Node p;
                    p = skipList.Find(x);
                    if (p.forward[0] != null && p.forward[0].val == x) {
                        System.out.printf("find success!n");
                    } else {
                        System.out.printf("find fail!n");
                    }
 
 
                    break;
                case 4:
                    skipList.print(0);
                    break;
                case 5:
                    skipList.printall();
                    break;
            }
            skipList.show();
        }
    }
}

2.測試結果

Please select:
-----------------------------
1: 插入
2: 刪除
3: 查詢
4: 遍歷
5: 遍歷所有層
0: 退出
-----------------------------
1
1
lay=0
Please select:
-----------------------------
1: 插入
2: 刪除
3: 查詢
4: 遍歷
5: 遍歷所有層
0: 退出
-----------------------------
5
level 0: 1
Please select:
-----------------------------
1: 插入
2: 刪除
3: 查詢
4: 遍歷
5: 遍歷所有層
0: 退出
-----------------------------
1
4
lay=5
Please select:
-----------------------------
1: 插入
2: 刪除
3: 查詢
4: 遍歷
5: 遍歷所有層
0: 退出
-----------------------------
5
level 5: 4
level 4: 4
level 3: 4
level 2: 4
level 1: 4
level 0: 1 4
Please select:
-----------------------------
1: 插入
2: 刪除
3: 查詢
4: 遍歷
5: 遍歷所有層
0: 退出
-----------------------------
1
7
lay=1
Please select:
-----------------------------
1: 插入
2: 刪除
3: 查詢
4: 遍歷
5: 遍歷所有層
0: 退出
-----------------------------
5
level 5: 4
level 4: 4
level 3: 4
level 2: 4
level 1: 4 7
level 0: 1 4 7
Please select:
----------------------------
1: 插入
2: 刪除
3: 查詢
4: 遍歷
5: 遍歷所有層
0: 退出
-----------------------------
1
2
lay=0
Please select:
-----------------------------
1: 插入
2: 刪除
3: 查詢
4: 遍歷
5: 遍歷所有層
0: 退出
-----------------------------
5
level 5: 4
level 4: 4
level 3: 4
level 2: 4
level 1: 4 7
level 0: 1 2 4 7
Please select:
-----------------------------
1: 插入
2: 刪除
3: 查詢
4: 遍歷
5: 遍歷所有層
0: 退出
-----------------------------
3
3
find fail!
Please select:
-----------------------------
1: 插入
2: 刪除
3: 查詢
4: 遍歷
5: 遍歷所有層
0: 退出
-----------------------------
3
2
find success!
Please select:
-----------------------------
1: 插入
2: 刪除
3: 查詢
4: 遍歷
5: 遍歷所有層
0: 退出
-----------------------------
2
2
2
Please select:
-----------------------------
1: 插入
2: 刪除
3: 查詢
4: 遍歷
5: 遍歷所有層
0: 退出
-----------------------------
5
level 5: 4
level 4: 4
level 3: 4
level 2: 4
level 1: 4 7
level 0: 1 4 7
Please select:
-----------------------------
1: 插入
2: 刪除
3: 查詢
4: 遍歷
5: 遍歷所有層
0: 退出
-----------------------------