數據結構之跳表

跳表（Skip List）是一種基于概率平衡的數據結構，通過多層有序鏈表實現高效的查找、插入和刪除操作。它在最壞情況下時間復雜度為 (O(n))，但通過隨機化設計，平均時間復雜度可優化至 (O(\log n))，與平衡二叉搜索樹性能相當，但實現更為簡單。

1. 什么是跳表？

想象一下，你有一本非常厚的電話簿，里面的名字是按字母順序排列的。現在你想找 “Zhang San” 這個名字。

方法一（鏈表/線性查找）：從第一頁的第一個名字 “A” 開始，一頁一頁地翻，直到找到 “Z”。這非常慢。
方法二（跳表）：聰明的電話簿出版商在書的側面貼上了一些“索引標簽”。比如：
- 第一個標簽指向 “B” 開頭的部分。
- 第二個標簽指向 “G” 開頭的部分。
- 第三個標簽指向 “M” 開頭的部分。
- 第四個標簽指向 “S” 開頭的部分。
- 第五個標簽指向 “Z” 開頭的部分。

現在你找 “Zhang San”：

你先看側面的標簽，發現 “Zhang” 的首字母 “Z” 在 “S” 和 “Z” 之間。于是你直接翻到 “S” 標簽指向的頁面。
從 “S” 開始，你繼續向后翻，因為 “Z” 在 “S” 之后。你可能還會看到一些更細分的標簽，比如 “T”, “W”, “X” 等，幫助你更快地定位。
很快，你就找到了 “Z” 開頭的部分，然后在這個小范圍內順序查找，最終找到 “Zhang San”。

跳表就是這種“帶有多級索引的有序鏈表”。它通過在原始有序鏈表之上建立多級“索引”層，來大幅提升查找效率，使得查找、插入、刪除操作都能在接近對數的時間復雜度內完成。

2. 為什么需要跳表？

跳表是為了解決有序鏈表的痛點而誕生的。

有序鏈表的優點：
- 插入和刪除操作非常快，只需要修改相鄰節點的指針，時間復雜度為?O(1)在找到位置后。
有序鏈表的致命缺點：
- 查找效率極低。由于不能像數組那樣通過下標隨機訪問，查找一個元素必須從頭節點開始逐個遍歷，時間復雜度為?O(n)。當數據量很大時，這個性能是無法接受的。

我們希望有一種數據結構，既能保持鏈表高效的插入/刪除特性，又能擁有像平衡二叉搜索樹那樣?O(log n)?級別的查找效率。

跳表就是答案之一。它通過增加空間（建立索引）來換取時間，完美地平衡了查找、插入、刪除的性能。

3. 跳表的結構與原理

一個跳表由以下幾部分構成：

基礎層：最底層是一個標準的有序鏈表，包含了所有的元素。
索引層：在基礎層之上，有多層稀疏的“索引”鏈表。
- 每一層都是一個有序鏈表。
- 第?L+1?層的元素是第?L?層元素的一個子集。
- 上層的每個節點，都有一個指針指向其在下層中相同的節點。
頭節點：所有層的鏈表都共享一個頭節點，方便從最高層開始查找。
概率性：一個節點出現在多少層索引中，是通過**“拋硬幣”**這樣的隨機算法決定的。這保證了跳表的平衡性，避免了像平衡樹那樣復雜的旋轉操作。

結構示意圖：

假設我們有基礎鏈表?1 <-> 3 <-> 4 <-> 5 <-> 7 <-> 8 <-> 10

一個可能的跳表結構如下：

Level 3:  ------------------------> 8 ------------------------> NULL|                        |
Level 2:  ----> 3 ----------------> 8 ------------------------> NULL|     |                  |
Level 1:  ----> 3 ------> 5 ------> 8 ------> 10 -------------> NULL|     |        |        |        |
Level 0:  -> 1 <-> 3 <-> 4 <-> 5 <-> 7 <-> 8 <-> 9 <-> 10 -> NULL

