跳表通过在有序链表上构建多层随机索引，将平均查找时间从O(n)降至O(log n)；其核心是“空间换时间”的分层跳转机制，插入时用抛硬币法随机决定层数，所有操作均从最高层开始逐层定位，实现简洁高效。
跳表（Skip List）通过在有序链表基础上构建多层索引，把平均查找时间从 O(n) 降到 O(log n)，实现方式不依赖平衡树的复杂调整，而是靠概率化分层和简单指针操作。
核心思想：用空间换时间的多级索引
跳表本质是带“快进通道”的链表。底层是原始有序链表（Level 0），上面若干层是它的稀疏子集——每层节点以一定概率（通常是 1/2）向上提升一层，形成阶梯状索引结构。查找时从最高层开始，沿该层向右跳过无关节点，一旦发现下一个值大于目标，就下降一层继续找。
- 每一层都是一个有序单向链表，且高层节点必然出现在低层中
- 最高层节点最少，提供粗粒度跳跃；最低层包含全部元素，保证精确命中
- 插入时随机决定新节点层数，避免人为维护层级平衡
关键操作：查找、插入、删除的逻辑要点
所有操作都从最高层开始，逐层向下推进，用一个数组（或栈）记录每层最后访问的节点，方便后续插入/删除时快速定位前驱。
- 查找：从头节点最高层出发，向右走直到下一节点值 ≥ target，再降一层；重复直到 Level 0，最后检查是否相等
- 插入：先按查找路径记录各层插入位置；再生成随机层数（如抛硬币直到首次出现反面，层数 = 抛掷次数）；为新节点创建对应层数的指针，并更新每层前驱的指针
- 删除：同样沿查找路径定位目标节点，在每一层中将其从链表摘除（需确保该节点在当前层存在）
层数设计与随机化实现技巧
层数上限通常设为 log₂(n)+1（n 是当前节点数），但实际实现常设固定上限（如 32 层），避免极端情况导致内存浪费。随机层数生成推荐用“抛硬币法”：
- 初始化 level = 1
- 循环执行：以 50% 概率 level++，直到失败或达到最大层数
- 这样期望层数为 2，实际分布符合几何分布，能自然保证索引密度递减
为什么比平衡树更易实现又足够高效
跳表没有旋转、染色、分裂合并等复杂逻辑，所有操作仅涉及指针修改和简单循环；并发场景下还可配合无锁编程优化（如论文《Lock-Free Skip Lists》）。实测在百万级数据下，其查找性能接近红黑树，而代码量不到后者的 1/3。
它不是理论最优，但在工程实践中做到了简洁性、可读性与性能的良好折中。
