数据结构之跳表

跳表（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)	可能有额外开销（解决冲突）
并发友好性	高（局部修改）	较低（结构调整可能影响大）	需要处理哈希冲突和扩容