解讀：

Level 0?是基礎層，包含所有元素。
Level 1?包含了?{3, 5, 8, 10}，它們是 Level 0 的一個子集。
Level 2?包含了?{3, 8}，是 Level 1 的一個子集。
Level 3?只包含了?{8}。
每個上層的節點都通過一個向下的指針連接到下層對應的節點。

4. 操作詳解

a. 查找

查找是跳表最核心的操作，插入和刪除都依賴于它。查找過程遵循“先高層后低層，先大步后小步”的原則。

目標：查找元素?5

從最高層開始：從頭節點?Head?的 Level 3 開始。
Level 3 查找：
- 當前節點是?Head，下一個節點是?8。
- 5 < 8，說明?5?在?Head?和?8?之間。不能在 Level 3 繼續向右走了。
- 向下：移動到 Level 2 的?Head?節點。
Level 2 查找：
- 當前節點是?Head，下一個節點是?3。
- 5 > 3，可以繼續向右走。移動到節點?3。
- 在節點?3，它的下一個節點是?8。
- 5 < 8，說明?5?在?3?和?8?之間。不能在 Level 2 繼續向右走了。
- 向下：移動到 Level 1 的節點?3。
Level 1 查找：
- 當前節點是?3，下一個節點是?5。
- 5 == 5，找到目標！

如果查找?6：

… (過程同上，直到 Level 1 的節點?5)
在 Level 1 的節點?5，下一個節點是?8。
6 < 8，不能向右。
向下：移動到 Level 0 的節點?5。
Level 0 查找：
- 當前節點是?5，下一個節點是?7。
- 6 < 7，且?6 != 5，說明?6?不存在。

查找路徑總結：Head(L3) -> Head(L2) -> 3(L2) -> 3(L1) -> 5(L1)。

b. 插入

插入分為兩步：查找位置?和?隨機建層。

目標：插入元素?6

查找插入位置：
- 按照查找?6?的方法，找到它在 Level 0 中的前驅節點。從上面的查找過程可知，6?應該插入在?5?和?7?之間。我們需要記錄下每一層中?6?的前驅節點，這里主要是 Level 0 的?5。
- 在實際操作中，我們會在查找過程中維護一個?update?數組，記錄每一層中待插入位置的前驅節點。
隨機決定層數：
- 這是跳表的精髓。我們通過一個隨機函數（比如，模擬拋硬幣）來決定新節點?6?要“晉升”到多少層。
- 算法：初始化層數?level = 1。然后循環，每次有?p?(通常?p=1/2?或?1/4) 的概率?level++，直到失敗為止。level?不能超過跳表當前的最大層數。
- 假設我們“拋硬幣”的結果是：第一次成功（level=2），第二次成功（level=3），第三次失敗。那么新節點?6?的層數就是?3。
插入節點并更新指針：
- 如果新節點的層數?3?大于當前跳表的最大層數（比如是?2），則需要增加一個新的 Level 3 層。
- 從?level=3?開始，逐層向下插入新節點：
  - Level 3：將?6?插入到?update[3]?(即?Head) 之后。Head -> 6。
  - Level 2：將?6?插入到?update[2]?(即?3) 之后。3 -> 6。
  - Level 1：將?6?插入到?update[1]?(即?5) 之后。5 -> 6。
  - Level 0：將?6?插入到?update[0]?(即?5) 之后。5 -> 6 -> 7。
- 同時，要確保新節點?6?在每一層的實例都通過?down?指針連接起來。

c. 刪除

刪除操作比插入簡單，因為它不需要隨機建層。

目標：刪除元素?5

