摘要：跳躍表的空間復(fù)雜度為。不過(guò)，二叉查找樹(shù)是有可能出現(xiàn)一種極端的情況的，就是如果插入的數(shù)據(jù)剛好一直有序，那么所有節(jié)點(diǎn)會(huì)偏向某一邊。例如這種接結(jié)構(gòu)會(huì)導(dǎo)致二叉查找樹(shù)的查找效率變?yōu)檫@會(huì)使二叉查找樹(shù)大打折扣。

假如我們要用某種數(shù)據(jù)結(jié)構(gòu)來(lái)維護(hù)一組有序的int型數(shù)據(jù)的集合，并且希望這個(gè)數(shù)據(jù)結(jié)構(gòu)在插入、刪除、查找等操作上能夠盡可能著快速，那么，你會(huì)用什么樣的數(shù)據(jù)結(jié)構(gòu)呢？

數(shù)組

一種很簡(jiǎn)單的方法應(yīng)該就是采用數(shù)組了，在查找方面，用數(shù)組存儲(chǔ)的話，采用二分法可以在 O(logn) 的時(shí)間里找到指定的元素，不過(guò)數(shù)組在插入、刪除這些操作中比較不友好，找到目標(biāo)位置所需時(shí)間為 O(logn) ，進(jìn)行插入和刪除這個(gè)動(dòng)作所需的時(shí)間復(fù)雜度為 O(n) ，因?yàn)槎夹枰苿?dòng)移動(dòng)元素，所以最終所需要的時(shí)間復(fù)雜度為 O(n) 。 例如對(duì)于下面這個(gè)數(shù)組：

插入元素 3

鏈表

另外一種簡(jiǎn)單的方法應(yīng)該就是用鏈表了，鏈表在插入、刪除的支持上就相對(duì)友好，當(dāng)我們找到目標(biāo)位置之后，插入、刪除元素所需的時(shí)間復(fù)雜度為 O(1) ，注意，我說(shuō)的是找到目標(biāo)位置之后，插入、刪除的時(shí)間復(fù)雜度才為O(1)。

但鏈表在查找上就不友好了，不能像數(shù)組那樣采用二分查找的方式，只能一個(gè)一個(gè)結(jié)點(diǎn)遍歷，所以加上查找所需的時(shí)間，插入、刪除所需的總的時(shí)間復(fù)雜度為O(n)。

假如我們能夠提高鏈表的查找效率，使鏈表的查找的時(shí)間復(fù)雜度盡可能接近 O(logn) ，那鏈表將會(huì)是很棒的選擇。

提高鏈表的查找速度

那鏈表的查找速度可以提高嗎？

對(duì)于下面這個(gè)鏈表

假如我們要查找元素9，按道理我們需要從頭結(jié)點(diǎn)開(kāi)始遍歷，一共遍歷8個(gè)結(jié)點(diǎn)才能找到元素9。能否采取某些策略，讓我們遍歷5次以內(nèi)就找到元素9呢？請(qǐng)大家花一分鐘時(shí)間想一下如何實(shí)現(xiàn)？

由于元素的有序的，我們是可以通過(guò)增加一些路徑來(lái)加快查找速度的。例如

通過(guò)這種方法，我們只需要遍歷5次就可以找到元素9了（紅色的線為查找路徑）。

還能繼續(xù)加快查找速度嗎？

答是可以的，再增加一層就行了，這樣只需要4次就能找到了，這就如同我們搭地鐵的時(shí)候，去某個(gè)站點(diǎn)時(shí)，有快線和慢線幾種路線，通過(guò)快線 + 慢線的搭配，我們可以更快著到達(dá)某個(gè)站點(diǎn)。

當(dāng)然，還能在增加一層，

基于這種方法，對(duì)于具有 n 個(gè)元素的鏈表，我們可以采取 ** (logn + 1) 層指針路徑的形式**，就可以實(shí)現(xiàn)在 O(logn) 的時(shí)間復(fù)雜度內(nèi)，查找到某個(gè)目標(biāo)元素了，這種數(shù)據(jù)結(jié)構(gòu)，我們也稱(chēng)之為跳躍表，跳躍表也可以算是鏈表的一種變形，只是它具有二分查找的功能。

插入與刪除

上面例子中，9個(gè)結(jié)點(diǎn)，一共4層，可以說(shuō)是理想的跳躍表了，不過(guò)隨著我們對(duì)跳躍表進(jìn)行插入/刪除結(jié)點(diǎn)的操作，那么跳躍表結(jié)點(diǎn)數(shù)就會(huì)改變，意味著跳躍表的層數(shù)也會(huì)動(dòng)態(tài)改變。

