跳表數(shù)據(jù)結(jié)構(gòu)的發(fā)明者William Pugh在1990年的論文《Skip Lists: A Probabilistic Alternative to Balanced Trees》中首次提出了跳表的概念和設(shè)計。跳表是一種基于鏈表的數(shù)據(jù)結(jié)構(gòu)，通過添加多層索引來加速查找操作，相比于平衡樹等其他數(shù)據(jù)結(jié)構(gòu)，跳表具有簡單、高效的特點；在插入、刪除、查找元素的時間復(fù)雜度跟紅黑樹都是一樣量級的，時間復(fù)雜度都是O(logn)。

1、本質(zhì)：有序鏈表之上添加索引

下圖是一個簡單的有序單鏈表，單鏈表的特性就是每個元素存放下一個元素的指針（或引用）。即：通過第一個元素可以找到第二個元素，通過第二個元素可以找到第三個元素，依次類推，直到找到最后一個元素。

單鏈表.png

如果我們想快速找到上圖鏈表中的 5這個元素，只能從頭開始遍歷鏈表，直到找到我們需要找的元素。查找路徑：0、1、2、3、4、5。這樣的查找效率很低，平均時間復(fù)雜度很高O(n)。那有沒有辦法提高鏈表的查找速度呢？如下圖所示，我們從鏈表中每兩個元素抽出來，加一級索引level1，level0為原始鏈表。

單鏈表_1層索引.png

查找路徑優(yōu)先從level1的head開始，向右直到遇到大于當(dāng)前查找值，也就是到節(jié)點4時發(fā)現(xiàn)下一個節(jié)點值為6，大于當(dāng)前查找值5，于是跳轉(zhuǎn)到level0的節(jié)點4，再繼續(xù)查找下一節(jié)點，找到5后搜索結(jié)束；查找路徑：level1的0（后續(xù)簡寫成1 - 0）、1 - 2、1 - 4、0 - 4、0 - 5；

從一層索引下，平均時間復(fù)雜度降為O(n/2)；但是這僅是一層索引的情況，在多層索引的情況下時間復(fù)雜度如何呢？

• 假設(shè)跳表的元素個數(shù)為n，每個節(jié)點的層級都是隨機分布的，平均來說，每個節(jié)點的上層節(jié)點數(shù)是下層的一半。這樣，最底層level 0有n個節(jié)點的索引，level 1有n/2個索引，level 2有n/4個索引，以此類推。最高級索引 h 滿足 1= n/2^h，即 h = log2n；

• 整個查找過程類似二分查找。我們從最高層開始，如果當(dāng)前節(jié)點的下一個節(jié)點值大于目標(biāo)值，我們就轉(zhuǎn)到當(dāng)前層的下一層繼續(xù)查找；如果當(dāng)前節(jié)點的下一個節(jié)點值小于或等于目標(biāo)值，我們就在當(dāng)前層向右移動。這樣平均每一層我們只需要遍歷1次節(jié)點（向右或向下），所以在每一層的時間復(fù)雜度是O(1)。

• 因為跳表的高度是logn，所以查找操作的總時間復(fù)雜度是O(logn) * O(1) = O(logn)。

2、 實際的數(shù)據(jù)結(jié)構(gòu)

上面講的是跳表從有序單鏈表演化的數(shù)據(jù)結(jié)構(gòu)，但在實際編碼中跳表的結(jié)構(gòu)是這樣的

    class Node<T> {
        String key;
        T value;
        Node<T>[] forwards;

        public Node(int level, T value, String key) {
            this.value = value;
            this.key = key;
            forwards = new Node[level];
        }
    }

跳表數(shù)據(jù)結(jié)構(gòu).png

• 每個節(jié)點node存放data(本例是map，存放key、value)和指針數(shù)組forward
• forward指針數(shù)組指向當(dāng)層level的下一節(jié)點，如node1的forward[2]指向level 2層的下一節(jié)點node2，而forward[3]指向level 3層的下一節(jié)點node3
• 遍歷從head的forward[n-1]開始，遍歷方向為向右，向上（算法上一般講向下，是指level層數(shù)意義上的；我這里取向上是指物理地址空間意義上的，方便圖文對應(yīng)）
• 每層節(jié)點數(shù)是下層的一半， 即level 0有全部n個節(jié)點，level 1有n/2個節(jié)點，leve l2有n/4個節(jié)點
• 索引結(jié)構(gòu)的高度是log n，整個跳表的空間復(fù)雜度可以近似地看作是O(n + log n)；但在實際應(yīng)用中，存儲的節(jié)點數(shù)n較小，通常將其簡化為O(n)

3、查找

跳表查找5.png

以下以查找元素5為例，詳細(xì)描述查找過程

