简介

本文将参照论文使用Golang语言实现跳表

建议阅读：跳表-原理篇 | Crayonの博客

本文按照以下顺序进行：

编码实现

本次实现和论文一样，节点顺序以升序排序

结构体定义

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
type (
	Node struct {
		Key      float64
		Value    interface{}
		Forwards []*Node
	}

	SkipList struct {
		Head     *Node
		Level    int
		// MaxLevel 跳表的最大层级，这样可以很方便的实现不同最高层级的跳表
		MaxLevel int
		// P 层级上升的概率
		P        float64
	}
)

随机函数

和论文如出一辙，这里使用了golang的rand包来生成随机数

1
2
3
4
5
6
7
func (s *SkipList) randomLevel() int {
	level := 1
	for level < s.MaxLevel && rand.Float64() < s.P {
		level += 1
	}
	return level
}

查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
func (s *SkipList) Search(key float64) (interface{}, bool) {
    // 从头节点出发
	x := s.Head
    // 外层循环，控制从上到下的层级搜索
	for i := s.Level - 1; i >= 0; i-- {
        // 内层循环，控制从左到右的前进搜索
		for x.Forwards[i] != nil && x.Forwards[i].Key < key {
			x = x.Forwards[i]
		}
	}
    // 一直搜索到最后一层，不小于目标key的前一个节点
    // 获取下一个节点（因为遇到NIL会提前返回，不会返回NIL，所以可以不用判空）
	x = x.Forwards[0]
	if x == nil || x.Key != key {
		return nil, false
	}
	return x.Value, true
}

插入

插入操作和search操作类似，只是在找到插入位置后，需要将新节点插入到各层的前面

而论文中的伪代码可以发现，其实遍历节点的逻辑是相同的，只是多了一步记录各层节点的操作（需要记录下当前节点在各层的前驱节点，后续插入时才能同步更新）

并且在删除操作我们也需要进行遍历，所以我们可以把遍历的代码封装起来

1
2
3
4
5
6
7
8
9
10
11
func (s *SkipList) findPrev(key float64) (x *Node, update []*Node) {
	update = make([]*Node, s.MaxLevel)
	x = s.Head
	for i := s.Level - 1; i >= 0; i-- {
		for x.Forwards[i] != nil && x.Forwards[i].Key < key {
			x = x.Forwards[i]
		}
		update[i] = x
	}
	return
}

插入函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
func (s *SkipList) Insert(key float64, value interface{}) {
	x, update := s.findPrev(key)
	x = x.Forwards[0]
	if x != nil && x.Key == key {
		x.Value = value
		return
	}

	level := s.randomLevel()
	if level > s.Level {
		for i := s.Level; i < level; i++ {
			update[i] = s.Head
		}
		s.Level = level
	}

	x = makeNode(key, value, level)
	for i := 0; i < level; i++ {
		x.Forwards[i] = update[i].Forwards[i]
		update[i].Forwards[i] = x
	}
}

查找函数

不要忘记更新下查找函数的代码

1
2
3
4
5
6
7
8
func (s *SkipList) Search(key float64) (interface{}, bool) {
	x, _ := s.findPrev(key)
	x = x.Forwards[0]
	if x == nil || x.Key != key {
		return nil, false
	}
	return x.Value, true
}

删除

删除操作和插入操作类似，只是在找到删除节点后，需要将各层节点的前驱节点更新，然后删除节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
func (s *SkipList) Delete(key float64) bool {
	x, update := s.findPrev(key)
	x = x.Forwards[0]
	if x == nil || x.Key != key {
		return false
	}

	for i := 0; i < s.Level; i++ {
		if update[i].Forwards[i] != x {
			break
		}
		update[i].Forwards[i] = x.Forwards[i]
	}

	for i := s.Level - 1; i >= 0; i-- {
		if s.Head.Forwards[i] != nil {
			break
		}
		s.Level--
	}

	return true
}

代码测试

由于跳表存在随机的因素，所以这里通过多次的运行来测试跳表的正确性

1737798614731

通过配置文件指定执行的操作

配置文件样例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# 批量插入0-9999的kv
# ot（operation type）：操作类型
- ot: insert_range
  # input：输入参数
  input:
    # 最终插入的数据范围：0-9999
    # range_start：范围起点
    range_start: 0
	# range_end：范围终点
    range_end: 10000
# k=-1，不存在
- ot: search
  input:
    key: -1
  output:
    ok: false
# k=3377，存在且v=3377
- ot: search
  input:
    key: 3377
  output:
    ok: true
    value: 3377

具体的测试代码可以查看
demo-bucket/algorithm/algorithm-golang/skiplist/skiplist_test.go at master · SuCrayon/demo-bucket

性能对比

通过设置层级为1我们可以用同样的代码模拟有序单链表（也就是BST退化成链表的那种情况）的查找性能

以下测试使用的benchmark参数

1
-test.benchmem -test.benchtime=5s

数据量1k

跳表（MaxLevel=16，P=0.5）

1
2
opCount,nsPerOp,bytePerOp,allocPerOp
34254062,179.8,384,3

跳表（MaxLevel=32，P=0.25）

1
2
opCount,nsPerOp,bytePerOp,allocPerOp
29570007,215.7,768,3

跳表（MaxLevel=32，P=0.5）

1
2
opCount,nsPerOp,bytePerOp,allocPerOp
24861520,237.4,768,3

单链表（MaxLevel=1，P=0）

1
2
opCount,nsPerOp,bytePerOp,allocPerOp
786034,7536,24,3

数据量1w

跳表（MaxLevel=16，P=0.5）

1
2
3
4
5
6
opCount,nsPerOp,bytePerOp,allocPerOp
25082064,292.0,384,3
21268509,252.2,384,3
19541179,270.8,384,3
24443103,234.1,384,3
23645776,236.2,384,3

跳表（MaxLevel=32，P=0.25）

1
2
3
4
opCount,nsPerOp,bytePerOp,allocPerOp
15089992,403.9,768,3
18066450,392.1,768,3
16331352,439.7,768,3

跳表（MaxLevel=32，P=0.5）

1
2
opCount,nsPerOp,bytePerOp,allocPerOp
15095322,430.9,768,3

单链表（MaxLevel=1，P=0）

1
2
opCount,nsPerOp,bytePerOp,allocPerOp
36655,166034,24,3

数据量10w

单链表（MaxLevel=1，P=0）

1737800600781

可以看到在这个数据量下的操作非常地慢

跳表（MaxLevel=32，P=0.5）

1737800664852

而跳表则和1w数据量时一样，没有明显地性能下降

具体的测试代码可以查看
demo-bucket/algorithm/algorithm-golang/skiplist/benchmark_test.go at master · SuCrayon/demo-bucket

Leetcode

正好Leetcode上就有一道手写跳表的题目

稍微改造下代码实现即可提交测试了

题目链接：1206. 设计跳表 - 力扣（LeetCode）

1737801773560