跳跃表的原理与实现：如何用概率数据结构达到平衡树的性能

一、从“电梯”说起：为什么我们需要跳跃表？

想象一下，你在一栋有100层的大楼里工作，你的工位在第99层。每天上班，你都需要从1楼坐电梯上去。如果这栋楼只有一部“停靠每一层”的慢速电梯，那你每天光等电梯和停靠的时间就非常漫长。

聪明的物业经理想了个办法：他加装了几部“特快电梯”。一部只停靠1楼、25楼、50楼、75楼、100楼；另一部停靠1楼、50楼、100楼。现在，你想去99楼，最优的策略是：

先坐“特快电梯”到75楼。
然后换乘“普通电梯”（或者走楼梯）从75楼到99楼。

这个策略让你跳过了大量无关的楼层，大大提升了“查找”目标楼层的效率。

跳跃表（Skip List） 的核心思想，就和这个“多级电梯”模型一模一样。它是一种用于有序元素集合的数据结构，主要用来快速查找、插入和删除。它的设计目标，就是在保持链表结构简单性的同时，通过增加“快速通道”（索引层），达到和平衡树（如红黑树、AVL树）相近的查询性能（平均O(log n)），而实现起来却要简单直观得多。

它的秘密武器就是概率。不是通过复杂的旋转规则来维持平衡，而是通过“抛硬币”来决定一个元素能建多高的“快速电梯”。

二、跳跃表的“骨架”：多级链表是如何搭建的？

一个基础的跳跃表由多层链表组成。最底层（第0层）是一个包含所有元素的有序链表，就像那部“每层都停”的普通电梯。

往上每一层，都可以看作是下一层的一个“稀疏索引”或“快速通道”。高层链表中的节点会“向下”指向底层链表中对应的同一个节点。

关键点：节点的“高度” 每个节点除了存储值（key）和指向同层下一个节点的指针（next）外，还有一个非常重要的属性：层数（level）。这个层数不是固定的，而是在节点被创建时，通过一个“抛硬币”的过程随机决定的。

规则很简单：从第0层开始，每次“抛硬币”，如果是正面，就为这个节点增加一层，继续抛；直到抛出反面为止。这样，一个节点就有1层、2层…甚至更多层。层数越高，概率越低。这就保证了高层节点非常少，形成了天然的“稀疏索引”。

让我们用一个完整的例子来构建一个跳跃表。为了清晰和通用性，我们使用 Python 作为技术栈来演示。

技术栈：Python

import random
from typing import Optional

class SkipNode:
    """跳跃表节点类"""
    def __init__(self, key: int, level: int):
        self.key = key          # 节点存储的值
        self.forward = [None] * (level + 1)  # forward[i] 表示该节点在第i层指向的下一个节点