這里我們面臨一個(gè)問(wèn)題，就是新插入的結(jié)點(diǎn)應(yīng)該跨越多少層？

這個(gè)問(wèn)題已經(jīng)有大牛替我們解決好了，采取的策略是通過(guò)拋硬幣來(lái)決定新插入結(jié)點(diǎn)跨越的層數(shù)：每次我們要插入一個(gè)結(jié)點(diǎn)的時(shí)候，就來(lái)拋硬幣，如果拋出來(lái)的是正面，則繼續(xù)拋，直到出現(xiàn)負(fù)面為止，統(tǒng)計(jì)這個(gè)過(guò)程中出現(xiàn)正面的次數(shù)，這個(gè)次數(shù)作為結(jié)點(diǎn)跨越的層數(shù)。

通過(guò)這種方法，可以盡可能著接近理想的層數(shù)。大家可以想一下為啥會(huì)這樣呢？

插入

例如，我們要插入結(jié)點(diǎn) 3，4，通過(guò)拋硬幣知道3，4跨越的層數(shù)分別為 0，2 (層數(shù)從0開(kāi)始算)，則插入的過(guò)程如下：

插入 3，跨越0層。

插入 4，跨越2層。

刪除

解決了插入之后，我們來(lái)看看刪除，刪除就比較簡(jiǎn)單了，例如我們要?jiǎng)h除4，那我們直接把4及其所跨越的層數(shù)刪除就行了。

小結(jié)

跳躍表的插入與刪除至此都講完了，總結(jié)下跳躍表的有關(guān)性質(zhì)：

(1). 跳躍表的每一層都是一條有序的鏈表.

(2). 跳躍表的查找次數(shù)近似于層數(shù)，時(shí)間復(fù)雜度為O(logn)，插入、刪除也為 O(logn)。

(3). 最底層的鏈表包含所有元素。

(4). 跳躍表是一種隨機(jī)化的數(shù)據(jù)結(jié)構(gòu)(通過(guò)拋硬幣來(lái)決定層數(shù))。

(5). 跳躍表的空間復(fù)雜度為 O(n)。

跳躍表 vs 二叉查找樹(shù)

有人可能會(huì)說(shuō)，也可以采用二叉查找樹(shù)啊，因?yàn)椴檎也檎覙?shù)的插入、刪除、查找也是近似 O(logn) 的時(shí)間復(fù)雜度。

不過(guò)，二叉查找樹(shù)是有可能出現(xiàn)一種極端的情況的，就是如果插入的數(shù)據(jù)剛好一直有序，那么所有節(jié)點(diǎn)會(huì)偏向某一邊。例如

這種接結(jié)構(gòu)會(huì)導(dǎo)致二叉查找樹(shù)的查找效率變?yōu)?O(n),這會(huì)使二叉查找樹(shù)大打折扣。

跳躍表 vs 紅黑樹(shù)

紅黑可以說(shuō)是二叉查找樹(shù)的一種變形，紅黑在查找，插入，刪除也是近似O(logn)的時(shí)間復(fù)雜度，但學(xué)過(guò)紅黑樹(shù)的都知道，紅黑樹(shù)比跳躍表復(fù)雜多了，反正我是被紅黑樹(shù)虐過(guò)。在選擇一種數(shù)據(jù)結(jié)構(gòu)時(shí)，有時(shí)候也是需要考慮學(xué)習(xí)成本的。

而且紅黑樹(shù)插入，刪除結(jié)點(diǎn)時(shí)，是通過(guò)調(diào)整結(jié)構(gòu)來(lái)保持紅黑樹(shù)的平衡，比起跳躍表直接通過(guò)一個(gè)隨機(jī)數(shù)來(lái)決定跨越幾層，在時(shí)間復(fù)雜度的花銷(xiāo)上是要高于跳躍表的。

當(dāng)然，紅黑樹(shù)并不是一定比跳躍表差，在有些場(chǎng)合紅黑樹(shù)會(huì)是更好的選擇，所以選擇一種數(shù)據(jù)結(jié)構(gòu)，關(guān)鍵還得看場(chǎng)合。

