跳表原理以及Golang实现

一、前言

大家应该对 二分查找算法 不陌生，二分查找之所以能达到 O(logN) 的时间复杂度，一个重要原因在于它所依赖的数据结构是数组，数组支持随机访问，可通过下标很容易地定位到中间的某个元素。但是链表就没有 随机访问数据 这个特性，要判断是否包含某个元素，只能从头开始遍历对比。但是数组有数组的局限性，比如需要连续的内存空间，插入删除操作会引起数组的扩容和元素移动；链表有链表的优势，链表不需要先申请连续的空间，插入删除操作的效率非常高。

事实上，对于一个有序的链表，我们可以通过建索引的方式，做到类似二分查找的效果。

假设我们有一个已经排好序的链表(其实是一个双链表，这里为了方便，看待成单链表)：

如果要对这个链表进行查找，那将是 O(n) 的时间复杂度，我们做一些额外的工作：先对链表中每两个结点建一个索引构成一级索引，再对一级索引进行同样的操作得到二级索引：

当我们要查找元素 20 时，从最高层开始查，则查找路线应该是 1(向右)->8(向右)->14(向下)->14(向右)->20，经过了 5 个结点；如果直接在原始链表中查找，需要经过 11 个结点，速度有很明显的提升。不过你也发现了，这是典型的 空间换时间 ，虽然查找速度提升了，但是需要花费空间去存储每一层的索引，占用了更大的空间。

这种带多级索引的链表结构，就是我们今天要详细学习的 跳表。许多开源软件中都有使用到 跳表 这种数据结构，比如 Redis 中的 zset ，我也是最近看 redis 源码才发现对 skiplist 了解甚少，才决定专门学习一遍。

二、跳表的性质

跳表 可以视为一个 水平排列(Level)、垂直排列(Tower) 的位置(position，对具体结点 Entry 访问的抽象) 的二维集合。跳表具有如下性质：

• 由多层(Level)组成，最底层为第 1 层，向上一层为第 2 层，以此类推。层数不会超过规定的一个最大值 LMAX；

• 每一层都是一个拥有头结点的有序列表，第 1 层的链表包含所有的元素；

• 如果一个元素出现在第 k 层，那么它一定出现在第 1 ~ (k-1) 层；同时会按照一定的概率 p 出现在第 k+1 层。 这也是 “第 k 层是第 k-1 层的索引” 描述的体现。

为了节省空间，第一层之上都不存储实际数据，只有指针，包含同层下一个元素的指针 和 同列下一个元素的指针。

当查找元素时，会从最顶层链表的头节点开始遍历。以升序跳表为例，如果当前节点的下一个节点包含的值比目标元素值小，则继续向右查找。如果下一个节点的值比目标值大，就转到当前层的下一层去查找。重复向右和向下的操作，直到找到与目标值相等的元素为止。以下为找到元素 20 的路径：

三、跳表的 Golang 实现

跳表首先由 William Pugh 在其 1990 年的论文《Skip lists: A probabilistic alternative to balanced trees》中提出。由该论文的题目可以知道两点：

• 跳表是概率型数据结构。
• 跳表是用来替代平衡树的数据结构。准确来说，是用来替代自平衡二叉查找树（self-balancing BST）的结构。

在这里我们用 Golang 具体实现一遍。

首先定义需要的结构体：

type Node struct {
    Value int            // 某个结点的值，为了方便理解，这里暂时使用 int
    forward  []*Node     // 存储该节点所有层的下一个节点的信息，纵向观察，数组的长度是固定的，为 maxLevel。
    curLevel int         // 本节点最高层
}

type SkipList struct {
    head     *Node // 当前结点
    length   int   // (最后一层)总结点长度
    maxLevel int   // 跳表的最大层
}

这里最让人疑惑的是 forward []*Node 这个属性，它用来存储该结点所有层的下一个节点。怎么理解呢？看上图，对于结点 8 来说，第一层该结点的下一个节点是 9，第二层该结点的下一个节点是 10，第三层该结点的下一个节点是 14，当 maxLevel = 3(代表forward数组长度为 3) 时，结点 8 的 forward 的应该是 [9, 10, 14]。

当我们要定位一个元素时，从最顶层 先行后列、从上到下 进行对比。怎么个先行后列？从最顶层开始，如上图，这就选定了第一个元素 1，如果当前的元素比要定位的元素小并且后面的元素不为空时，将当前的位置水平向右移动(p = p.forward[i])，否则，向下移动。重复这个动作，直到找到合适的位置。