• 從head的forward[n-1]開始，指向node3
• node3的value為3，小于查找值5，跳轉(zhuǎn)node3
• node3的forward[n-1]指向空，無法向右；向上跳轉(zhuǎn)forward[n-2]
• node3的forward[n-2]指向node6，node6的value為6，大于5，無法向右；向上跳轉(zhuǎn)forward[n-3]
• node3的forward[n-3]指向node6，node6的value為6，大于5，無法向右；向上跳轉(zhuǎn)直至forward[4]
• node3的forward[4]指向node4，node4的value為4，小于5，向右跳轉(zhuǎn)至node4
• node4的forward[4]指向node6，node6的value為6，大于5，無法向右；向上跳轉(zhuǎn)直至forward[3]
• node4的forward[3]指向node5，node5的value為5，等于查找值5，查找結(jié)束

    public T get(String key) {
        Node<T> current = head;
        for (int i = level - 1; i >= 0; i--) {
            while (current.forwards[i] != null && current.forwards[i].key.compareTo(key) < 0) {
                current = current.forwards[i];
            }
        }
        current = current.forwards[0];
        if (current != null && current.key.equals(key)) {
            return current.value;
        } else {
            return null;
        }
    }

在最壞情況下，查找操作可能需要遍歷整個跳表，導(dǎo)致時間復(fù)雜度變?yōu)镺(n)。平均情況下的時間復(fù)雜度是O(log n)。

4、插入

在查找中我們沒有講到整個索引表是如何構(gòu)建出來，所以在插入中我們重點講一下如何構(gòu)建整個跳表的節(jié)點和索引的。

4.1、如何保證level h層的索引數(shù)1= n/2^h

要保證level 0有n個節(jié)點的索引，level 1有n/2個索引，level 2有n/4個索引, level 3有n/4個索引...
我們可以通過randomLevel函數(shù)來實現(xiàn)這個分布；randomLevel() 隨機生成 1~MAX_LEVEL 之間的數(shù)（MAX_LEVEL表示索引的最高層數(shù)），當(dāng)randomLevel返回1，表示當(dāng)前node只有一層索引（level 0層），概率為100%(返回值>=1的概率為100%)；當(dāng)randomLevel返回2，表示當(dāng)前node有2層索引（level 1層），概率為1/2；當(dāng)randomLevel返回3，表示當(dāng)前node有3層索引（level 2層），概率為1/4；所以在大量數(shù)據(jù)插入時，node節(jié)點按這個概率去生成forward數(shù)組，整個表基本會滿足這個分布，代碼如下：

    private final Random rand = new Random();
    private final double P = 0.5;
    private final int MAX_LEVEL = 16;

    private int randomLevel() {
        int newLevel = 1;
        while (rand.nextDouble() < P && newLevel < MAX_LEVEL) {
            newLevel++;
        }
        return newLevel;
    }

4.2插入節(jié)點和更新索引

• 本處以插入node4為例，假設(shè)randomlevel生成的索引層數(shù)為5層，插入前表結(jié)構(gòu)如下

  
  
  插入前.png

• 尋找到合適的插入位置，查找算法同步驟3，找到node3

  
  
  尋找插入位置

• 查找過程中，記錄需要更新索引的左側(cè)update節(jié)點，本例中是node3的forward[0] ~ forward[4]（下圖紅框選中節(jié)點）

  
  
  記錄左側(cè)待更新索引節(jié)點.png

• 更新索引，將node4的forward[0] ~ forward[4]指向原node3的forward[0] ~ forward[4]所指向的節(jié)點；然后將node3的forward[0] ~ forward[4]指向插入的node4；

  
  
  更新索引

• 插入流程結(jié)束，平均時間復(fù)雜度為O(log n)。

5、刪除

刪除與插入一樣，需要對索引進行更新，本處以刪除node1為例

• 查找刪除節(jié)點的前一節(jié)點，本例為node0；同時記錄需要更新索引的左側(cè)update節(jié)點（下圖紅框選中節(jié)點）

  
  
  查找待刪除節(jié)點的前面一個節(jié)點

• 更新索引，將update數(shù)組的forwards指向node1的forwards

  
  
  更新索引
• 刪除流程結(jié)束，平均時間復(fù)雜度為O(log n)。

public void remove(String key) {
        Node<T>[] update = new Node[level];
        Node<T> current = head;
        for (int i = level; i >= 0; i--) {
            while (current.forwards[i] != null && current.forwards[i].key.compareTo(key) < 0) {
                current = current.forwards[i];
            }
            update[i] = current;
        }
        current = current.forwards[0];
        if (current != null && current.key.equals(key)) {
            for (int i = 0; i <= level; i++) {
                if (update[i].forwards[i] != current) {
                    break;
                }
                update[i].forwards[i] = current.forwards[i];
            }
            while (level > 0 && head.forwards[level] == null) {
                level--;
            }
            nodeCount--;
        }
    }

總結(jié)

• 跳表是一個接近二分查找的有序鏈表
• 跳表中最核心的就是搜索，不管是在插入，更新，刪除還是查找中，都要先搜索
• 跳表在插入node時，通過隨機數(shù)確定node中層數(shù)的
• 跳表相對于紅黑樹，優(yōu)勢是相對容易實現(xiàn)，和范圍查找方便