class SkipList:
    """跳跃表类"""
    def __init__(self, max_level: int = 16, p: float = 0.5):
        """
        初始化跳跃表。
        :param max_level: 最大允许的层数，防止层数无限增长。
        :param p: “抛硬币”正面朝上的概率，决定节点层数的分布。
        """
        self.max_level = max_level
        self.p = p
        self.header = SkipNode(-1, max_level)  # 头节点，拥有最大层数，值为-1（小于任何有效值）
        self.level = 0  # 当前跳跃表实际使用的最大层数（不包括头节点）

    def _random_level(self) -> int:
        """
        模拟抛硬币，随机生成新节点的层数。
        从第0层开始，每次‘抛硬币’（随机数小于p），层数加一。
        """
        lvl = 0
        while random.random() < self.p and lvl < self.max_level:
            lvl += 1
        return lvl

    def insert(self, key: int):
        """向跳跃表中插入一个键值。"""
        # update 数组用于记录在每一层中，待插入节点位置的前驱节点
        update = [None] * (self.max_level + 1)
        current = self.header

        # 从最高层开始，逐层向下查找插入位置
        for i in range(self.level, -1, -1):
            # 在当前层向右遍历，直到找到下一个节点值大于或等于key的节点
            while current.forward[i] and current.forward[i].key < key:
                current = current.forward[i]
            # 记录下当前层中，最后一个小于key的节点，它将是新节点在该层的前驱
            update[i] = current

        # 移动到第0层（最底层）的下一个节点，这就是我们要插入的位置
        current = current.forward[0]

        # 如果该key已存在，可以选择更新或直接返回（这里我们假设不允许重复键，直接返回）
        if current is None or current.key != key:
            # 为新区节点生成随机层数
            new_level = self._random_level()

            # 如果新节点的层数超过了当前跳跃表的层数，需要更新头节点在更高层的指针
            if new_level > self.level:
                for i in range(self.level + 1, new_level + 1):
                    update[i] = self.header  # 这些更高层的前驱节点都是头节点
                self.level = new_level  # 更新跳跃表层数

            # 创建新节点
            new_node = SkipNode(key, new_level)

            # 将新节点插入到各层链表中
            for i in range(new_level + 1):
                # 新节点在第i层的后继，指向原前驱节点在第i层的后继
                new_node.forward[i] = update[i].forward[i]
                # 原前驱节点在第i层的后继，更新为新节点
                update[i].forward[i] = new_node

            print(f"已插入键值: {key}，节点层数: {new_level}")

    def search(self, key: int) -> Optional[SkipNode]:
        """在跳跃表中查找一个键值，找到则返回节点，否则返回None。"""
        current = self.header
        # 同样从最高层开始查找
        for i in range(self.level, -1, -1):
            while current.forward[i] and current.forward[i].key < key:
                current = current.forward[i]
        # 定位到第0层最接近的节点
        current = current.forward[0]

        # 检查是否找到
        if current and current.key == key:
            print(f"已找到键值: {key}")
            return current
        else:
            print(f"未找到键值: {key}")
            return None

    def delete(self, key: int):
        """从跳跃表中删除一个键值。"""
        update = [None] * (self.max_level + 1)
        current = self.header

        # 查找过程与插入类似，记录每一层中待删除节点的前驱
        for i in range(self.level, -1, -1):
            while current.forward[i] and current.forward[i].key < key:
                current = current.forward[i]
            update[i] = current

        current = current.forward[0]

        # 如果找到要删除的节点
        if current is not None and current.key == key:
            # 从最底层开始，逐层将前驱节点的指针绕过当前节点
            for i in range(self.level + 1):
                # 如果第i层的前驱节点的后继不是当前节点，说明该层没有这个节点，可以停止
                if update[i].forward[i] != current:
                    break
                update[i].forward[i] = current.forward[i]

            # 删除节点后，可能需要降低跳跃表的层级（如果最高层只剩下头节点）
            while self.level > 0 and self.header.forward[self.level] is None:
                self.level -= 1
            print(f"已删除键值: {key}")
        else:
            print(f"删除失败，未找到键值: {key}")

    def display(self):
        """以层级方式打印跳跃表（用于可视化）。"""
        print("\n***** 跳跃表结构 *****")
        for i in range(self.level, -1, -1):
            node = self.header.forward[i]
            print(f"第 {i} 层: ", end="")
            while node is not None:
                print(f"{node.key} -> ", end="")
                node = node.forward[i]
            print("None")

# 让我们来实际运行一下，看看跳跃表是如何工作的
if __name__ == "__main__":
    skip_list = SkipList(max_level=4, p=0.5)
    keys_to_insert = [3, 6, 7, 9, 12, 19, 17, 26, 21, 25]

    print("=== 开始插入操作 ===")
    for key in keys_to_insert:
        skip_list.insert(key)

    skip_list.display()

    print("\n=== 开始查找操作 ===")
    skip_list.search(19)
    skip_list.search(20)

    print("\n=== 开始删除操作 ===")
    skip_list.delete(19)
    skip_list.delete(20)

    skip_list.display()

运行这段代码，你可以清晰地看到节点是如何被插入到不同层级的。例如，值 19 的节点可能出现在第0、1、2层，而值 3 的节点可能只出现在第0层。查找 19 时，查找路径会从高层（快速通道）开始，迅速跳跃到目标区域，再在底层精确锁定。

三、性能探秘：为什么它能媲美平衡树？

现在我们来回答核心问题：这个看似随机的结构，凭什么和精心设计的平衡树叫板？

