一、概述

跳表是一種在各個方面都比較優秀的動態數據結構，可支持快速的插入、刪除、查找操作，甚至可以替代紅黑樹(Red-black Tree)
應用：Redis 中的有序集合(sorted set)是用跳表實現的。

基本思想

結合 鏈表 和 二分法 的特點，將鏈表進行加工，創造一個二者的結合體：

• 鏈表從頭節點到尾節點是有序的
• 可以進行跳躍查找（形如二分法）

例如：我們建立兩層索引(第三層和第二層)，若要查找某個結點，比如d?？梢韵仍诘谌龑舆M行遍歷，當遍歷的時候，發現結點d在結點a和節點e之間，則通過第三層結點a的指針，下降到第二層，繼續遍歷==》結點c和節點e之間==》結點c的指針到第一層 ==》繼續遍歷，找到結點d

當鏈表的長度 n 比較大時，比如 1000、10000 的時候，在構建索引之后，查找效率的提升就會非常明顯。

二、分析

1、時間復雜度分析

如果鏈表里有 n 個結點，會有多少級索引呢？

每兩個結點會抽取一個作為上一級索引的結點，所以第 k 級索引的結點個數是第 k-1 級索引的結點個數的 1/2，那第 k級索引結點的個數就是 n/(2k)。
==》
假設索引有 h 級，最高級的索引有 2 個結點。通過上面的公式，我們可以得到 n/(2h)=2，從而求得 h=log₂n-1。如果包含原始鏈表這一層，整個跳表的高度就是log₂n。
==》
在跳表中查詢某個數據的時候，如果每一層都要遍歷 m 個結點，那在跳表中查詢一個數據的時間復雜度就是 O(m*logn)。其中 m=3（二分思想）
==》時間復雜度：O(logn)

2、空間復雜度分析

原始鏈表大小為n，每2個結點抽1個，每層索引的結點數為：

n/2, n/4, n/8, ... , 8 , 4 , 2

結點總和為 n/2 + n/4 + n/8 + … + 8 + 4 + 2 = n - 2
==》空間復雜度為O(n)

3、變形

每兩個結點抽一個結點到上級索引 ==》每三個結點或五個結點，抽一個結點到上級索引

則，第一級索引需要大約 n/3 個結點，第二級索引需要大約 n/9 個結點。每往上一級，索引結點個數都除以 3。通過等比數列求和公式，總的索引結點大約就是 n/3+n/9+…
+9+3+1=n/2。
==》雖然空間復雜度仍為O(n)，但是減少了一半索引結點存儲空間

但是實際應用中，不必太在意索引占用的額外空間。

三、操作

1、動態插入和刪除

• 插入、刪除操作的時間復雜度為 O(logn)

為了保證原始鏈表中數據的有序性，需要先找到要插入的位置（時間復雜度為O(logn)），然后執行插入操作。

刪除操作：若該結點在索引中也有出現，除了要刪除原始鏈表中的結點外，還要刪除索引中的。需要獲得要刪除結點的前驅結點。

2、索引動態更新

當不停地插入向跳表中插入數據時，如果不更新索引，可能導致某兩個索引結點之間的數據非常多的情況 ==》退化為單鏈表

解決方法：通過隨機函數來維護索引與原始鏈表大小之間的 “平衡性”。也就是說，如果鏈表中結點多了，索引結點就相應地增加一些，避免復雜度退化，以及查找、插入、刪除操作性能下降。

通過隨機函數來決定該結點插入到哪一層索引中，比如隨機函數生成了 K，則將該結點添加到第一級到第K級這K級索引中。

四、應用

Redis 使用跳表實現有序集合（其實也包括散列表，此處先忽略掉），而非紅黑樹？

Redis中有序結合支持的核心操作主要是：

• 插入一個數據；
• 刪除一個數據；
• 查找一個數據；
• 按照區間查找數據（eg: 查找值在[155, 296]區間內）==》時間復雜度：O(logn)
• 迭代輸出有序序列

跳表更加靈活，它可以通過改變索引構建策略，有效平衡執行效率和內存消耗。

總結

以上是生活随笔為你收集整理的九、跳表(Skip List)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。