總上所述，維護(hù)一組有序的集合，并且希望在查找、插入、刪除等操作上盡可能快，那么跳躍表會(huì)是不錯(cuò)的選擇。redis 中的數(shù)據(jù)數(shù)據(jù)便是采用了跳躍表，當(dāng)然，ridis也結(jié)合了哈希表等數(shù)據(jù)結(jié)構(gòu)，采用的是一種復(fù)合數(shù)據(jù)結(jié)構(gòu)。

代碼如下

package skiplist;

//節(jié)點(diǎn)
class Node{
    int value = -1;
    int level;//跨越幾層
    Node[] next;//指向下一個(gè)節(jié)點(diǎn)

    public Node(int value, int level) {
        this.value = value;
        this.level = level;
        this.next = new Node[level];
    }
}
//跳躍表
public class SkipList {
    //允許的最大層數(shù)
    int maxLevel = 16;
    //頭節(jié)點(diǎn)，充當(dāng)輔助。
    Node head = new Node(-1, 16);
    //當(dāng)前跳躍表節(jié)點(diǎn)的個(gè)數(shù)
    int size = 0;
    //當(dāng)前跳躍表的層數(shù),初始化為1層。
    int levelCount = 1;


    public Node find(int value) {
        Node temp = head;
        for (int i = levelCount - 1; i >= 0; i--) {
            while (temp.next[i] != null && temp.next[i].value < value) {
                temp = temp.next[i];
            }
        }
        //判斷是否有該元素存在
        if (temp.next[0] != null && temp.next[0].value == value) {
            System.out.println(value + "  查找成功");
            return temp.next[0];
        } else {
            return null;
        }
    }
    // 為了方便，跳躍表在插入的時(shí)候，插入的節(jié)點(diǎn)在當(dāng)前跳躍表是不存在的
    //不允許插入重復(fù)數(shù)值的節(jié)點(diǎn)。
    public void insert(int value) {
        int level = getLevel();
        Node newNode = new Node(value, level);
        //update用于記錄要插入節(jié)點(diǎn)的前驅(qū)
        Node[] update = new Node[level];

        Node temp = head;
        for (int i = level - 1; i >= 0; i--) {
            while (temp.next[i] != null && temp.next[i].value < value) {
                temp = temp.next[i];
            }
            update[i] = temp;
        }
        //把插入節(jié)點(diǎn)的每一層連接起來(lái)
        for (int i = 0; i < level; i++) {
            newNode.next[i] = update[i].next[i];
            update[i].next[i] = newNode;
        }
        //判斷是否需要更新跳躍表的層數(shù)
        if (level > levelCount) {
            levelCount = level;
        }
        size++;
        System.out.println(value + " 插入成功");
    }

    public void delete(int value) {
        Node[] update = new Node[levelCount];
        Node temp = head;

        for (int i = levelCount - 1; i >= 0; i--) {
            while (temp.next[i] != null && temp.next[i].value < value) {
                temp = temp.next[i];
            }
            update[i] = temp;
        }

        if (temp.next[0] != null && temp.next[0].value == value) {
            size--;
            System.out.println(value + " 刪除成功");
            for (int i = levelCount - 1; i >= 0; i--) {
                if (update[i].next[i] != null && update[i].next[i].value == value) {
                    update[i].next[i] = update[i].next[i].next[i];
                }
            }
        }
    }

    //打印所有節(jié)點(diǎn)
    public void printAllNode() {
        Node temp = head;
        while (temp.next[0] != null) {
            System.out.println(temp.next[0].value + "  ");
            temp = temp.next[0];
        }
    }

    //模擬拋硬幣
    private int getLevel() {
        int level = 1;
        while (true) {
            int t = (int)(Math.random() * 100);
            if (t % 2 == 0) {
                level++;
            } else {
                break;
            }
        }
        System.out.println("當(dāng)前的level = " + level);
        return level;
    }

    //測(cè)試數(shù)據(jù)
    public static void main(String[] args) {
        SkipList list = new SkipList();
        for (int i = 0; i < 6; i++) {
            list.insert(i);
        }
        list.printAllNode();
        list.delete(4);
        list.printAllNode();
        System.out.println(list.find(3));
        System.out.println(list.size + " " + list.levelCount);
    }
}

如果你覺(jué)得不錯(cuò)，不妨點(diǎn)個(gè)贊讓更多人看到這篇文章，感激不盡。

最后推廣下我的公眾號(hào)：苦逼的碼農(nóng)，文章都會(huì)首發(fā)于我的公眾號(hào)，公眾號(hào)已有100多篇原創(chuàng)文章，期待各路英雄的關(guān)注交流。