Go语言实现跳表

跳表是一种经典的以空间换时间的数据结构。对于普通的链表来说，由于只能使用顺序查找，因此查找的时间复杂度就为 O(n)，而跳表有多条并联链表，因此可以实现 O(logn) 的时间复杂度，类似于二分查找的链表版本。其空间复杂度为 O(n)。

推荐文章：基于golang从零到一实现跳表，以下内容来自于该文章。

跳表的读流程

以 head 节点作为起点
从当前跳表存在的最大高度出发
倘若右侧节点 key 值小于 target，则持续向右遍历
倘若右侧节点 key 值等于 target，则代表找到目标，直接取值返回
倘若右侧节点为终点（nil）或者 key 值大于 target，则沿当前节点降低高度进入下一层
重复 3 - 5 步
倘若已经抵达第 1 层仍然找到不到 target，则返回 key 不存在的信息

跳表的写流程

首先基于读流程检索出 key 对应的节点是否存在，倘若存在，则对值进行更新并直接返回
根据基于golang从零到一实现跳表 3.6 小节中的规则，随机出新插入节点的高度；倘若新插入节点的高度大于当前跳表的最大高度，则需要对起点和终点的高度进行扩容
以 head 节点作为起点，从当前跳表存在的最大高度出发
倘若右侧节点 key 值小于 target，则持续向右遍历
倘若右侧节点为终点（nil）或者 key 值大于 target，则在该空隙插入新节点，并降低高度进入下一层
重复 4 - 5 步
倘若已经进入第 1 层，插入新节点后即可返回

步骤 2 中的规则是指：

每个上层链表节点个数接近于相邻下层链表个数的一半
每个上层链表节点均在相邻下层链表中存在

上层链表节点相隔距离不作要求，只要我们保证了上层节点个数接近于相邻下层的一半，在大数据量的情况下，随机性问题会被转化为数学期望问题，最终同样能够实现上层索引的二分查找效果

层数	数量	概率
1	N	1/2
2	N/2	1/4
3	N/4	1/8
m	N/2^(m-1)	1/2^m

跳表的删流程

以 head 节点作为起点，从当前跳表存在的最大高度出发
倘若右侧节点 key 值小于 target，则持续向右遍历
倘若右侧节点为终点（nil）或者 key 值大于 target，降低高度进入下一层
倘若右侧节点 key 值等于 target，则代表找到目标
找到目标值后，沿当前节点层层向下，依次将每层中的目标节点删除
倘若已经进入第 1 层仍然没有找到节点，说明节点不存在，删除失败
倘若删除成功，需要尝试对跳表的整体高度进行缩容，即需要对高度递减，直到确定最大高度对应的层数上至少存在一个有效的数据节点为止

跳表的 range 流程

以 head 节点作为起点
从当前跳表存在的最大高度出发
倘若右侧节点 key 值小于 target，则持续向右遍历
倘若右侧节点为终点（nil）或者 key 值大于 target，则沿当前节点降低高度进入下一层
倘若右侧节点 key 值等于 target，则代表找到目标，直接沿该节点向下来到第 1 层
重复 3 - 5 步，直到来到第 1 层，接下来从首个大于等于 target 的节点出发，向右依次遍历，直到取满 range 区间的数据后返回

跳表的 ceiling 流程

以 head 节点作为起点
从当前跳表存在的最大高度出发
倘若右侧节点 key 值小于 target，则持续向右遍历
倘若右侧节点为终点（nil）或者 key 值大于 target，则沿当前节点降低高度进入下一层
倘若右侧节点 key 值等于 target，则代表找到目标，直接取值返回
重复 3 - 5 步，直到找到 key 值等于 target 的节点或者来到第 1 层，接下来获取到首个大于等于 target 的节点并返回

跳表的 floor 流程

以 head 节点作为起点
从当前跳表存在的最大高度出发
倘若右侧节点 key 值小于 target，则持续向右遍历
倘若右侧节点为终点（nil）或者 key 值大于 target，则沿当前节点降低高度进入下一层
倘若右侧节点 key 值等于 target，则代表找到目标，直接取值返回
重复 3 - 5 步，直到找到 key 值等于 target 的节点或者来到第 1 层，接下来获取到首个小于等于 target 的节点并返回

代码实现：

这里统一将 key-value 设置为 int 类型，当然也可以使用 Go 中的泛型 [T cmp.Ordered]

定义数据结构

