一、跳表是什么？为什么需要它？

链表大家都很熟悉了。单链表查找一个元素，得从头结点一个个往后走，时间复杂度是 O(n)。你想想看，如果链表里有 100 万个节点，最坏情况下得比较 100 万次——这谁受得了？

那有没有办法让链表也支持「跳跃式」查找呢？

嗯，这就是跳表（Skip List）的出发点。跳表本质上是一种「多层链表」结构。底层是完整的有序链表，上层是「快速通道」——每几个节点抽一个出来，形成更稀疏的链表。查找时从顶层开始，快速跳过大量节点，再逐层下降，最终定位到目标。

我个人习惯把跳表理解为「链表版的二分查找」。虽然它不像平衡树那样严格平衡，但通过随机化策略，平均性能也能达到 O(log n)。

核心思想：用空间换时间。通过维护多层索引，让链表查找从 O(n) 降到 O(log n)。

二、跳表的结构设计

先看一个简单的跳表长什么样。假设我们有一个有序链表：1 → 3 → 5 → 7 → 9 → 11 → 13 → 15。

如果只有一层，查找 13 需要比较 7 次。但如果我们在上面加一层「索引层」，只保留 1、5、9、13 这四个节点，查找时先走索引层，找到 13 只需要 3 次比较。

跳表的层数不是固定的。每个节点在插入时，会随机决定它的「层高」。比如有的节点只有 1 层（只出现在底层），有的节点有 2 层、3 层甚至更高。层高越高，这个节点在索引层出现的次数就越多，跳过的节点也就越多。

我做过一个项目，需要在嵌入式设备上维护一个动态的在线用户列表。用户 ID 是 uint32_t，插入和查找都很频繁。用普通链表，查找一个用户要遍历几百个节点，延迟完全不可控。换成跳表后，查找时间稳定在几十微秒以内。

节点结构定义

// 跳表节点
typedef struct skip_node {
    int key;                    // 键值（假设为整数）
    int value;                  // 存储的数据
    int level;                  // 该节点的层高
    struct skip_node **forward; // 指向各层下一个节点的指针数组
} skip_node_t;

// 跳表结构
typedef struct skip_list {
    int max_level;              // 最大允许层高
    float probability;          // 层高增长概率（通常 0.25 或 0.5）
    int level;                  // 当前实际最高层数
    skip_node_t *header;        // 头结点（不存储数据，层高为 max_level）
} skip_list_t;

注意这里的 forward 是一个指针数组。forward[0] 指向底层下一个节点，forward[1] 指向第 1 层索引的下一个节点，以此类推。这样设计的好处是：查找时只需要一个节点指针，就能在不同层之间跳转。

三、跳表的核心操作

3.1 随机层高生成

这是跳表最巧妙的地方。每个新节点插入时，我们通过随机数决定它的层高。规则很简单：从第 1 层开始，每次有概率 p 升到下一层，直到达到最大层数或概率失败。

int random_level(int max_level, float probability) {
    int level = 1;
    while ((rand() / (float)RAND_MAX) < probability && level < max_level) {
        level++;
    }
    return level;
}

概率 p 通常取 0.25 或 0.5。p 越大，节点层高越高，索引越密集，查找越快，但内存开销也越大。p 取 0.25 时，平均每个节点约 1.33 层，内存开销比较可控。

我的经验：在嵌入式场景下，内存通常比较紧张。我一般取 p=0.25，最大层数设为 16。这样 100 万个节点的跳表，额外内存开销大约在 2-3 MB 左右，完全可以接受。

3.2 查找操作

查找是跳表最核心的操作。从最高层开始，沿着当前层向前走，直到下一个节点的 key 大于等于目标 key，然后下降到下一层继续。重复这个过程，直到到达底层。

int skip_list_search(skip_list_t *list, int key) {
    skip_node_t *cur = list->header;
    
    // 从最高层开始，逐层下降
    for (int i = list->level - 1; i >= 0; i--) {
        while (cur->forward[i] != NULL && cur->forward[i]->key < key) {
            cur = cur->forward[i];
        }
        // 此时 cur 是第 i 层中最后一个小于 key 的节点
    }
    
    // 到达底层，检查下一个节点
    cur = cur->forward[0];
    if (cur != NULL && cur->key == key) {
        return cur->value;
    }
    return -1; // 未找到
}

这个代码看起来简单，但有个细节要注意：list->level 是当前实际最高层数，不是最大允许层数。查找时只遍历实际存在的层，避免空指针访问。

3.3 插入操作

插入比查找多一步：需要记录每一层中「最后一个小于 key 的节点」，也就是插入位置的前驱。然后随机生成新节点的层高，逐层插入。

