跳表是多层有序单链表，平均O(log n)时间完成增删查，通过随机提升实现层级结构；搜索从最高层开始逐层下降，用update数组记录前驱节点；节点含key、value和多层next指针数组。
跳表（Skip List）是一种概率性数据结构，能在平均 O(log n) 时间内支持插入、删除和搜索操作，实现比平衡树简单，且天然支持并发。Java 标准库没有直接提供跳表，但可通过自定义实现一个线程不安全但高效的基础版本。
核心思想：多层链表 + 随机提升
跳表本质是多级有序单链表。底层（level 0）包含全部元素；上层是下层的“快进子集”，每个节点以固定概率（如 1/2）向上提升一层。搜索时从最高层开始，沿当前层向右跳过比目标小的节点，遇到大于目标的节点就下降一层，直到 level 0 找到或确认不存在。
- 层级高度用随机数决定，常见策略：抛硬币直到首次出现反面，层数 = 抛掷次数（至少为 1）
- 每层都是严格递增的单向链表，节点持有指向同层下一个节点的引用
- 头节点（dummy head）在每一层都存在，值设为最小（如 Integer.MIN_VALUE），不参与实际比较
节点设计：支持多层指针
每个节点需保存 key、value 和一个指针数组，长度等于其所在最大层级。例如：
<font size="2">static class Node {
final int key;
String value;
Node[] next; // next[i] 表示第 i 层的后继节点
Node(int key, String value, int level) {
this.key = key;
this.value = value;
this.next = new Node[level];
}
}</font>
注意：next 数组按 level 0 到 level max 编号，next[0] 是最底层后继，next[level-1] 是最高层后继。
立即学习“Java免费学习笔记（深入）”；
搜索逻辑：从顶层逐层下降
查找 key 时，从最高层 head 开始，向右扫描直到 next 节点 key ≥ target，然后降一层继续，最终在 level 0 判断是否命中：
- 维护一个数组
update[]记录每层最后一个小于 target 的节点（用于后续插入/删除） - 从最高层（currentLevel）往 level 0 遍历，每层内部 while 循环推进
- 找到 level 0 的前驱节点后，检查其 next[0] 是否存在且 key 相等
示例搜索片段：
<font size="2">Node current = head;
for (int i = currentLevel; i >= 0; i--) {
while (current.next[i] != null && current.next[i].key < key) {
current = current.next[i];
}
update[i] = current; // 记录该层落点
}
Node candidate = current.next[0];
return candidate != null && candidate.key == key ? candidate.value : null;</font>
插入与删除：复用搜索路径
插入前先执行搜索，得到每层的插入位置（即 update[i]）。再生成新节点，随机决定层数（不超过当前最大层+1），然后逐层链接：
- 对每一层 i（0 到 newLevel-1），设置 new_node.next[i] = update[i].next[i]，再令 update[i].next[i] = new_node
- 若 newLevel > currentLevel，需补高 head 的 next 指针，并更新 currentLevel
- 删除类似：先搜索定位，再逐层断开链接；若某层无节点了，可降低 currentLevel（非必须，但节省空间）
关键细节：所有修改只影响局部指针，无需全局调整，这是跳表简洁性的体现。
