C++如何实现一个跳表（Skip List）？C++概率数据结构实战【算法】-C++-PHP中文网

C++如何实现一个跳表（Skip List）？C++概率数据结构实战【算法】

冰火之心

发布： 2025-12-13 21:48:07

原创

617人浏览过

跳表是一种概率型多层链表结构，平均查找复杂度O(log n)，通过随机升层维持平衡，支持高效插入、删除与并发操作，C++需手写实现。

c++如何实现一个跳表（skip list）？c++概率数据结构实战【算法】

跳表（Skip List）是一种概率型数据结构，用多层链表实现快速查找，平均时间复杂度为 O(log n)，实现比平衡树简单，且天然支持并发。C++ 标准库没有内置跳表，但可以手写一个轻量、可扩展的版本。

核心设计思路：分层+随机提升

跳表本质是“带索引的有序链表”。底层是完整有序链表（Level 0），上层是稀疏子集（每层节点数约减半），通过随机决定是否“升层”来维持结构平衡——不靠旋转或重平衡，靠概率摊平高度。

关键点：

每个节点包含一个值 + 一组指针（指向各层的后继），层数在插入时随机生成（如抛硬币直到出现反面，层数 = 连续正面次数 + 1）
所有层共享同一套节点（不是复制值），只是不同层的指针视图不同
查找从最高层开始，向右走不动就下一层，类似“先坐快线再换慢车”
删除只需断开各层对应指针，无需调整结构

简易可运行的 C++ 跳表实现（支持插入/查找/删除）

以下是一个精简但完整、带注释的单文件实现（C++17）：

立即学习“C++免费学习笔记（深入）”；

#include <iostream>
#include <vector>
#include <random>
#include <algorithm>
<p>template<typename T>
class SkipList {
private:
struct Node {
T value;
std::vector<Node*> next; // next[i] 指向第 i 层的后继
explicit Node(const T& v, size_t level) : value(v), next(level, nullptr) {}
};</p><pre class='brush:php;toolbar:false;'>Node* head;
size_t max_level;
mutable std::mt19937 rng;

// 抛硬币：返回 [1, max_level] 的随机层数（概率 ~1/2^k）
size_t random_level() const {
    size_t lvl = 1;
    std::uniform_int_distribution<int> dist(0, 1);
    while (dist(rng) == 1 && lvl < max_level) ++lvl;
    return lvl;
}

登录后复制

public: explicit SkipList(size_t max_lvl = 16) : max_level(max_lvl), rng(std::random_device{}()) { head = new Node(T{}, max_level); // 哨兵头节点，值不重要 }

~SkipList() {
    while (head) {
        Node* tmp = head;
        head = head->next[0];
        delete tmp;
    }
}

bool find(const T& key) const {
    Node* x = head;
    for (int i = max_level - 1; i >= 0; --i) {
        while (x->next[i] && x->next[i]->value < key)
            x = x->next[i];
    }
    x = x->next[0];
    return x && x->value == key;
}

void insert(const T& key) {
    std::vector<Node*> update(max_level, head);
    Node* x = head;

    // 记录每层最后一个小于 key 的节点（用于后续链接）
    for (int i = max_level - 1; i >= 0; --i) {
        while (x->next[i] && x->next[i]->value < key)
            x = x->next[i];
        update[i] = x;
    }

    size_t lvl = random_level();
    Node* newNode = new Node(key, lvl);

    // 将新节点插入到各层
    for (size_t i = 0; i < lvl; ++i) {
        newNode->next[i] = update[i]->next[i];
        update[i]->next[i] = newNode;
    }
}

bool erase(const T& key) {
    std::vector<Node*> update(max_level, nullptr);
    Node* x = head;

    for (int i = max_level - 1; i >= 0; --i) {
        while (x->next[i] && x->next[i]->value < key)
            x = x->next[i];
        update[i] = x;
    }

    x = x->next[0];
    if (!x || x->value != key) return false;

    for (size_t i = 0; i < x->next.size(); ++i) {
        update[i]->next[i] = x->next[i];
    }
    delete x;
    return true;
}

登录后复制

};

Figma

Figma 是一款基于云端的 UI 设计工具，可以在线进行产品原型、设计、评审、交付等工作。

1371

查看详情

使用示例与注意事项

你可以这样测试：

int main() {
    SkipList<int> sl;
    sl.insert(3); sl.insert(6); sl.insert(7);
    sl.insert(9); sl.insert(12); sl.insert(19);
<pre class='brush:php;toolbar:false;'>std::cout << sl.find(7) << "\n"; // 1
std::cout << sl.find(5) << "\n"; // 0
sl.erase(6);
std::cout << sl.find(6) << "\n"; // 0

登录后复制

}

注意点：

max_level 默认设为 16：对亿级数据也足够（2¹⁶ ≈ 65536，理论最大高度极小概率超限）
随机种子用 std::random_device，避免重复序列；生产环境可考虑线程局部 rng
未实现迭代器或范围 for，如需遍历，可从 head→next[0] 链顺序访问 Level 0
内存安全：析构函数递归释放，但实际中建议用智能指针或内存池优化频繁增删

进阶方向：并发跳表 / 持久化 / 泛型增强

真实系统中（如 Redis 的 ZSET、LevelDB 的 memtable）跳表常被改造：

无锁并发插入：各层原子 compare-and-swap 更新 next 指针，配合标记删除（如 Java ConcurrentSkipListMap）
支持重复键：修改比较逻辑，或让 Node 存 vector 或计数器
自适应层数：根据当前 size 动态调整 max_level，避免空间浪费
序列化支持：重载 operator

基本上就这些。跳表不复杂但容易忽略概率建模和边界指针管理——写一遍，比背红黑树规则直观得多。

以上就是C++如何实现一个跳表（Skip List）？C++概率数据结构实战【算法】的详细内容，更多请关注php中文网其它相关文章！