跳表（Skip List）
一句话说明
跳表本质上是“给有序链表加多层索引”，用随机化换来接近平衡树的查找效率。
先别背定义，先看它解决什么问题
有序链表的问题是：
- 插入删除很方便
- 但查找太慢，要从头一路走到尾
跳表的思路很直接：
- 底层仍然是有序链表
- 上面额外挂几层“快速通道”
- 查找时先在高层快速跳，再逐层下落
你可以把它想成“链表版的多级索引”。
核心直觉
Level 2: 1 ------------ 9 ---------------- 21
Level 1: 1 ---- 5 ---- 9 ---- 15 --------- 21
Level 0: 1 -> 3 -> 5 -> 7 -> 9 -> 15 -> 21找 15 时，不需要从 1 一个个走过去：
- 先在高层尽量往右跳
- 一旦再跳就会超过目标，就往下一层
- 重复直到最底层
这就是跳表查询能接近 O(log n) 的原因。
为什么它不需要像 AVL / 红黑树那样旋转
因为跳表不是靠严格结构约束维持平衡，而是靠随机层高。
每次插入一个元素时：
- 先决定它出现在哪几层
- 这个层数通常由随机函数生成
只要随机分布足够均匀，整体高度和查询复杂度的期望值就会比较稳定。
Go 代码：基础结构
const (
maxLevel = 16
pFactor = 0.5
)
type skipNode struct {
val int
next []*skipNode
}
type SkipList struct {
head *skipNode
level int
}
func NewSkipList() *SkipList {
return &SkipList{
head: &skipNode{next: make([]*skipNode, maxLevel)},
level: 1,
}
}Go 代码：随机层高
func randomLevel() int {
level := 1
for level < maxLevel && rand.Float64() < pFactor {
level++
}
return level
}层高越高，节点越少。
这就形成了“上层稀疏、下层稠密”的索引结构。
Go 代码：查找
func (sl *SkipList) Search(target int) bool {
cur := sl.head
for i := sl.level - 1; i >= 0; i-- {
for cur.next[i] != nil && cur.next[i].val < target {
cur = cur.next[i]
}
}
cur = cur.next[0]
return cur != nil && cur.val == target
}这段代码就是跳表的灵魂：
- 从最高层往下扫
- 每层都尽量向右跳
Go 代码：插入
func (sl *SkipList) Add(num int) {
update := make([]*skipNode, maxLevel)
cur := sl.head
for i := sl.level - 1; i >= 0; i-- {
for cur.next[i] != nil && cur.next[i].val < num {
cur = cur.next[i]
}
update[i] = cur
}
if cur.next[0] != nil && cur.next[0].val == num {
return
}
newLevel := randomLevel()
if newLevel > sl.level {
for i := sl.level; i < newLevel; i++ {
update[i] = sl.head
}
sl.level = newLevel
}
node := &skipNode{
val: num,
next: make([]*skipNode, newLevel),
}
for i := 0; i < newLevel; i++ {
node.next[i] = update[i].next[i]
update[i].next[i] = node
}
}update 数组在干什么
它记录的是：
- 每一层中，插入位置前面的那个节点是谁
这样我们就能在所有相关层里一次性把新节点接进去。
Go 代码：删除
func (sl *SkipList) Erase(num int) bool {
update := make([]*skipNode, maxLevel)
cur := sl.head
for i := sl.level - 1; i >= 0; i-- {
for cur.next[i] != nil && cur.next[i].val < num {
cur = cur.next[i]
}
update[i] = cur
}
target := cur.next[0]
if target == nil || target.val != num {
return false
}
for i := 0; i < sl.level; i++ {
if update[i].next[i] != target {
break
}
update[i].next[i] = target.next[i]
}
for sl.level > 1 && sl.head.next[sl.level-1] == nil {
sl.level--
}
return true
}跳表和平衡树怎么选
跳表的优势
- 实现逻辑通常更直观
- 不需要维护复杂旋转
- 对并发场景更友好
- 支持有序遍历和范围查询
平衡树的优势
- 最坏复杂度有更强保证
- 工程标准库支持更成熟
- 理论结构更严谨
所以跳表和 红黑树 / 平衡二叉树 的关系，不是谁绝对更强，而是“随机化方案 vs 严格平衡方案”。
为什么 Redis 会喜欢跳表
因为它特别适合这类需求：
- 有序集合
- 范围查询
- 按分数排序
- 插入删除频繁
相比硬写一棵复杂平衡树，跳表实现和维护成本更低。
复杂度
| 操作 | 期望复杂度 | 最坏复杂度 |
|---|---|---|
| 查找 | O(log n) | O(n) |
| 插入 | O(log n) | O(n) |
| 删除 | O(log n) | O(n) |
| 空间 | O(n) | O(n log n) |
这里要注意，“快”是概率意义上的快。
易错点
写跳表时最容易错的地方
- 层数通常从
1开始更直观，但数组下标仍然从0开始。- 插入和删除都要先维护
update数组。- 删除后如果最高层已经空了，要记得回收层数。
- 跳表的复杂度保证是期望值，不是严格最坏值。
经典题目
- 设计跳表 - LeetCode 1206
- 支持范围查询的跳表
- 支持排名统计的跳表
- Redis
zset的底层结构理解