查找待刪除節點：
- 首先查找?5。在查找過程中，同樣需要記錄每一層中?5?的前驅節點（update?數組）。
- 如果找不到?5，則刪除失敗。
逐層刪除：
- 從?5?存在的最高層開始（比如 Level 1），逐層向下刪除。
- 在每一層，修改前驅節點（update[i]）的?next?指針，使其指向?5?的后繼節點。
- Level 1：update[1]?是?3，將?3->next?從指向?5?改為指向?8。
- Level 0：update[0]?是?4，將?4->next?從指向?5?改為指向?6。
- 這樣，5?在所有層中的引用都被移除了，垃圾回收器會自動回收內存。
（可選）清理空層：如果刪除某個節點后，最高層只剩下一個頭節點，可以考慮移除這一層以節省空間。

5. 性能分析

時間復雜度：
- 查找、插入、刪除：平均時間復雜度均為?O(log n)。
- 最壞情況：如果運氣極差，所有節點都在同一層，那么跳表就退化成了普通鏈表，時間復雜度為?O(n)。但由于層數是隨機決定的，這種情況的概率極低，可以忽略不計。
空間復雜度：
- 平均空間復雜度為?O(n)。
- 每個節點被包含在第?i?層索引中的概率是?p^(i-1)。一個節點平均包含的指針數是?1/(1-p)。
- 當?p = 1/2?時，每個節點平均有?1 + 1/2 + 1/4 + ... = 2?個指針（一個?next，一個?down）。所以總空間開銷大約是基礎鏈表的 2 倍，即?O(2n) = O(n)。

6. 跳表的優缺點

優點：

性能均衡：查找、插入、刪除的性能都非常優秀，都是 O(log n)。
實現簡單：相比于紅黑樹、AVL樹等平衡二叉搜索樹，跳表的實現邏輯要簡單得多，沒有復雜的旋轉和顏色變換操作。
天然有序：底層是有序鏈表，非常適合需要范圍查詢的場景（如 “查找所有 score 在 100 到 200 之間的元素”）。
并發友好：由于跳表的修改操作（插入、刪除）通常只影響局部節點，不像平衡樹那樣可能引起全局性的結構調整，因此更容易實現高效的并發控制。Redis 的作者就曾評價，跳表在并發環境下比平衡樹更有優勢。

缺點：

空間開銷：需要額外的空間來存儲多層索引，空間復雜度高于普通鏈表和平衡樹（雖然都是 O(n)，但常數因子更大）。
非最壞情況保證：性能是概率性的，雖然最壞情況概率極低，但不像平衡樹那樣能提供硬性的性能保證。

7. 實際應用

跳表最著名的應用是在?Redis?中。

Redis 的有序集合：Redis 的 ZSET (Sorted Set) 數據結構，在元素數量較少時使用?ziplist（壓縮列表）來節省內存，當元素數量超過閾值（zset-max-ziplist-entries）時，會轉換為?跳表 + 哈希表?的實現。
- 跳表：負責按?score?排序，支持高效的范圍查找、按 rank 查找等操作。
- 哈希表：負責建立?member?到?score?的映射，支持 O(1) 復雜度的按?member?查找?score。
- 這種組合完美地發揮了兩種數據結構的優勢。
LevelDB / RocksDB：這些著名的鍵值存儲引擎在其內部內存表（MemTable）的實現中也使用了跳表。

8. 與其他數據結構的對比

特性	跳表	平衡二叉搜索樹 (如紅黑樹)	哈希表
查找	O(log n) 平均	O(log n) 最壞	O(1) 平均
插入	O(log n) 平均	O(log n) 最壞	O(1) 平均
刪除	O(log n) 平均	O(log n) 最壞	O(1) 平均
有序性	天然有序，范圍查詢高效	天然有序，范圍查詢高效	無序，不支持范圍查詢
實現復雜度	相對簡單	復雜（旋轉/變色）	簡單
空間開銷	較高 (約 2n)	較低 (n)	可能有額外開銷（解決沖突）
并發友好性	高（局部修改）	較低（結構調整可能影響大）	需要處理哈希沖突和擴容