拜托，面試別再問我跳錶了！

何為跳錶？

跳錶是一個隨機化的數據結構，實質就是一種可以進行二分查找的有序鏈表。

跳錶在原有的有序鏈表上面增加了多級索引，通過索引來實現快速查找。

跳錶不僅能提高搜索性能，同時也可以提高插入和刪除操作的性能。

跳錶詳解

有序鏈表

考慮一個有序鏈表，我們要查找3、7、17這幾個元素，我們只能從頭開始遍歷鏈表，直到查找到元素為止。

上述這個鏈表是有序的，但是不能使用二分查找，是不是很捉急？（P.S.數組可以實現二分查找）

那麼，有沒有什麼方法可以實現有序鏈表的二分查找呢？

答案是肯定的，那就是我們將要介紹的這種數據結構——跳錶。

跳錶的演進

我們把一些節點從有序表中提取出來，緩存一級索引，就組成了下麵這樣的結構：

現在，我們要查找17這個元素是不是要快很多呢？

我們只要從一級索引往後遍歷即可，只需要經過1、6、15、17這幾個元素就可以找到17了。

那麼，我們要查找11這個元素呢？

我們從一級索引的1開始，向右到6，再向右發現是15，它比11大，此路不通，從6往下走，再從下麵的6往右走，到7，再到11。

同樣地，一級索引也可以往上再提取一層，組成二級索引，如下：

這時候我們再查找17這個元素呢？

只需要經過6、15、17這幾個元素就可以找到17了。

這基本上就是跳錶的核心思想了，其實這也是一個“空間換時間”的演算法，通過向上提取索引增加了查找的效率。

跳錶的插入

上面講的都是跳錶的查詢，那麼，該如何向跳錶中插入元素呢？

比如，我們要向上面這個跳錶添加一個元素8。

首先，我們先根據投硬幣的方式，決定8這個元素要占據的層數，沒錯就是扔硬幣，是不是很好玩兒^^

比如，層數level=2。

然後，找到8這個元素在下麵兩層的前置節點。

接著，就是鏈表的插入元素操作了，比較簡單。

最後，就像下麵這樣：

跳錶的刪除

查詢、插入元素都講了，下麵我們就來說說怎麼刪除元素。

首先，找到各層中包含元素x的節點。

然後，使用標準的鏈表刪除元素的方法刪除即可。

比如，要刪除17這個元素。

標準化的跳錶

上面舉的例子是完全隨機的跳錶，那麼，如果我們每兩個元素提取一個元素作為上一級的索引會怎麼樣呢？

這是不是很像平衡二叉樹，現在這顆樹元素比較少，可能不太明顯，我們來看個元素個數多的情況。

可以看到，上一級元素的個數是下一級的一半，這樣每次減少一半，就很接近平衡二叉樹了。

時間複雜度

我們知道單鏈表查詢的時間複雜度為O(n)，而插入、刪除操作需要先找到對應的位置，所以插入、刪除的時間複雜度也是O(n)。

那麼，跳錶的時間複雜度是多少呢？

如果按照標準的跳錶來看的話，每一級索引減少k/2個元素（k為其下麵一級索引的個數），那麼整個跳錶的高度就是(log n)。

學習過平衡二叉樹的同學都知道，它的時間複雜度與樹的高度成正比，即O(log n)。

所以，這裡跳錶的時間複雜度也是O(log n)。（這裡不一步步推倒了，只要記住，查詢時每次減少一半的元素的時間複雜度都是O(log n)，比如二叉樹的查找、二分法查找、歸併排序、快速排序）

空間複雜度

我們還是以標準的跳錶來分析，每兩個元素向上提取一個元素，那麼，最後額外需要的空間就是：

n/2 + (n/2)^2 + (n/2)^3 + ... + 8 + 4 + 2 = n - 2

所以，跳錶的空間複雜度是O(n)。

總結

（1）跳錶是可以實現二分查找的有序鏈表；

（2）每個元素插入時隨機生成它的level；

（3）最低層包含所有的元素；

（4）如果一個元素出現在level(x)，那麼它肯定出現在x以下的level中；

（5）每個索引節點包含兩個指針，一個向下，一個向右；

（6）跳錶查詢、插入、刪除的時間複雜度為O(log n)，與平衡二叉樹接近；

彩蛋

為什麼Redis選擇使用跳錶而不是紅黑樹來實現有序集合？

首先，我們來分析下Redis的有序集合支持的操作：

1）插入元素

2）刪除元素

3）查找元素

4）有序輸出所有元素

5）查找區間內所有元素

其中，前4項紅黑樹都可以完成，且時間複雜度與跳錶一致。

但是，最後一項，紅黑樹的效率就沒有跳錶高了。

在跳錶中，要查找區間的元素，我們只要定位到兩個區間端點在最低層級的位置，然後按順序遍歷元素就可以了，非常高效。

而紅黑樹只能定位到端點後，再從首位置開始每次都要查找後繼節點，相對來說是比較耗時的。

此外，跳錶實現起來很容易且易讀，紅黑樹實現起來相對困難，所以Redis選擇使用跳錶來實現有序集合。