跳表是一种概率性多层链表结构，平均查找复杂度O(log n)，通过随机提升和分层索引实现高效操作，比平衡树更易实现。
<p>跳表（Skip List）是一种概率性数据结构，用多层链表实现快速查找，平均时间复杂度为 O(log n)，最坏 O(n)，但实践中非常稳定，且比红黑树、AVL 等平衡树更易实现和调试。c++ 中无需依赖复杂旋转逻辑，只需维护多级前向指针即可。</p> <H3>核心设计思路：分层 + 随机提升</H3> <p>跳表本质是“带索引的有序链表”：底层是完整有序链表（Level 0），上层是稀疏子集（每层节点以约 50% 概率“晋升”到上一层）。查找时从最高层开始向右跳，遇到过大值就下移，最终在底层定位目标。</p> <p>关键点：</p> <ul> <li>每个节点不是固定层数，而是插入时随机决定层数（如用 rand() % 2 == 0 不断提升，直到失败，最大层数可设上限，如 32）</li> <li>所有层共享同一组键值，仅指针结构分层</li> <li>头节点（head）需初始化为 max_level 层，每层 next 指针初始为 nullptr</li> <li>为简化边界处理，可设哨兵尾节点（或用 nullptr 表示结尾）</li> </ul> <H3>节点定义与内存管理</H3> <p>节点需存储 key、value（支持 map 语义）、以及动态长度的 next 指针数组：</p><p><span>立即学习</span>“<a href="https://pan.quark.cn/s/6e7abc4abb9f" style="text-decoration: underline !important; color: blue; font-weight: bolder;" rel="nofollow" target="_blank">C++免费学习笔记（深入）</a>”；</p> <pre class="brush:php;toolbar:false;"><font size="2">struct SkipListnode { int key; std::string value; // 可泛化为 template <typename V> std::vector<SkipListNode*> next; SkipListNode(int k, const std::string& v, int level) : key(k), value(v), next(level, nullptr) {} };</font>不推荐用 raw new/delete 手动管理 —— 可封装在类内用 std::vector 或 std::unique_ptr 统一释放；若追求极致性能，可用内存池（但初版跳表建议先忽略）。
插入与查找的核心逻辑
查找（search）是插入/删除的基础：记录每层最后一个小于 key 的节点（update 数组），用于后续链接修复：
<font size="2">SkipListNode* search(int key) { auto x = head; for (int i = current_level - 1; i >= 0; i--) { while (x->next[i] && x->next[i]->key < key) { x = x->next[i]; } } x = x->next[0]; // 落到 level 0，检查是否命中 return (x && x->key == key) ? x : nullptr; }</font>插入（insert）流程：
- 先执行 search 过程，同时记录每层“前驱节点”到 update[i]
- 生成新节点，层数 random_level()（如：while (rand() & 1 && lvl
- 更新 current_level（若新层数更高）
- 逐层设置新节点 next[i] = update[i]->next[i]，再令 update[i]->next[i] = 新节点
完整可运行精简版（支持 int→string 映射）
<font size="2">#include <iostream> #include <vector> #include <random> #include <algorithm> struct SkipListNode { int key; std::string value; std::vector<SkipListNode*> next; SkipListNode(int k, const std::string& v, int level) : key(k), value(v), next(level, nullptr) {} }; class SkipList { SkipListNode* head; int current_level; const int max_level = 16; std::mt19937 rng{std::random_device{}()}; int random_level() { int lvl = 1; std::bernoulli_distribution d(0.5); while (d(rng) && lvl < max_level) ++lvl; return lvl; } public: SkipList() : current_level(1) { head = new SkipListNode(0, "", max_level); } ~SkipList() { auto x = head; while (x) { auto next = x->next[0]; delete x; x = next; } } void insert(int key, const std::string& value) { std::vector<SkipListNode*> update(max_level, head); auto x = head; for (int i = current_level - 1; i >= 0; i--) { while (x->next[i] && x->next[i]->key < key) x = x->next[i]; update[i] = x; } x = x->next[0]; if (x && x->key == key) { x->value = value; // 更新已存在 key return; } int lvl = random_level(); if (lvl > current_level) { for (int i = current_level; i < lvl; ++i) update[i] = head; current_level = lvl; } x = new SkipListNode(key, value, lvl); for (int i = 0; i < lvl; ++i) { x->next[i] = update[i]->next[i]; update[i]->next[i] = x; } } std::string find(int key) { auto x = head; for (int i = current_level - 1; i >= 0; i--) { while (x->next[i] && x->next[i]->key < key) x = x->next[i]; } x = x->next[0]; return (x && x->key == key) ? x->value : ""; } }; // 使用示例 int main() { SkipList sl; sl.insert(3, "three"); sl.insert(1, "one"); sl.insert(5, "five"); std::cout << sl.find(1) << "n"; // one std::cout << sl.find(4) << "n"; // (empty) }</font>该实现支持重复 key 的覆盖写入，无锁（单线程安全），内存自动释放。如需并发，可在关键路径加 std::shared_mutex（读多写少场景下性能仍优于平衡树锁粒度）。
基本上就这些 —— 跳表不复杂但容易忽略层级同步和内存释放细节，掌握 update 数组和 random_level 就抓住了主干。