---

什么是跳表

對于一個單鏈表來講，即便鏈表中存儲的數(shù)據(jù)是有序的，如果我們要想在其中查找某個數(shù)據(jù)，也只能從頭到尾遍歷鏈表。這樣查找效率就會很低，時間復(fù)雜度會很高，是 O(n)。

那怎么來提高查找效率呢？如果像圖中那樣，對鏈表建立一級“索引”，查找起來是不是就會更快一些呢？每兩個結(jié)點提取一個結(jié)點到上一級，我們把抽出來的那一級叫做索引或索引層。你可以看我畫的圖。圖中的 down 表示 down 指針，指向下一級結(jié)點。

如果我們現(xiàn)在要查找某個結(jié)點，比如 16。我們可以先在索引層遍歷，當(dāng)遍歷到索引層中值為 13 的結(jié)點時，我們發(fā)現(xiàn)下一個結(jié)點是 17，那要查找的結(jié)點 16 肯定就在這兩個結(jié)點之間。然后我們通過索引層結(jié)點的 down 指針，下降到原始鏈表這一層，繼續(xù)遍歷。這個時候，我們只需要再遍歷 2 個結(jié)點，就可以找到值等于 16 的這個結(jié)點了。這樣，原來如果要查找 16，需要遍歷 10 個結(jié)點，現(xiàn)在只需要遍歷 7 個結(jié)點。

從這個例子里，我們看出，加來一層索引之后，查找一個結(jié)點需要遍歷的結(jié)點個數(shù)減少了，也就是說查找效率提高了。那如果我們再加一級索引呢？效率會不會提升更多呢？

跟前面建立第一級索引的方式相似，我們在第一級索引的基礎(chǔ)之上，每兩個結(jié)點就抽出一個結(jié)點到第二級索引?，F(xiàn)在我們再來查找 16，只需要遍歷 6 個結(jié)點了，需要遍歷的結(jié)點數(shù)量又減少了。

這種鏈表加多級索引的結(jié)構(gòu)，就是跳表。

跳表的時間復(fù)雜度

按照我們剛才講的，每兩個結(jié)點會抽出一個結(jié)點作為上一級索引的結(jié)點，那第一級索引的結(jié)點個數(shù)大約就是 n/2，第二級索引的結(jié)點個數(shù)大約就是 n/4，第三級索引的結(jié)點個數(shù)大約就是 n/8，依次類推，也就是說，第 k 級索引的結(jié)點個數(shù)是第 k-1 級索引的結(jié)點個數(shù)的 1/2，那第 k 級索引結(jié)點的個數(shù)就是 n/(2^k)。

假設(shè)索引有 h 級，最高級的索引有 2 個結(jié)點。通過上面的公式，我們可以得到 n/(2^h)=2，從而求得 h=log2n-1。如果包含原始鏈表這一層，整個跳表的高度就是 log2n。我們在跳表中查詢某個數(shù)據(jù)的時候，如果每一層都要遍歷 m 個結(jié)點，那在跳表中查詢一個數(shù)據(jù)的時間復(fù)雜度就是 O(m*logn)。

那這個 m 的值是多少呢？按照前面這種索引結(jié)構(gòu)，我們每一級索引都最多只需要遍歷 3 個結(jié)點，也就是說 m=3，為什么是 3 呢？我來解釋一下。

假設(shè)我們要查找的數(shù)據(jù)是 x，在第 k 級索引中，我們遍歷到 y 結(jié)點之后，發(fā)現(xiàn) x 大于 y，小于后面的結(jié)點 z，所以我們通過 y 的 down 指針，從第 k 級索引下降到第 k-1 級索引。在第 k-1 級索引中，y 和 z 之間只有 3 個結(jié)點（包含 y 和 z），所以，我們在 K-1 級索引中最多只需要遍歷 3 個結(jié)點，依次類推，每一級索引都最多只需要遍歷 3 個結(jié)點。

通過上面的分析，我們得到 m=3，所以在跳表中查詢?nèi)我鈹?shù)據(jù)的時間復(fù)雜度就是 O(logn)。這個查找的時間復(fù)雜度跟二分查找是一樣的。換句話說，我們其實是基于單鏈表實現(xiàn)了二分查找.

跳表的空間復(fù)雜度

通過上面的分析，我們得到 m=3，所以在跳表中查詢?nèi)我鈹?shù)據(jù)的時間復(fù)雜度就是 O(logn)。這個查找的時間復(fù)雜度跟二分查找是一樣的。換句話說，我們其實是基于單鏈表實現(xiàn)了二分查找

這幾級索引的結(jié)點總和就是 n/2+n/4+n/8…+8+4+2=n-2。所以，跳表的空間復(fù)雜度是 O(n)。也就是說，如果將包含 n 個結(jié)點的單鏈表構(gòu)造成跳表，我們需要額外再用接近 n 個結(jié)點的存儲空間。

如何高效的插入和刪除

我們知道，在單鏈表中，一旦定位好要插入的位置，插入結(jié)點的時間復(fù)雜度是很低的，就是 O(1)。但是，這里為了保證原始鏈表中數(shù)據(jù)的有序性，我們需要先找到要插入的位置，這個查找操作就會比較耗時。