// 跳表节点
type SkipListNode struct {
    key   int
    value int
    nexts []*SkipListNode
}

// 跳表结构
type SkipList struct {
    head *SkipListNode
}

跳表读操作

// 跳表的读操作
// 根据 key 读取 value，bool 表示 key 是否存在
func (s *SkipList) Get(key int) (int, bool) {
    // 根据 key 尝试检索对应的 node，如果存在则返回对应的值，否则返回 false
    if node := s.search(key); node != nil {
        return node.value, true
    }
    return -1, false
}

// 从跳表中检索 key 对应的 node
func (s *SkipList) search(key int) *SkipListNode {
    // 如果跳表为空，则直接返回 nil
    if s.head == nil || len(s.head.nexts) == 0 {
        return nil
    }
    // 从跳表的头节点开始，从最高层开始检索
    curr := s.head
    for level := len(s.head.nexts) - 1; level >= 0; level-- {
        // 在当前层上，从左向右检索，直到找到一个节点，其 key 大于等于目标 key
        for curr.nexts[level] != nil && curr.nexts[level].key < key {
            curr = curr.nexts[level]
        }
        // 如果找到了一个节点，其 key 等于目标 key，则返回该节点
        if curr.nexts[level] != nil && curr.nexts[level].key == key {
            return curr.nexts[level]
        }
        // 如果没有找到，则继续层数 - 1，在更低的层上进行检索
    }
    // 如果检索到了跳表的最底层，仍然没有找到，则返回 nil
    return nil
}

跳表写操作

这里可以巧妙地使用 rand.Int() 函数随机产生有符合整数，分别有 1/2 的概率产生正负整数。每产生一次正数或者负数就增加一层，这样就符合跳表的写流程中的概率规则。

也可以使用 rand.Intn(2) == 1 是相同的道理

// 跳表的写操作
// roll函数用于随机生成一个层数，每层概率 * 1/2
func (s *SkipList) roll() int {
    var level int
    // 巧妙利用 rand.Intn(2) 函数，每次产生一个 0 或 1 的概率为 1/2
    for rand.Intn(2) == 1 {
        level++
    }
    return level
}

// 插入 key-value 键值对到跳表中
func (s *SkipList) Put(key, value int) {
    // 如果跳表为空，则创建一个新的跳表
    if s.head == nil {
        s.head = &SkipListNode{
            key:   -1,
            value: -1,
            nexts: make([]*SkipListNode, 1),
        }
    }
    // 如果 key-value 键值对已经存在，则更新其 value 并返回
    if node := s.search(key); node != nil {
        node.value = value
        return
    }
    // roll产生一个随机层数
    level := s.roll()
    // 如果随机层数大于当前跳表的层数，则暂时通过 nil 补齐高度
    for len(s.head.nexts)-1 < level {
        s.head.nexts = append(s.head.nexts, nil)
    }
    // 创建新节点
    newNode := &SkipListNode{
        key:   key,
        value: value,
        nexts: make([]*SkipListNode, level+1),
    }
    // 从跳表的头节点开始，从最高层开始检索
    curr := s.head
    for l := len(s.head.nexts) - 1; l >= 0; l-- {
        // 在当前层上，从左向右检索，直到找到一个节点，其 key 大于等于目标 key
        for curr.nexts[l] != nil && curr.nexts[l].key < key {
            curr = curr.nexts[l]
        }
        // 如果当前层的节点数大于等于随机层数，则将新节点插入到当前层
        if l <= level {
            // 单链表插入: 调整指针关系，完成新节点的插入
            // curr -> newNode -> curr.nexts
            newNode.nexts[l] = curr.nexts[l]
            curr.nexts[l] = newNode
        }
    }
}

跳表的删操作

// 跳表的删操作
func (s *SkipList) Del(key int) bool {
    // 如果 key-value 不存在，则无需删除直接返回
    if node := s.search(key); node == nil {
        return false
    }
    // 从跳表的头节点开始，从最高层开始检索
    curr := s.head
    for level := len(s.head.nexts) - 1; level >= 0; level-- {
        // 在当前层上，从左向右检索，直到找到一个节点，其 key 大于等于目标 key
        for curr.nexts[level] != nil && curr.nexts[level].key < key {
            curr = curr.nexts[level]
        }
        // 右侧节点不存在或者 key 值大于 target，则直接跳过
        if curr.nexts[level] == nil || curr.nexts[level].key > key {
            continue // 进入下一层
        }
        // 此处意味着右侧节点的 key 值必然等于 key，则调整指针引用，进行删除
        curr.nexts[level] = curr.nexts[level].nexts[level]
    }
    // 对跳表的最大高度进行更新
    var dif int
    // 如果某一层已经不存在数据节点，高度需要减少
    for level := len(s.head.nexts) - 1; level > 0 && s.head.nexts[level] == nil; level-- {
        dif++
    }
    s.head.nexts = s.head.nexts[:len(s.head.nexts)-dif]
    return true
}

