跳表（skiplist）是一种性能较好的有序表，查找、插入和删除操作的平均时间复杂度都是 O(log n)。跳表和红黑树功能、性能相当，但实现起来却要简单许多。Redis 的 sorted set 实现中就有跳表的身影。

跳表的思想：

基于链表：插入和删除操作效率高，只需要修改指针指向即可
索引、空间换时间、二分查找：链表查找效率低，因此建立多层索引
随机化，概率分布：每个节点的层数是随机的，每层索引的节点数是随机的，但有着一定的概率分布

跳表优势：

性能好
实现较为简单
支持范围查找

跳表原理

有序链表插入和删除效率高，也支持查找，但查找效率低（O(n)）。

可以通过建立索引，来加速查找过程。如图，将链表的元素视为一层索引，每两个节点提取一个节点构建二层索引，每 4 个节点提取一个节点构建 3 层索引，以此类推，第 i 层索引的节点个数为 n/2^i-1，i >= 1。

在实现上，每个节点含有若干个指针，指向不同层级的下一个节点，我们将带有 k 个指针的节点称为 k 阶节点，一般地，大约有 1/2ⁱ 的节点是 i 阶节点。在这种数据结构中的查找基本上是二分查找。

但是上一张图片里的这种确定节点阶数的方式，导致节点的插入和删除非常麻烦，可能需要调整其他所有节点的阶数。我们可以按照 大约有 1/2ⁱ 的节点是 i 阶节点 的概率分布来随机选择节点的阶数。

随机选择节点的阶数

幂次定律（power law），越大的数出现的概率越小。

NOTE：要定义跳表的最大层数。

const (
    maxLevel = 32
)

func randomLevel() int {
    level := 1
    for rand.Intn(2) == 1 {
        level++
    }
    if level > maxLevel {
        level = maxLevel
    }
    return level
}

节点和跳表定义

NOTE：本文没有考虑存储重复值和插入重复值的情况。

type node struct {
    val int // 节点存储的值
    forwards []*node // 前进指针，指向各层的下一个节点
}

// Skiplist 定义了一个跳表，跳表中不能存储重复值
type Skiplist struct {
    level int // 跳表的层数
    header *node // 跳表的头节点，不存储数据，只存储前进指针
}

初始化跳表

func New() Skiplist {
    return Skiplist {
        level: 0,
        head: &node{
            // 头节点直接初始化为 maxLevel 层，方便后续操作
            forwards: make([]*node, maxLevel),
        },
    }
}

插入

上图表示插入节点 43，蓝色虚线箭头标识需要添加/重新构建的指针。

func (s *Skiplist) Add(num int)  {
    l := randomLevel()
    if l > s.level {
        s.level = l
    }

    n := &node{
        val: num,
        forwards: make([]*node, l),
    }

    x := s.header
    for i := s.level-1; i >= 0; i-- {
        for x.forwards[i] != nil && x.forwards[i].val < num {
            x = x.forwards[i]
        }
        // 需要添加/重新构建指针
        if l-1 >= i {
            n.forwards[i] = x.forwards[i]
            x.forwards[i] = n
        }
    }
}

查找

上图为查找节点 60 的过程，红色箭头标识查找的路径，橙色箭头标识未沿路径前进的一次比较。

func (s *Skiplist) Search(target int) bool {
    x := s.header
    for i := s.level-1; i >= 0; i-- {
        for x.forwards[i] != nil && x.forwards[i].val < target {
            x = x.forwards[i]
        }
        if x.forwards[i] != nil && x.forwards[i].val == target {
            return true
        }
    }
    return false
}

删除

上图表示删除节点 43。红色箭头标识需要重新构建的指针。黑色标识要删除的节点、指针、要做的调整，注意，这里要调整头节点的层级。

func (s *Skiplist) Erase(num int) bool {
    erased := false

    x := s.head
    for i := s.level-1; i >= 0; i-- {
        for x.forwards[i] != nil && x.forwards[i].val < num {
            x = x.forwards[i]
        }
        if x.forwards[i] != nil && x.forwards[i].val == num {
            erased = true
            x.forwards[i] = x.forwards[i].forwards[i]
        }
    }
    for i, forward := range s.header.forwards {
        if forward == nil {
            this.level = i
            break
        }
    }
    return erased    
}

通用模式

x := s.header
for i := s.level-1; i >= 0; i-- {
    for x.forwards[i] != nil && x.forwards[i].val < target {
        x = x.forwards[i]
    }
    if x.forwards[i] != nil && x.forwards[i].val == target {
        // Do something.
    }
}

跳表练习

leetcode - 1206. Design Skiplist + 一个 solution

参见

数据结构与算法 C语言描述 10.4.2 跳跃表
Redis 设计与实现第 5 章跳跃表
Redis 源码：t_zset.c、server.h

dushaoshuai / dushaoshuai.github.io

跳表 #131