對于純粹的單鏈表，需要遍歷每個結(jié)點，來找到插入的位置。但是，對于跳表來說，我們講過查找某個結(jié)點的時間復(fù)雜度是 O(logn)，所以這里查找某個數(shù)據(jù)應(yīng)該插入的位置，方法也是類似的，時間復(fù)雜度也是 O(logn)。我畫了一張圖，你可以很清晰地看到插入的過程。

我們再看下刪除操作。 如果這個結(jié)點在索引中也有出現(xiàn)，我們除了要刪除原始鏈表中的結(jié)點，還要刪除索引中的。因為單鏈表中的刪除操作需要拿到要刪除結(jié)點的前驅(qū)結(jié)點，然后通過指針操作完成刪除。所以在查找要刪除的結(jié)點的時候，一定要獲取前驅(qū)結(jié)點。當(dāng)然，如果我們用的是雙向鏈表，就不需要考慮這個問題了。

跳表索引動態(tài)更新

當(dāng)我們不停地往跳表中插入數(shù)據(jù)時，如果我們不更新索引，就有可能出現(xiàn)某 2 個索引結(jié)點之間數(shù)據(jù)非常多的情況。極端情況下，跳表還會退化成單鏈表。

作為一種動態(tài)數(shù)據(jù)結(jié)構(gòu)，我們需要某種手段來維護索引與原始鏈表大小之間的平衡，也就是說，如果鏈表中結(jié)點多了，索引結(jié)點就相應(yīng)地增加一些，避免復(fù)雜度退化，以及查找、插入、刪除操作性能下降。

當(dāng)我們往跳表中插入數(shù)據(jù)的時候，我們可以選擇同時將這個數(shù)據(jù)插入到部分索引層中。如何選擇加入哪些索引層呢？

我們通過一個隨機函數(shù)，來決定將這個結(jié)點插入到哪幾級索引中，比如隨機函數(shù)生成了值 K，那我們就將這個結(jié)點添加到第一級到第 K 級這 K 級索引中。

隨機函數(shù)的選擇很有講究，從概率上來講，能夠保證跳表的索引大小和數(shù)據(jù)大小平衡性，不至于性能過度退化。

代碼示例

public class SkipList {private static final float SKIPLIST_P = 0.5f;private static final int MAX_LEVEL = 16;private int levelCount = 1;private Node head = new Node();  // 帶頭鏈表public Node find(int value) {Node p = head;for (int i = levelCount - 1; i >= 0; --i) {while (p.forwards[i] != null && p.forwards[i].data < value) {p = p.forwards[i];}}if (p.forwards[0] != null && p.forwards[0].data == value) {return p.forwards[0];} else {return null;}}public void insert(int value) {// 隨機索引層數(shù)int level = randomLevel();// 定義新節(jié)點Node newNode = new Node();newNode.data = value;//Node update[] = new Node[level];for (int i = 0; i < level; ++i) {update[i] = head;}// record every level largest value which smaller than insert value in update[]Node p = head;for (int i = level - 1; i >= 0; --i) {while (p.forwards[i] != null && p.forwards[i].data < value) {p = p.forwards[i];}update[i] = p;// use update save node in search path}// in search path node next node become new node forwords(next)for (int i = 0; i < level; ++i) {newNode.forwards[i] = update[i].forwards[i];update[i].forwards[i] = newNode;}// update node hightif (levelCount < level) levelCount = level;}public void delete(int value) {Node[] update = new Node[levelCount];Node p = head;for (int i = levelCount - 1; i >= 0; --i) {while (p.forwards[i] != null && p.forwards[i].data < value) {p = p.forwards[i];}update[i] = p;}if (p.forwards[0] != null && p.forwards[0].data == value) {for (int i = levelCount - 1; i >= 0; --i) {if (update[i].forwards[i] != null && update[i].forwards[i].data == value) {update[i].forwards[i] = update[i].forwards[i].forwards[i];}}}while (levelCount > 1 && head.forwards[levelCount] == null) {levelCount--;}}// 理論來講，一級索引中元素個數(shù)應(yīng)該占原始數(shù)據(jù)的 50%，二級索引中元素個數(shù)占 25%，三級索引12.5% ，一直到最頂層。// 因為這里每一層的晉升概率是 50%。對于每一個新插入的節(jié)點，都需要調(diào)用 randomLevel 生成一個合理的層數(shù)。// 該 randomLevel 方法會隨機生成 1~MAX_LEVEL 之間的數(shù)，且 ：//        50%的概率返回 1//        25%的概率返回 2//      12.5%的概率返回 3 ...private int randomLevel() {int level = 1;while (Math.random() < SKIPLIST_P && level < MAX_LEVEL)level += 1;return level;}public void printAll() {Node p = head;while (p.forwards[0] != null) {System.out.print(p.forwards[0] + " ");p = p.forwards[0];}System.out.println();}public class Node {private int data = -1;private Node forwards[] = new Node[MAX_LEVEL];}
}