跳表原理#
一句话答案#
跳表是多层有序链表，逐层跳跃实现 O(logn) 查找，比红黑树实现简单且范围查询方便。
核心要点
结构： 多层索引链表，上层是下层的子集，从最高层开始查找
为什么 Redis 用跳表不用红黑树： 1.实现简单 2.范围查询方便(遍历链表) 3.并发友好 4.空间可调
时间： 查找/插入/删除 O(logn)，空间 O(n)
查找期望 O(logn) 的概率推导#
晋升模型： 每个节点以概率 p（常用 1/2）独立晋升到上一层，节点出现在第 i 层的概率为 p^i。
期望层数（树高）： 第 i 层期望节点数 = $n \cdot p^i$，当 $n \cdot p^i < 1$ 即 $i > \log_{1/p} n$ 时该层基本为空，故期望最高层数 $L \approx \log_{1/p} n$ = O(logn)。
每层期望步数（反向分析）： 从查找终点反推路径——在某节点要么「向上爬一层」（概率 p）要么「向左走一步」（概率 1-p）。设爬升 k 层期望步数 C(k)：
解得 $C(k) = k/p$，即每爬一层平均走 1/p 步（p=1/2 时为 2 步）。
合并： 总期望步数 = 层数 × 每层步数 = $\frac{1}{p}\log_{1/p} n$，仍是 O(logn)。
直觉：层数像二分一样砍半（O(logn) 层），每层因为索引稀疏只需常数步（1/p 步）就能跳到下一个下降点，两者相乘仍是对数级。注意这是期望而非最坏——极端随机下所有节点都不晋升会退化成 O(n)，但概率随 n 指数级趋零。
面试回答（2分钟版）
跳表本质是一种多层有序链表，通过逐层建立稀疏索引来实现O(logn)的查找效率。最底层是完整的有序链表包含所有元素，每一层都是下层的子集，查找时从最高层开始，如果当前节点的下一个节点值大于目标就下降一层，否则继续前进，这样每一步都能跳过大量节点。插入时通过随机函数决定新节点的层数，概率通常是1/2或1/4，这保证了各层节点数量的期望分布。Redis的ZSet底层就是用跳表而非红黑树，原因有四个：第一实现简单，链表比树好写好调试好维护；第二范围查询天然支持，找到起点后沿链表遍历即可，而红黑树需要中序遍历；第三并发友好，跳表可以做局部锁而红黑树旋转需要锁更大范围；第四空间可调，通过调整层数概率参数可以灵活权衡时间和空间。时间复杂度查找插入删除都是O(logn)期望，空间复杂度O(n)。
追问与易错
追问方向：
- “跳表的空间复杂度？”→ 期望 O(n)，每个节点平均有约 2 层索引指针（概率 p=0.5 时）；通过调整晋升概率可在时间和空间之间权衡
- “查找为什么期望 O(logn)？”→ 节点以概率 p 逐层晋升，第 i 层期望节点数 $n \cdot p^i$，到 $i > \log_{1/p}n$ 层即空 → 期望层数 O(logn)；反向分析每爬一层平均走 1/p 步（常数），层数×每层步数 = $(1/p)\log_{1/p}n$ = O(logn)。是期望非最坏，最坏退化 O(n) 但概率指数趋零
- “跳表并发怎么处理？”→ 跳表天然适合并发：插入/删除只影响局部节点，可用细粒度锁或 CAS 实现无锁并发；Java ConcurrentSkipListMap 就是基于跳表实现的
- “跳表和平衡树的对比？”→ 跳表实现简单、范围查询方便、并发友好；平衡树（如红黑树）最坏情况有严格保证；Redis 选跳表是因为实现简单且支持范围操作
易错点：
- ❌ 跳表查找一定是 O(logn)——期望值随机性保证
- ❌ 跳表不能范围查询——链表天然支持