跳表的 range 操作

range 操作就是找到一个区间内的 key-value，这里是因为 key-value 都为 int 类型，所以使用 [2]int 数组，如果 key-value 是不同的类型，可以使用字典或者结构体。

// 跳表的range操作
// 找到 skiplist 当中 >= start，且 <= end 的 key-value 返回二维数组
func (s *SkipList) Range(start, end int) [][2]int {
    // 首先通过 ceiling 方法，找到 skiplist 中 key 值大于等于 start 且最接近于 start 的节点 ceilNode
    ceilNode := s.ceiling(start)
    // 如果不存在，直接返回
    if ceilNode == nil {
        return [][2]int{}
    }
    // 从 ceilNode 最低层出发向右遍历，把所有位于 [start,end] 区间内的节点都返回
    var res [][2]int
    for curr := ceilNode; curr != nil && curr.key <= end; curr = curr.nexts[0] {
        res = append(res, [2]int{curr.key, curr.value})
    }
    return res
}

// 找到 skiplist 当中 key 值大于等于 target 且最接近于 target 的节点
func (s *SkipList) ceiling(target int) *SkipListNode {
    // 如果跳表为空，则直接返回 nil
    if s.head == nil || len(s.head.nexts) == 0 {
        return nil
    }
    // 从跳表的头节点开始，从最高层开始检索
    curr := s.head
    for level := len(s.head.nexts) - 1; level >= 0; level-- {
        // 在当前层上，从左向右检索，直到找到一个节点，其 key 大于等于目标 key
        for curr.nexts[level] != nil && curr.nexts[level].key < target {
            curr = curr.nexts[level]
        }
        // 如果找到了一个节点，其 key 等于目标 key，则返回该节点
        if curr.nexts[level] != nil && curr.nexts[level].key == target {
            return curr.nexts[level]
        }
    }
    // 此处 curr 已经对应于在最低层 key 值小于 key 且最接近于 key 的节点
    // 其右侧第一个节点即为所寻找的目标节点
    return curr.nexts[0]
}

跳表的 ceiling 操作

这一部分的 ceiling 操作实际上已经在上面的 range 操作中讲解了，这里只需要再封装一层可导出的接口即可。

// 跳表的ceiling操作
func (s *SkipList) Ceiling(target int) ([2]int, bool) {
    if ceilNode := s.ceiling(target); ceilNode != nil {
        return [2]int{ceilNode.key, ceilNode.value}, true
    }
    return [2]int{}, false
}

跳表的 floor 操作

floor 操作与 ceiling 操作类似，只是条件范围不同。

// 跳表的floor操作
// 找到 skiplist 中，key 值小于等于 target 且最接近于 target 的 key-value
func (s *SkipList) Floor(target int) ([2]int, bool) {
    // 使用 floor 方法，找到 skiplist 中 key 值小于等于 target 且最接近于 target 的节点 floorNode
    if floorNode := s.floor(target); floorNode != nil {
        return [2]int{floorNode.key, floorNode.value}, true
    }
    return [2]int{}, false
}

// 找到 skiplist 中 key 值小于等于 target 且最接近于 target 的节点
func (s *SkipList) floor(target int) *SkipListNode {
    // 如果跳表为空，则直接返回 nil
    if s.head == nil || len(s.head.nexts) == 0 {
        return nil
    }
    // 从跳表的头节点开始，从最高层开始检索
    curr := s.head
    for level := len(s.head.nexts) - 1; level >= 0; level-- {
        // 在当前层上，从左向右检索，直到找到一个节点，其 key 大于目标 key
        for curr.nexts[level] != nil && curr.nexts[level].key <= target {
            curr = curr.nexts[level]
        }
        // 如果找到了一个节点，其 key 等于目标 key，则返回该节点
        if curr.nexts[level] != nil && curr.nexts[level].key == target {
            return curr.nexts[level]
        }
    }
    // 此处 curr 已经对应于在最低层 key 值小于等于 key 且最接近于 key 的节点
    return curr
}