接下来我们还要有一个初始化 SkipList 的操作：

// CreateSkipList 初始化一个 SkipList
func CreateSkipList(base,maxLevel int) *SkipList {
    s := new(SkipList)
    s.head = new(Node)
    s.maxLevel = maxlevel

    // 第一列默认全都为 base ，并且不计算在 length 中
    s.head.curLevel = maxlevel - 1  // 计算层数的时候，为了和 forward 数组保持一致，从第 0 层开始计数
    s.head.forward = make([]*Node, maxlevel)
    s.head.Value = base
    s.length = 0

    return s
}

我们先看插入一个元素：

1. 插入新元素

第一步，确定这个元素的位置；第二步，确定这个元素应该有的层数。

参考之前的性质：如果一个元素出现在第 k 层，那么它一定出现在第 1 ~ (k-1) 层；同时会按照一定的概率 p 出现在第 k+1 层。这个概率我们可以通过一个函数来解决：

//
func (s *SkipList) getNodeLevel() int {
    var level int = 0  // 根据性质 第1层包含所有的元素，所以第一层肯定包含这个新元素，所以默认在第一层

    rand.Seed(time.Now().UnixNano())
    for {
        // 第 k 层 有 1/2 的概率成为 k-1 层的索引，并且不会超过最大层
        if rand.Intn(2) == 1 || level >= s.maxLevel-1 {
            break
        }
        level++
    }
    return level
}

接下来我们看插入的过程：

func (s *SkipList) Insert(value int) (bool, error) {
    v, err := checkSkipListValid(s)
    if v == false {
        return false, err
    }

    p := s.head
    newNode := new(Node)
    newNode.Value = value
    newNode.forward = make([]*Node, s.maxLevel)
    level := s.getNodeLevel() // 当前节点所包含的层数


    // forward []*Node 存储该节点所有层的下一个节点的信息
    for i := s.maxLevel - 1; i >= 0; i-- {
        // 从最高层开始，向下移动
        for {
            // 找到应该插入的位置
            if p.forward[i] != nil && p.forward[i].Value < value {
                p = p.forward[i] // 不为空且插入的值比当前值大，向右移动
            } else {
                // 当前值的当前行的后继为空或者大于插入值，应该向下走，即 i-1
                break
            }
        }
        //find the last Node which match user defined IsLess() condition in i level
        //insert new Node after the node
        // 在第i层找到应该插入的最佳位置，然后在该位置插入新的节点
        // level层以下都有这个节点
        if i <= level {
            // 相当于链表的插入操作，新节点在当前层的下一个节点就是当前节点的后一个节点
            newNode.forward[i] = p.forward[i]
            p.forward[i] = newNode  // 当前节点的后一个节点就是新节点
        }
    }
    newNode.curLevel = level
    s.length++  // 更新节点长度加一

    return true, nil
}

我们通过一组图来说明这个情况：

加入我们设定 maxLevel = 5、插入节点 10 时得到的 level = 1，那么效果如下：

当我们继续 插入元素 20 时，假如计算得到 level = 2，从上述代码第 15 行开始进去循环，从节点 p = base 开始遍历，在第二个 for 循环，也就是第 17 行里面，base 的 forward = [10, 10, nil, nil, nil] ，第 4 层和第 3 层都直接跳过。

当 i = 2 也就是第 2 层时，base.forward[2] = nil，所以不会走到第 20 行，但是此时 i <= level，于是有 newNode.forward[2] = p.forward[2] = base.forward[2] = nil，也就是第 2 层的下一个结点，p.forward[2] = base.forward[2] = newNode(结点 20)：

当 i = 1 也就是第 1 层时，在第 19 行处，base.forward[1] = 10 != nil，并且 10 < 20，因此会走到底 20 行，p = p.forward[i] = base.forward[1] = 10，之后跳出内层循环，来到第 30 行，同样执行赋值操作：

同样，当 i = 0 即最底下一层时，操作步骤和 i=1 时一样，最终效果为：

再比如我们 插入元素 15。假如得到的 level = 0，即只出现在最底层。i >= 1 这个过程和插入 20 时没多大区别：

