实战：跳表（Skip List）实现——概率数据结构

跳表这东西，我第一次接触是在做内存缓存系统的时候。当时项目里需要一个高性能的有序集合，既要支持快速查找，又要支持范围查询。红黑树当然可以，但实现起来太复杂了，调试起来更是噩梦。后来我翻到了 William Pugh 那篇经典论文，嗯，跳表——简单、高效、还容易实现。

说白了，跳表就是一种「用概率换性能」的数据结构。它通过多层链表来加速查找，每一层都是下一层的「快速通道」。你想想看，如果只有一层链表，查找一个元素得一个个往后走，O(n) 的复杂度，数据量一上来就扛不住了。但如果我们给链表加上「跳跃」的能力，让指针能一次跳过多个节点，那查找速度就能接近二分查找的 O(log n)。

跳表的核心思想

跳表的结构其实很直观。最底层是一个完整的有序链表，上面每一层都是下一层的「子集」。每个节点随机决定自己出现在多少层——这个随机性就是跳表的灵魂。

关键点：跳表通过「空间换时间」的方式，用多层索引来加速查找。每一层都是下一层的快速通道，查找时从最高层开始，快速定位到目标区间，然后逐层下降，最终在底层找到精确位置。

我习惯把跳表想象成地铁线路图。底层是普通线路，每站都停。上层是快线，只停大站。你要从 A 到 Z，先坐快线快速跨越大部分区间，再换乘普通线精确到达目的地。跳表就是这么干的。

跳表的结构设计

每个跳表节点需要存储：

  • 键值对（key-value）
  • 一个指针数组，指向不同层级的后继节点

节点层数的确定方式：

  • 每个节点至少在第 0 层（最底层）出现
  • 每向上提升一层，概率为 p（通常取 0.25 或 0.5）
  • 最大层数通常限制为 MAX_LEVEL，比如 16 或 32

这里有个小坑。我曾经在项目里把 p 设成了 0.75，结果跳表变得「太扁平」，查找性能退化严重。后来我改回 0.25，效果就好多了。p 值越小，高层节点越少，空间开销小但查找步数可能增加；p 值越大，高层节点越多，查找更快但内存占用更大。0.25 是个不错的平衡点。

跳表的三种核心操作

1. 查找（Search）

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

// 查找 key 对应的 value
int* skip_list_find(skip_list* list, int key) {
    // 从最高层开始
    skip_node* current = list->head;
    
    // 逐层下降
    for (int i = list->level - 1; i >= 0; i--) {
        // 在当前层向前移动，直到下一个节点 key 大于等于目标 key
        while (current->next[i] != nullptr && 
               current->next[i]->key < key) {
            current = current->next[i];
        }
    }
    
    // 现在 current 在第 0 层，检查下一个节点
    current = current->next[0];
    if (current != nullptr && current->key == key) {
        return &current->value;
    }
    return nullptr;
}

你想想看，这个查找过程其实很优雅。每次下降一层，搜索范围就缩小一圈。平均时间复杂度 O(log n)，最坏情况 O(n)——但最坏情况出现的概率极低，因为层数是随机决定的。

2. 插入（Insert）

插入操作比查找多了一步：需要记录每一层中「最后一个小于目标 key」的节点，也就是前驱节点。这样在插入新节点时，才能正确更新各层的指针。

void skip_list_insert(skip_list* list, int key, int value) {
    // 记录每一层的前驱节点
    skip_node* prev[MAX_LEVEL];
    skip_node* current = list->head;
    
    // 查找插入位置，同时记录前驱
    for (int i = list->level - 1; i >= 0; i--) {
        while (current->next[i] != nullptr && 
               current->next[i]->key < key) {
            current = current->next[i];
        }
        prev[i] = current;
    }
    
    // 检查 key 是否已存在
    current = current->next[0];
    if (current != nullptr && current->key == key) {
        current->value = value;  // 更新值
        return;
    }
    
    // 随机决定新节点的层数
    int new_level = random_level();
    
    // 如果新层数超过当前最大层数，需要更新 head 的指针
    if (new_level > list->level) {
        for (int i = list->level; i < new_level; i++) {
            prev[i] = list->head;
        }
        list->level = new_level;
    }
    
    // 创建新节点
    skip_node* new_node = create_node(key, value, new_level);
    
    // 插入到各层
    for (int i = 0; i < new_level; i++) {
        new_node->next[i] = prev[i]->next[i];
        prev[i]->next[i] = new_node;
    }
}

