一、跳表是什么跳表Skip List是一种支持快速查找、插入和删除的有序数据结构。它的底层仍然是链表但额外建立了多层“索引链表”让查找时可以跳过大量节点。可以把它理解成普通链表逐个节点寻找跳表先大步跳跃接近目标后再小步查找思想类似二分查找但更适合动态插入和删除二、为什么普通链表查找很慢假设有一个有序链表1 → 3 → 5 → 7 → 9 → 11 → 13 → 15查找13时只能从头开始逐个比较1 → 3 → 5 → 7 → 9 → 11 → 13时间复杂度是O(n)数组可以使用二分查找达到O(log n)但数组中间插入或删除元素通常需要移动大量数据复杂度为O(n)。跳表希望同时获得查找O(log n) 插入O(log n) 删除O(log n)这些是期望时间复杂度。三、跳表的基本结构在原始链表上建立多级索引Level 3: HEAD ----------------------→ 13 Level 2: HEAD --------→ 7 ----------→ 13 Level 1: HEAD → 3 ----→ 7 → 9 -----→ 13 Level 0: HEAD → 1 → 3 → 5 → 7 → 9 → 11 → 13 → 15其中Level 0保存全部节点越高层的节点越少高层用于快速定位底层用于找到精确位置每个节点可能同时存在于多层中例如节点7的逻辑结构可能是7.forward[0] → Level 0 的下一个节点 7.forward[1] → Level 1 的下一个节点 7.forward[2] → Level 2 的下一个节点实际上它通常是一个节点持有多个前向指针并不是复制出多个节点。四、查找过程以上面的跳表为例查找11。第一步从最高层开始HEAD → 13因为13 11不能前进于是下降一层。第二步在较低层前进HEAD → 77 11移动到7。下一个节点是13超过目标于是再次下降。第三步继续逼近目标在 Level 17 → 99 11移动到9。下一步会超过目标所以继续下降。第四步在底层精确查找9 → 11找到目标。核心规则是如果右侧节点小于目标向右移动 如果右侧节点大于等于目标下降一层伪代码current head 从最高层向下遍历: while current.forward[level] ! null and current.forward[level].value target: current current.forward[level] current current.forward[0] 如果 current.value target: 返回 current 否则: 返回不存在这个过程很像在二维结构中不断“向右、向下”移动。五、插入过程假设要插入8。5.1 找到每一层的前驱节点查找插入位置时记录每一层最后一个小于8的节点update[2] 7 update[1] 7 update[0] 7update数组表示新节点在每一层应该插到哪个节点后面5.2 随机生成节点高度跳表通常通过随机算法决定新节点拥有多少层以概率p 1/2为例level 0 只要抛硬币成功: level 1可能产生50% 的节点只有 Level 0 25% 的节点拥有 Level 01 12.5% 的节点拥有 Level 02 6.25% 的节点拥有 Level 03因此层数越高节点越少。5.3 修改指针假设8被随机为两层节点new.forward[0] update[0].forward[0] update[0].forward[0] new new.forward[1] update[1].forward[1] update[1].forward[1] new插入后Level 1: ... → 7 → 8 → 9 ... Level 0: ... → 7 → 8 → 9 ...重要的是寻找插入位置需要O(log n)修改指针本身只需要O(level)六、删除过程删除节点时同样先找到目标节点在每一层的前驱update[level]然后逐层检查如果 update[level].forward[level] 是目标节点: update[level].forward[level] target.forward[level]例如删除前7 → 8 → 9 删除后7 ─────→ 9如果删除后最高层已经没有任何数据节点可以降低跳表当前的最大层数。七、为什么随机层数能提高效率如果人为固定每隔两个节点建立一层索引Level 2: 1 -------→ 9 Level 1: 1 → 5 ---→ 9 → 13 Level 0: 1 → 3 → 5 → 7 → 9 → 11 → 13查找很快但插入节点后可能需要重新调整大量索引。跳表不维护严格的索引间隔而是随机决定节点高度。虽然局部结构不完全均匀但从概率上看第 0 层约有 n 个节点 第 1 层约有 n × p 个节点 第 2 层约有 n × p² 个节点 第 k 层约有 n × pᵏ 个节点当p 1/2时n, n/2, n/4, n/8, ...这与二分查找不断缩小范围的效果类似所以期望查找复杂度为O(log n)八、时间和空间复杂度操作平均/期望复杂度最坏复杂度查找O(log n)O(n)插入O(log n)O(n)删除O(log n)O(n)范围查询O(log n k)O(n)空间O(n)与最大层数设置有关这里k是范围查询返回的元素数量最坏情况可能是所有节点都只有最底层跳表退化成普通链表。不过在合理随机化和最大层数限制下这种情况概率很低当p 1/2时每个节点的期望指针数量为1 1/2 1/4 1/8 ... 2所以总空间仍然是O(n)。九、跳表和其他结构的对比数据结构查找插入/删除有序遍历特点有序数组O(log n)O(n)容易缓存友好普通链表O(n)找到位置后O(1)容易查找慢哈希表平均O(1)平均O(1)不支持适合精确查询平衡树O(log n)O(log n)支持保证最坏复杂度跳表期望O(log n)期望O(log n)支持实现简单、并发友好相比哈希表跳表支持查找大于等于 x 的第一个元素 查询 [left, right] 范围内的元素 按顺序遍历普通哈希表通常不能高效完成这些操作。相比平衡树跳表的优点不需要旋转操作插入、删除逻辑相对直观范围遍历自然某些并发场景更容易设计平衡树的优点最坏时间复杂度有严格的O(log n)保证通常不依赖随机数每个节点的结构更加固定