当 i = 0 时，第 19 行代码中，base.forward[0] = 10 != nil，并且 ·10 < 15，因此 p = p.forward[0] = 10，继续内层循环，此时发现虽然 p.forward[0] = 结点10.forward[0] = 20 != nil，但是 20 > 15，因此跳出内层循环，在下面第 30 行，将 结点 15 插在了结点 10 和结点 20 的中间，效果如下：

2. 查找元素

查找元素 value 是否在跳表中，如果存在返回对应的 Node，否则返回 nil。

还是固定的遍历策略，先看代码：

//try to find the first node which not match the user defined IsLess() condition
func (s *SkipList) Search(value int) *Node {
    p := s.head

    // 从最高层开始
    for i := s.maxLevel - 1; i >= 0; i-- {
        // 从左往右
        for {
            if p.forward[i] != nil && p.forward[i] < value {
                p = p.forward[i]  // 当前节点的 next 不空，且当前值小于待查找值，则向右移动
            } else {
                break
            }
        }
    }

    // 假如我们需要查找 value=14，此时已经定位到第一层的10
    p = p.forward[0]

    // 还是要再判断一下p的 value，比如我们要查找14，那 p=15 就不符合，应该返回 nil
    if p.Value != value {
        return nil
    }

    return p
}

3. 删除元素

假设我们已经有了如下的跳表：

代码如下：

func (s *SkipList) RemoveNode(obj int) bool {

    var update []*Node = make([]*Node, s.maxLevel)  // 用来存储被删除结点每一层的前缀
    p := s.head

    for i := s.maxLevel - 1; i >= 0; i-- {
        for {
            if p.forward[i] != nil && p.forward[i].Value < obj {
                p = p.forward[i]
            } else {
                break
            }
        }
        update[i] = p
    }
    p = p.forward[0]

    // 删除的节点不存在
    if p == nil || p.Value < obj || obj < p.Value {
        return false
    }

    for i := p.curLevel; i >= 0; i-- {
        // 将被删除结点的前缀，指向删除结点的 next
        update[i].forward[i] = p.forward[i]
    }
    s.length--

    return true
}

现在我们想 删除结点 20。运行到第 16 行时，update = [15, 10, base, base, base]。p = p.forward[0] = 20，即此时 p 指向被删除的节点。在第 23 行，从 结点 20 的最高层开始，逐层替换掉被删除结点的前缀结点的后缀结点。

4. 逐层打印跳表

直接看代码：

func (s *SkipList) Traverse() {

	var p *Node = s.head

	for i := s.maxLevel - 1; i >= 0; i-- {
		for {
			if p != nil {
				fmt.Print("%d",p.Value)
				if p.forward[i] != nil {
					fmt.Print("-->")
				}
				p = p.forward[i]
			} else {
				break
			}
		}
		fmt.Println()
		p = s.head
	}
}

四、时空复杂度分析

都是 O(logn)。具体证明方法请阅读 【参考文献】中 2 跟 3 。

五、总结

跳表 是一个非常优秀的数据结构，在 Redis 中被用来作为 zset 的底层实现，但是 Redis 的实现比上述设计要复杂的多，比如其引入了 span 表示当前节点到下一个 forward 跨过了几个元素，用来快速计算排名等。

不过有一点，二叉平衡树也能用来做排序查找，为什么 Redis 不采用树形结构呢？其实 Redis 的作者已经在 这里 说出了原因：

There are a few reasons:

1. They are not very memory intensive. It’s up to you basically. Changing parameters about the probability of a node to have a given number of levels will make then less memory intensive than btrees.

2. A sorted set is often target of many ZRANGE or ZREVRANGE operations, that is, traversing the skip list as a linked list. With this operation the cache locality of skip lists is at least as good as with other kind of balanced trees.

3. They are simpler to implement, debug, and so forth. For instance thanks to the skip list simplicity I received a patch (already in Redis master) with augmented skip lists implementing ZRANK in O(log(N)). It required little changes to the code.

大致意思就是：

跳表更加节省内存，并且计算随机层数的函数，可以由自己随意更改来获得更多或者更少的索引；

zset 经常用来实现整体遍历操作，这一点上二者相差无几；

跳表在调试的时候更容易操作一些。

【参考文献】

• 1. Golang 跳表的实现 https://github.com/GrassInWind2019/skipList/blob/master/src/skipList/skipList.go
• 2. 跳表时空复杂度分析 https://lotabout.me/2018/skip-list/
• 3. 一文彻底搞懂跳表的各种时间复杂度、适用场景以及实现原理