个人经验：随机层数的生成函数很关键。我一般用 while (rand() < RAND_MAX * p && level < MAX_LEVEL) level++; 这种方式。注意要保证随机数质量，否则跳表的性能会受影响。我在一个项目里用过简单的线性同余生成器，结果跳表的分布不均匀，查找性能时好时坏。后来换成了梅森旋转算法，问题就解决了。

3. 删除（Delete）

删除操作和插入类似，也需要记录前驱节点。找到目标节点后，更新各层指针，然后释放内存。

bool skip_list_delete(skip_list* list, int key) {
    skip_node* prev[MAX_LEVEL];
    skip_node* current = list->head;
    
    // 查找目标节点，记录前驱
    for (int i = list->level - 1; i >= 0; i--) {
        while (current->next[i] != nullptr && 
               current->next[i]->key < key) {
            current = current->next[i];
        }
        prev[i] = current;
    }
    
    current = current->next[0];
    if (current == nullptr || current->key != key) {
        return false;  // 没找到
    }
    
    // 从各层中移除
    for (int i = 0; i < list->level; i++) {
        if (prev[i]->next[i] != current) {
            break;  // 更高层没有这个节点
        }
        prev[i]->next[i] = current->next[i];
    }
    
    // 释放节点
    delete current;
    
    // 更新最大层数（可选优化）
    while (list->level > 1 && 
           list->head->next[list->level - 1] == nullptr) {
        list->level--;
    }
    
    return true;
}

注意：删除操作后，如果最高层已经没有节点了，记得更新 list->level。否则下次查找时，会从空层开始，白白浪费一次循环。我曾经因为这个疏忽，导致跳表在频繁插入删除后性能下降，排查了半天才发现是 level 没更新。

跳表的性能分析

操作 平均时间复杂度 最坏时间复杂度 空间复杂度
查找 O(log n) O(n) —
插入 O(log n) O(n) O(n log n) 期望
删除 O(log n) O(n) —
范围查询 O(log n + k) O(n) —

注意看，范围查询是跳表的一大优势。找到起始节点后，沿着第 0 层的链表往后走就行，非常自然。红黑树做范围查询就得中序遍历，实现起来麻烦多了。

跳表 vs 红黑树

我经常被问到：「跳表和红黑树哪个好？」我的回答是：看场景。

  • 实现难度：跳表完胜。红黑树的旋转、变色逻辑太复杂了，跳表的代码量大概只有红黑树的三分之一。
  • 并发性能：跳表更适合并发环境。因为跳表的更新只影响局部节点，锁粒度可以很小。红黑树的旋转可能影响整棵树，锁粒度不好控制。
  • 内存占用：红黑树更省内存。每个节点只需要两个指针（左、右），跳表每个节点平均需要 1/(1-p) 个指针，p=0.25 时平均 1.33 个，但最大层数可能到 32，所以实际分配时会有浪费。
  • 性能稳定性：红黑树更稳定，最坏情况也是 O(log n)。跳表依赖随机性，虽然最坏情况概率极低，但理论上存在。

我的建议：如果你在写一个需要快速上线的功能，或者团队里其他人要维护你的代码，选跳表。如果你在做底层基础设施，对性能稳定性要求极高，选红黑树。我在做游戏服务器时用的跳表，因为迭代快、需求变化多；在做数据库引擎时用的红黑树，因为要保证最坏情况下的响应时间。

跳表的完整实现

下面是一个完整的跳表实现，包含了查找、插入、删除和打印功能。代码量不大，但麻雀虽小五脏俱全。

#include <iostream>
#include <cstdlib>
#include <ctime>
#include <cstring>

const int MAX_LEVEL = 16;
const float P = 0.25;

struct skip_node {
    int key;
    int value;
    skip_node** next;
    
    skip_node(int k, int v, int level) 
        : key(k), value(v) {
        next = new skip_node*[level];
        memset(next, 0, sizeof(skip_node*) * level);
    }
    
    ~skip_node() {
        delete[] next;
    }
};

struct skip_list {
    skip_node* head;
    int level;
    
    skip_list() {
        head = new skip_node(INT_MIN, 0, MAX_LEVEL);
        level = 1;
    }
    
