跳表是一种概率型多层链表结构，平均查找复杂度O(log n)，通过随机升层维持平衡，支持高效插入、删除与并发操作，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;
}};
使用示例与注意事项
你可以这样测试：
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<T> 或计数器
- 自适应层数：根据当前 size 动态调整 max_level，避免空间浪费
- 序列化支持：重载 operator<< / 可选 JSON/Binary 输出，方便调试或快照
基本上就这些。跳表不复杂但容易忽略概率建模和边界指针管理——写一遍，比背红黑树规则直观得多。