1. 查找的“高速公路”效应 查找时，我们从最高层开始。因为高层节点非常稀疏，我们每次向右移动，都能跨越底层的大量节点。这就像坐上了特快电梯。然后逐层下降，搜索范围迅速缩小。平均下来，只需要遍历大约 (1/p) * log_{1/p}(n) 个节点。当 p=0.5 时，复杂度约为 O(2 * log2(n))，也就是 O(log n)。这和平衡树的二分查找效率在同一个数量级。

2. 插入与删除的“优雅” 插入和删除的核心都是先找到位置。由于查找是O(log n)的，所以插入和删除的主要开销也是O(log n)。插入时，我们只需要为新节点随机生成层数，然后像在普通链表中插入一样，更新各层前驱节点的指针即可。删除同理。整个过程没有平衡树那种复杂的旋转（Rebalancing）操作，实现极其简洁。

关联技术对比：红黑树 红黑树通过严格的着色规则和旋转操作来保证树的大致平衡，从而确保最坏情况下的性能。但它的实现非常复杂，容易出错。跳跃表通过概率来保证“统计意义上”的平衡，虽然存在极小的概率导致性能退化，但在实践中，只要最大层数设置合理（如对于10亿数据，设max_level=32），其性能表现非常稳定，且代码可读性远胜于红黑树。

四、跳跃表的舞台与两面性

任何技术都有其适用场景和优缺点，跳跃表也不例外。

应用场景：

Redis的有序集合（Sorted Set）: 这是跳跃表最著名的应用。Redis使用跳跃表作为有序集合的底层实现之一（在元素较多或元素较长时），因为它支持高效的区间查询（ZRANGE），这对于排行榜等功能至关重要。
内存中的有序数据结构： 当你需要一个线程安全、支持高效并发操作的有序容器时，并发跳跃表（如Java的ConcurrentSkipListMap）是绝佳选择。它的无锁或细粒度锁设计比并发平衡树更友好。
需要频繁插入删除的排序列表： 相比于平衡树，跳跃表的插入删除逻辑更简单，常数因子更小，在某些场景下实际性能更好。

技术优缺点：

优点：
- 实现简单： 核心代码几百行就能搞定，调试和维护成本低。
- 性能优异： 平均时间复杂度与平衡树持平，均为O(log n)。
- 支持高效区间查询： 找到区间起点后，在底层链表上线性遍历即可，非常自然。
- 易于并发优化： 链表结构更容易实现细粒度的锁或无锁算法。
缺点：
- 空间开销： 每个节点需要存储多个指针（平均 1/(1-p) 个，p=0.5时约为2个），比普通链表和二叉树的指针开销大。
- 非绝对平衡： 性能是“概率平衡”或“期望平衡”，存在极低概率的性能退化可能（虽然可通过参数控制）。
- 缓存不友好： 节点在内存中可能不连续，指针跳转对CPU缓存（Cache）不如数组或紧凑的树结构友好。

注意事项：

参数调优： 概率 p 和最大层数 max_level 需要根据数据规模预估。p=0.5 是一个经典值。max_level 可以设为 log_{1/p}(n) 的上界，例如 log2(最大预期元素数)。
内存管理： 在手动管理内存的语言（如C++）中，注意节点删除时的内存释放，避免内存泄漏。
重复键处理： 示例中假设键唯一。如果需要支持重复键，需要在节点结构或比较逻辑上进行调整。

五、总结

跳跃表是一个将“简单”与“高效”结合得淋漓尽致的典范。它放弃了平衡树那种 deterministic（确定性）的严格平衡，转而拥抱概率，用“随机层高”构建多级索引，换来了代码实现上的极大简化，同时又在统计意义上获得了与平衡树匹敌的搜索性能。

它特别适合那些需要快速查找、插入、删除以及区间遍历，并且对实现复杂度敏感、或需要高并发的场景。下次当你使用Redis的排行榜功能，或者看到Java的ConcurrentSkipListMap时，你就会知道，背后正是这个优雅的概率数据结构在默默支撑。

所以，如果你在项目中需要一个高效的有序容器，又不想陷入红黑树复杂的旋转逻辑中，不妨考虑一下跳跃表——这个用“抛硬币”抛出来的性能利器。

敲码拾光专注于编程技术，涵盖编程语言、代码实战案例、软件开发技巧、IT前沿技术、编程开发工具，是您提升技术能力的优质网络平台。