void skip_list_insert(skip_list_t *list, int key, int value) {
    skip_node_t *update[list->max_level]; // 记录每层的前驱
    skip_node_t *cur = list->header;
    
    // 1. 查找插入位置，记录每层前驱
    for (int i = list->level - 1; i >= 0; i--) {
        while (cur->forward[i] != NULL && cur->forward[i]->key < key) {
            cur = cur->forward[i];
        }
        update[i] = cur;
    }
    
    // 2. 随机生成新节点层高
    int new_level = random_level(list->max_level, list->probability);
    if (new_level > list->level) {
        // 如果新层高超过当前最高层，补充前驱为 header
        for (int i = list->level; i < new_level; i++) {
            update[i] = list->header;
        }
        list->level = new_level;
    }
    
    // 3. 创建新节点并插入
    skip_node_t *new_node = create_node(key, value, new_level);
    for (int i = 0; i < new_level; i++) {
        new_node->forward[i] = update[i]->forward[i];
        update[i]->forward[i] = new_node;
    }
}

这里有个坑：如果新节点的层高比当前最高层还高，需要把超出部分的 update 指针指向 header。我曾经漏掉这一步，结果插入后高层指针乱飞，调试了一整个下午才找到原因。

3.4 删除操作

删除和插入类似，也是先查找并记录前驱，然后逐层删除。删除后如果最高层变空了，记得更新 list->level。

int skip_list_delete(skip_list_t *list, int key) {
    skip_node_t *update[list->max_level];
    skip_node_t *cur = list->header;
    
    for (int i = list->level - 1; i >= 0; i--) {
        while (cur->forward[i] != NULL && cur->forward[i]->key < key) {
            cur = cur->forward[i];
        }
        update[i] = cur;
    }
    
    cur = cur->forward[0];
    if (cur == NULL || cur->key != key) {
        return -1; // 不存在
    }
    
    // 逐层删除
    for (int i = 0; i < list->level; i++) {
        if (update[i]->forward[i] != cur) break;
        update[i]->forward[i] = cur->forward[i];
    }
    
    // 清理空层
    while (list->level > 1 && list->header->forward[list->level - 1] == NULL) {
        list->level--;
    }
    
    free(cur);
    return 0;
}
注意：删除后清理空层这一步很容易被忽略。如果不清理，查找时会在空层上浪费时间，虽然不影响正确性，但会降低性能。我建议每次删除后都检查一下。

四、跳表 vs 平衡树 vs 哈希表

很多同学会问：跳表和红黑树比怎么样？和哈希表比呢？我简单列个对比表：

操作 跳表 红黑树 哈希表
查找 O(log n) 平均 O(log n) O(1) 平均
插入 O(log n) 平均 O(log n) O(1) 平均
删除 O(log n) 平均 O(log n) O(1) 平均
有序遍历 O(n) 天然有序 O(n) 中序遍历 不支持
范围查询 支持，效率高 支持 不支持
实现复杂度 中等 高 低
内存开销 中等（约 1.33 倍） 较高（左右子树指针） 低

跳表最大的优势是「实现简单且性能稳定」。红黑树的旋转操作在嵌入式环境中容易引入不确定性，而跳表没有旋转，只有指针重连，代码量少很多。

哈希表虽然快，但不支持有序遍历和范围查询。如果你需要「查找所有 key 在 [a, b] 之间的元素」，哈希表就无能为力了。跳表可以轻松做到——找到 a 的位置，然后沿着底层链表往后走直到超过 b。

五、跳表的结构图

下面我用 SVG 画一个跳表的结构示意图，帮助大家直观理解。

跳表结构示意图 第0层（完整链表） H 1 3 5 7 9 11 13 15 N 第1层（索引层） H 3 7 11 15 N 第2层（索引层） H 7 15 N 第3层（最高索引） H 15 N 头结点 数据节点 尾结点

从图中可以清楚看到：查找 key=13 时，从第 3 层出发，H → 15（发现 15>13，下降），第 2 层 H → 7 → 15（15>13，下降），第 1 层 7 → 11 → 15（下降），第 0 层 11 → 13，找到！总共只比较了 6 次，而普通链表需要 8 次。层数越高，差距越明显。

六、避坑指南与实战建议

最后分享几个我在实际项目中踩过的坑：

  • 随机数种子要初始化。 嵌入式设备上 rand() 默认种子是 1，如果不调用 srand()，每次重启后跳表结构完全一样。我建议用硬件随机数或 ADC 噪声来初始化种子。
  • 内存碎片问题。 跳表频繁插入删除时，每个节点的大小不同（层高不同），容易产生内存碎片。如果平台支持，可以用内存池来管理节点分配。
  • 最大层数不要设太大。 对于 100 万个节点，log2(1000000) ≈ 20，设 20 层就足够了。设得太大只会浪费内存。
  • 概率 p 的选择。 我做过测试：p=0.5 时查找性能最好，但内存开销翻倍；p=0.25 时性能略差（约 10%），但内存节省 40%。在资源受限的场景下，我倾向于 p=0.25。
一个小技巧：如果你需要频繁的范围查询，可以在跳表底层维护一个双向链表。这样找到起始节点后，可以双向遍历，灵活性更高。代价是每个节点多一个 prev 指针。

跳表是个被低估的数据结构。它没有红黑树那么复杂，性能却毫不逊色。在很多嵌入式场景下，跳表是平衡树的绝佳替代品。嗯，希望今天的分享对你有帮助。

公众号:蓝海资料掘金营，微信deep3321

← 上一章 📖 返回目录 下一章 →