    ~skip_list() {
        skip_node* cur = head->next[0];
        while (cur) {
            skip_node* tmp = cur;
            cur = cur->next[0];
            delete tmp;
        }
        delete head;
    }
};

int random_level() {
    int level = 1;
    while ((rand() / (float)RAND_MAX) < P && level < MAX_LEVEL) {
        level++;
    }
    return level;
}

int* find(skip_list* list, int key) {
    skip_node* cur = list->head;
    for (int i = list->level - 1; i >= 0; i--) {
        while (cur->next[i] && cur->next[i]->key < key) {
            cur = cur->next[i];
        }
    }
    cur = cur->next[0];
    if (cur && cur->key == key) {
        return &cur->value;
    }
    return nullptr;
}

void insert(skip_list* list, int key, int value) {
    skip_node* prev[MAX_LEVEL];
    skip_node* cur = list->head;
    
    for (int i = list->level - 1; i >= 0; i--) {
        while (cur->next[i] && cur->next[i]->key < key) {
            cur = cur->next[i];
        }
        prev[i] = cur;
    }
    
    cur = cur->next[0];
    if (cur && cur->key == key) {
        cur->value = value;
        return;
    }
    
    int new_level = random_level();
    if (new_level > list->level) {
        for (int i = list->level; i < new_level; i++) {
            prev[i] = list->head;
        }
        list->level = new_level;
    }
    
    skip_node* new_node = new skip_node(key, value, new_level);
    for (int i = 0; i < new_level; i++) {
        new_node->next[i] = prev[i]->next[i];
        prev[i]->next[i] = new_node;
    }
}

bool remove(skip_list* list, int key) {
    skip_node* prev[MAX_LEVEL];
    skip_node* cur = list->head;
    
    for (int i = list->level - 1; i >= 0; i--) {
        while (cur->next[i] && cur->next[i]->key < key) {
            cur = cur->next[i];
        }
        prev[i] = cur;
    }
    
    cur = cur->next[0];
    if (!cur || cur->key != key) {
        return false;
    }
    
    for (int i = 0; i < list->level; i++) {
        if (prev[i]->next[i] != cur) break;
        prev[i]->next[i] = cur->next[i];
    }
    
    delete cur;
    
    while (list->level > 1 && 
           !list->head->next[list->level - 1]) {
        list->level--;
    }
    
    return true;
}

void print(skip_list* list) {
    for (int i = list->level - 1; i >= 0; i--) {
        std::cout << "Level " << i << ": ";
        skip_node* cur = list->head->next[i];
        while (cur) {
            std::cout << cur->key << " ";
            cur = cur->next[i];
        }
        std::cout << std::endl;
    }
}

跳表的结构示意图

下面这张图展示了跳表的多层结构。你可以看到，高层节点稀疏，底层节点密集。查找时从顶层开始，快速跳过大量元素。

跳表结构示意图 L0 L1 L2 L3 H 10 20 30 40 50 60 10 30 50 10 50 10 查找路径示例：从 L3 开始 → L2 → L1 → L0，快速定位目标元素

实际应用场景

跳表在实际项目中用得挺多的。我整理了几个常见的场景：

  • Redis 的有序集合（ZSET）：Redis 的 ZSET 底层就用到了跳表。为什么不用红黑树？因为 Redis 的作者觉得跳表实现更简单，而且范围查询更方便。
  • 内存缓存系统：需要快速查找和范围查询的场景，比如 LRU 缓存与有序索引的结合。
  • 数据库索引：一些嵌入式数据库（如 LevelDB）的 MemTable 就用跳表来实现。
  • 并发数据结构：跳表的并发版本比红黑树容易实现得多，很多无锁数据结构都基于跳表。

总结一下：跳表是一种用概率换性能的数据结构。它实现简单、性能优秀、并发友好。虽然最坏情况是 O(n)，但实际中几乎不会出现。如果你需要一个有序的键值存储结构，又不想跟红黑树的旋转逻辑死磕，跳表绝对是个好选择。

嗯，跳表的内容就讲到这里。代码我已经贴出来了，你可以直接拿去用。记得调整 MAX_LEVEL 和 P 的值来适配你的场景。如果数据量不大，MAX_LEVEL 设成 8 就够了；如果数据量上亿，建议设到 32 以上。

公众号:蓝海资料掘金营，微信deep3321
← 上一章 📖 返回目录 下一章 →