引言在现代软件开发中有序集合的高效操作是许多系统的核心需求。无论是缓存系统的过期管理、排行榜的实时更新还是数据库的索引结构都需要一种能够支持快速查找、插入和删除的数据结构。平衡二叉搜索树如红黑树、AVL树是常见的选择但其复杂的旋转和重平衡逻辑令很多开发者望而却步。而今天的主角——跳表SkipList却以一种非常巧妙且易于实现的方式达到了与平衡树不相上下的性能表现。它不仅成为了Redis有序集合的底层实现之一也在LevelDB、HBase等存储系统的MemTable中发挥着关键作用。本文将带你从零开始深入理解跳表的设计哲学掌握其核心原理并最终实现一个完整、可运行的跳表。所有代码均经过测试你可以直接复制到IDE中运行。一、核心概念用空间换时间的层叠式链表1.1 为什么需要跳表想象你有一本只有下一页没有目录的字典查找一个单词只能一页一页翻——这就像普通链表查询复杂度O(n)。为了提高效率我们可以在字典前加一个简略索引比如“A开头的在第10页B开头的在第50页……”这样就能快速定位区间。多级索引能进一步加速这正是跳表的思想。跳表本质上是一个多层有序链表。最底层第0层包含所有元素每一层都是下层元素的稀疏索引节点会以一定概率向上层“晋升”。查找时从最高层开始沿当前层向右直到碰到大于目标值的节点然后下降一层继续直到最底层找到目标或确认不存在。这种结构使复杂度降至平均O(log n)最坏情况可能退化到O(n)但通过合理的随机层高生成算法可以保证退化概率极低。1.2 节点结构一个跳表节点需要存储-值value可比较的键用来排序。-前进指针数组forward[]数组下标表示层级forward[i]指向该节点在第i层的下一个节点。层级从0开始计数节点最高层下标为maxLevel - 1。头节点不存实际数据只作为入口标记其前进指针数组长度等于跳表的最大允许层数。class SkipListNodeT extends ComparableT { T value; SkipListNodeT[] forward; // 前进指针数组 SuppressWarnings(unchecked) SkipListNode(T value, int level) { this.value value; this.forward new SkipListNode[level 1]; // level是最大索引数组长度为 level1 } }1.3 随机层高的生成关键在于如何决定一个节点能到第几层。通常采用类似抛硬币的方式从第0层开始每次以概率p常取0.5或0.25决定是否提升一层直到失败或达到最大层级。这种随机化保证指数级递减的节点分布从而维持O(log n)期望性能。private int randomLevel() { int level 0; while (Math.random() PROBABILITY level MAX_LEVEL - 1) { level; } return level; }PROBABILITY通常取0.5表示约一半节点在L11/4在L21/8在L3……符合几何分布。MAX_LEVEL建议设为log_ (1/PROBABILITY) (预期最大元素数)例如当PROBABILITY0.5且预期存2^16个元素时MAX_LEVEL可设为16。二、实战手写一个完整跳表以下代码实现了一个泛型跳表支持插入、查找、删除并包含节点的更新层级处理。我们使用Integer作为示例键你可以替换为任何可比较类型。public class SkipListT extends ComparableT { private static final double PROBABILITY 0.5; // 晋升概率 private static final int MAX_LEVEL 16; // 最大层数 private SkipListNodeT head; // 头节点 private int currentMaxLevel; // 当前实际最大层级 private int size; // 元素数量 public SkipList() { this.head new SkipListNode(null, MAX_LEVEL - 1); // 头节点最高层级 this.currentMaxLevel 0; this.size 0; } // 生成随机层级 private int randomLevel() { int level 0; while (Math.random() PROBABILITY level MAX_LEVEL - 1) { level; } return level; } // 查找节点返回每一层的前驱节点更新数组 private SkipListNodeT[] findPredecessors(T value) { SuppressWarnings(unchecked) SkipListNodeT[] update new SkipListNode[MAX_LEVEL]; SkipListNodeT curr head; // 从最高层开始搜索 for (int i currentMaxLevel; i 0; i--) { while (curr.forward[i] ! null curr.forward[i].value.compareTo(value) 0) { curr curr.forward[i]; } update[i] curr; // 记录该层最后一个小于value的节点 } return update; } // 查找指定值是否存在 public boolean search(T value) { SkipListNodeT node findPredecessors(value)[0].forward[0]; return node ! null node.value.compareTo(value) 0; } // 插入值如果已存在则不做任何操作或可选择更新 public void insert(T value) { SkipListNodeT[] update findPredecessors(value); SkipListNodeT node update[0].forward[0]; // 如果值已存在直接返回实际场景可考虑覆盖 if (node ! null node.value.compareTo(value) 0) { return; } int newLevel randomLevel(); // 如果新节点层级超过当前最大层则需要更新头节点中更高层的指针 if (newLevel currentMaxLevel) { for (int i currentMaxLevel 1; i newLevel; i) { update[i] head; } currentMaxLevel newLevel; } // 创建新节点 SkipListNodeT newNode new SkipListNode(value, newLevel); // 插入节点对于每一层将新节点插入到update[i]之后 for (int i 0; i newLevel; i) { newNode.forward[i] update[i].forward[i]; update[i].forward[i] newNode; } size; } // 删除指定值返回是否成功 public boolean delete(T value) { SkipListNodeT[] update findPredecessors(value); SkipListNodeT node update[0].forward[0]; // 未找到要删除的节点 if (node null || node.value.compareTo(value) ! 0) { return false; } // 从底层到节点最高层逐层移除引用 int nodeLevel node.forward.length - 1; for (int i 0; i nodeLevel; i) { if (update[i].forward[i] ! null update[i].forward[i].value.compareTo(value) 0) { update[i].forward[i] node.forward[i]; } } // 更新currentMaxLevel如果删除的节点是最高层的唯一节点 while (currentMaxLevel 0 head.forward[currentMaxLevel] null) { currentMaxLevel--; } size--; return true; } // 打印跳表结构用于调试 public void printStructure() { System.out.println(SkipList (size size , maxLevel (currentMaxLevel 1) )); for (int i currentMaxLevel; i 0; i--) { System.out.print(Level i : head - ); SkipListNodeT curr head.forward[i]; while (curr ! null) { System.out.print(curr.value - ); curr curr.forward[i]; } System.out.println(null); } } // 元素个数 public int size() { return size; } // 内部节点类 static class SkipListNodeT extends ComparableT { T value; SkipListNodeT[] forward; SuppressWarnings(unchecked) SkipListNode(T value, int level) { this.value value; this.forward new SkipListNode[level 1]; } } // 测试主函数 public static void main(String[] args) { SkipListInteger list new SkipList(); int[] testData {3, 6, 7, 9, 12, 19, 17, 26, 21, 25}; // 插入测试 for (int num : testData) { list.insert(num); } list.printStructure(); // 查找测试 System.out.println(查找 19: list.search(19)); // true System.out.println(查找 15: list.search(15)); // false // 删除测试 list.delete(19); list.delete(3); System.out.println(删除 19 和 3 后:); list.printStructure(); } }2.1 核心操作解析插入1. 通过findPredecessors获取每层最后一个小于target的节点数组。2. 若节点已存在直接返回也可实现值覆盖。3. 生成随机层高newLevel并若超过当前最大层补齐头节点在该层的指针。4. 在各层执行标准链表插入。查找查找过程与插入的前驱查找类似最终检查第0层的下一个节点是否为目标值。删除同样获取前驱数组确认节点存在后从第0层到节点的最高层逐一修改前驱指针跳过待删节点。随后维护currentMaxLevel。三、常见问题与注意事项3.1 并发问题上述实现是线程不安全的。在实际并发场景如Redis中跳表常配合锁或无锁CAS操作。Java中可使用ConcurrentSkipListMap其内部采用无锁跳表但实现复杂度远高于本示例。3.2 概率因子的选择PROBABILITY设置直接决定空间时间权衡- 取0.5时空间开销约增加100%每个节点平均1.5个指针查询效率很高。- 取0.25时空间节约层数更低适合元素数量极大且内存敏感的场景。Redis中skipList采用p0.25。3.3 最大层数最大层数过小会导致大量节点集中在高层查找退化过大则浪费空间。经验公式MAX_LEVEL ceil(log_ (1/p) N)如预期存储100万个元素p0.5时log₂ 1000000 ≈ 20。3.4 删除后currentMaxLevel维护必须检查高层是否已无节点否则会导致search时因高层指向null而提前终止影响性能。正确做法是在删除后从currentMaxLevel向下遍历直至发现非空层。3.5 值重复处理示例中插入重复值会忽略。若需要支持重复键可修改为节点存储值列表或采用更复杂的版本号机制。四、性能分析与应用场景跳表的平均时间复杂度为查找O(log n)插入O(log n)删除O(log n)空间复杂度O(n)。相比红黑树其优点在于实现简单、易于调试、支持高效的范围查询只需在最底层沿链表扫描。缺点在于额外空间开销和随机性导致的非严格稳定但概率上足够可靠。典型应用- Redis有序集合当元素较少或元素较大时使用跳表。- LevelDB/RocksDB内存表MemTable使用跳表保证有序写然后批量刷盘。- 京东HotKey探测使用跳表维护请求频率的有序排名。- 通用高性能有序map。总结跳表通过多层索引将普通链表的线性查找优化为对数级同时保留了链表易于实现和范围查询的优点。本文从零实现了完整的插入、查找、删除逻辑并详细讨论了随机层高生成、概率选择等关键细节。建议读者实际运行代码观察跳表结构变化加深理解。在此基础上你可以进一步探索无锁并发跳表的实现或将其改造为支持范围查询和排名操作的高级集合。跳表教会我们一个朴素却强大的工程哲学用可控的随机性换取实现简洁与性能平衡这一思想同样适用于布隆过滤器、HyperLogLog等众多经典数据结构。