跳表(Skip List)

作者： /

什么是跳表

跳表（Skip List）是一种概率性的有序数据结构，通过给有序链表叠加多层索引，把查找、插入、删除的平均复杂度从 O(n) 降到 O(log n)。它以少量空间为代价换取接近平衡树的性能，但实现比红黑树简单得多——没有旋转、没有颜色标记，代码量通常只有平衡树的一半。

原理：从有序链表到多层索引

一个 10 个节点的有序链表 1→2→…→10，查找元素 9 要遍历 9 次。如果每隔一个节点建一条”快速通道”（一级索引 1→3→5→7→10），查找路径变为 1→3→5→7→9，只需 5 次比较；再叠一层二级索引（1→5→10），路径进一步缩短。层数越多，跳过的节点越多，这就是跳表的直觉来源。

时间复杂度分析

设晋升概率为 p，每层期望节点数是上一层的 p 倍。高度约为 log1/pn，每层期望步数 1/p，因此查找总复杂度 O(log n)。工程上常取 p = 0.25 或 0.5 来平衡高度与内存。

与平衡树的对比

  • 实现简单，无需旋转等自平衡操作；
  • 天然支持范围查询（从某节点往后遍历）；
  • 更容易做并发改造（无锁跳表是 Redis 的经典方案）；
  • 代价是随机性——最坏复杂度 O(n)，但实际中几乎不可能出现。

Golang 实现

数据结构

const (
    maxLevel = 32    // 最大层数
    p        = 0.25  // 层数晋升概率
)

type SkipNode struct {
    key     int
    value   interface{}
    forward []*SkipNode // 每层的前进指针
}

type SkipList struct {
    head   *SkipNode
    level  int
    length int
    rand   *rand.Rand
}

func NewSkipList() *SkipList {
    return &SkipList{
        head:  &SkipNode{forward: make([]*SkipNode, maxLevel)},
        level: 1,
        rand:  rand.New(rand.NewSource(time.Now().UnixNano())),
    }
}

func (sl *SkipList) randomLevel() int {
    level := 1
    for level < maxLevel && sl.rand.Float64() < p {
        level++
    }
    return level
}

查找

func (sl *SkipList) Search(key int) (interface{}, bool) {
    cur := sl.head
    for i := sl.level - 1; i >= 0; i-- {
        for cur.forward[i] != nil && cur.forward[i].key < key {
            cur = cur.forward[i]
        }
    }
    cur = cur.forward[0]
    if cur != nil && cur.key == key {
        return cur.value, true
    }
    return nil, false
}

插入

func (sl *SkipList) Insert(key int, value interface{}) {
    update := make([]*SkipNode, maxLevel)
    cur := sl.head
    // 记录每一层最后小于 key 的节点
    for i := sl.level - 1; i >= 0; i-- {
        for cur.forward[i] != nil && cur.forward[i].key < key {
            cur = cur.forward[i]
        }
        update[i] = cur
    }

    level := sl.randomLevel()
    if level > sl.level {
        for i := sl.level; i < level; i++ {
            update[i] = sl.head
        }
        sl.level = level
    }

    node := &SkipNode{key: key, value: value, forward: make([]*SkipNode, level)}
    for i := 0; i < level; i++ {
        node.forward[i] = update[i].forward[i]
        update[i].forward[i] = node
    }
    sl.length++
}

删除

func (sl *SkipList) Delete(key int) bool {
    update := make([]*SkipNode, maxLevel)
    cur := sl.head
    for i := sl.level - 1; i >= 0; i-- {
        for cur.forward[i] != nil && cur.forward[i].key < key {
            cur = cur.forward[i]
        }
        update[i] = cur
    }

    target := cur.forward[0]
    if target == nil || target.key != key {
        return false
    }
    for i := 0; i < sl.level; i++ {
        if update[i].forward[i] != target {
            break
        }
        update[i].forward[i] = target.forward[i]
    }
    // 收缩空层
    for sl.level > 1 && sl.head.forward[sl.level-1] == nil {
        sl.level--
    }
    sl.length--
    return true
}

性能优化技巧

  • 随机层数生成：用预计算概率表代替每次循环取随机数，减少 rand 调用；
  • 内存预分配：节点 forward 切片按最大层数一次性分配，减少 GC 压力；
  • 缓存友好：把高频访问的字段放在结构体前面；
  • 无锁并发：用原子操作（CAS）实现无锁版本，如 ConcurrentSkipListMap；
  • 层数上限：maxLevel 设 32 左右，过高只会浪费内存。

开源实现参考

  • github.com/throne-developer/skiplist：Redis 风格，支持重复 score + 唯一 member、ZRangeByScore 等范围查询、GetRank 排名操作；
  • github.com/liyue201/gostl：基于 Go 泛型，类型安全，概率表优化 + 内存预分配，支持迭代器；
  • github.com/roseduan/rosedb：内嵌数据库中的跳表，支持字节切片 key 与高效区间扫描。

应用场景

  • Redis 有序集合（ZSET）：底层就是跳表 + 哈希表；
  • LevelDB / RocksDB：内存表（MemTable）用跳表组织有序数据；
  • 排名系统：游戏排行榜、热搜榜；
  • 范围查询：需要高效区间扫描的有序存储场景。

总结

跳表用”多层索引 + 随机化”换来 O(log n) 的平均复杂度，实现简单、支持范围查询、并发友好，是平衡树之外同样值得选的有序数据结构。配合 Go 1.18+ 的泛型，还能写出类型安全的通用版本。

滚动至顶部