有时候，我们会说，在计算机世界里，其实只有两种数据结构，一个是数组一个是链表。原因是其他的数据结构都是基于这两种数据结构做的扩展。
数组和链表的优缺点实在是非常的明显。数组可以高效查找，按照下标索引，但是很难进行高效的删除和扩容。链表的优缺点正好相反。很多时候，我们不用链表的原因就是因为它没有办法快速查找和插入。但是，如果我们可以对它进行改造，让它可以使用类似二分查找的方法就很棒了。这个改造的结果就是 SkipList。
跳表的原理
SkipList 的原理是给链表中的某一些元素添加索引，然后建立多级索引达到效果。
每隔几个节点，从链表中提取出一个节点作为一级索引。然后再从一级索引中，每隔几个节点，再提取一个节点作为二级索引。如下图所示：
当我们查找时，在最高级索引中查找，依次向下。假如我们要查找数字 18。我们从最高级索引中查找，找到 5，然后找到 27 时，发现它大于 18，我们到下一级查找。在下一级中找到 15，然后 27，发现 27 比 18 大，然后到最低级中查找，15 的后一个就是 18。
可以看到，即便是在元素很少的时候，这个查找路径也要比从头开始查找要少一个元素。如果想象整个链表的数据是 1000 个，或者 10000 个，那么查询效率会大大提升。
跳表的空间时间占用
但是，SkipList 有一个明显的缺点，就是空间占用变多，假设每两个元素提出一个索引时，空间占用就是：$\frac n 2, \frac n 4, \frac n 8, …, 8, 4, 2$ ，求和之后得到 $n-2$。实际上就是 $O(n)$ 的时间复杂度。但是实际上，索引存储的只是实际数据的指针，即便是多级索引，也是多了几个索引而已。并不是将原始数据 copy 一遍。所以，实际使用的过程中，这个空间并不会达到 $O(n)$ 这么夸张。
假设，我们在任何一级中，都保持每两个元素提出一个索引。那么一级索引就是 $\frac n 2$ ，二级索引就是 $\frac n 4$ ，以此类推，可以得到第 $K$ 级索引的节点个数就是 $\frac n {2^k}$ 。加入索引有 $H$ 级，有两个索引节点，那么可得 $\frac n {2 ^h} = 2$ ，那么可以得到 $h = \log_2 n -1$，如果再加上原始链表一层，那么就是 $\log_2 n$ 。在查询过程中，如果每一层都需要查询 $m$ 个节点，那么时间复杂度就是 $O(m * \log_2 n)$ ，因为每一层 $m$ 的值有一个最大的限制。时间复杂度为 $O(\log_2n)$。
跳表的索引生成
当我们向一个链表中添加一个节点后，索引之间的节点数就会增多，如果增加太多的话，就会导致跳表的查询效率急剧退化。所以，当我们向跳表中添加一个元素之后，我们就要决定是否要对它生成索引，生成到几级。所以，我们也像红黑树一样，需要有一种手段来维护整个跳表。
如果节点增多了，那么相应的索引就增多，避免性能退化。红黑树通过左右旋转来达到这个要求。跳表一般使用一个随机函数来决定将这个结点插入到哪几级索引中，比如随机函数生成了值 X，那我们就将这个结点添加到第一级到第 X 级的索引中。
跳表的实现
那么下面我们来实现一个 SkipList。下面的跳表实现了一个 SortedSet，一个有序的不能重复的跳表结构。
跳表定义
// 定义了最大的层级限制
const MAX_LEVEL = 16
// 定义生成层级的因子
const LEVEL_FACTOR = 0.5
// 定义了几种错误码
const (
OK = iota + 1
DUPLICATED
NOT_EXIST
NOT_INIT
)
// 定义了一个描述数据的接口
type Interface interface {
// less than p
Less(p Interface) bool
// equal with p
Equal(p Interface) bool
}
// 定义了一个伪节点，用于当做链表中的哨兵
type fakeNode struct {
}
func (f *fakeNode) Less(p Interface) bool {
return false
}
func (f *fakeNode) Equal(p Interface) bool {
return false
}
上面定义了一些后面会用到的 struct 和 interface 。最主要的就是 Interface ，他用来描述一个实际存储的对象。
fakeNode 是用来放在链表的头部，方便后面的节点操作。这是数据结构中一种常用的哨兵方法。
// 链表中 实际的节点
type node struct {
data Interface // 实际的数据
forwards []*node // 索引存储的位置
level int // 节点的层级
}
// 链表的定义
type SkipList struct {
head *node // 链表头节点，存储 fakeNode
length uint32 // 链表长度
level int // 当前跳表最高层级
}
// 初始化一个节点
func newNode(p Interface, l int) *node {
return &node{data: p, forwards: make([]*node, l, l), level: l}
}
// 初始化一个跳表，head 默认是拥有最高层级
func NewSkipList() *SkipList {
return &SkipList{newNode(&fakeNode{}, MAX_LEVEL), 0, 1}
}
下面是具体的方法实现，主要实现了三个 Add 、 Delete 和 Search。
跳表添加元素
// 这里随机产生一个 层级
// 在 LEVEL_FACTOR 是 0.5 的情况下
// 1 级的概率是 50%
// 2 级的概率是 25%
// 3 级的概率是 12.5%, 以此类推
func (sl *SkipList) randomLevel() int {
l := 1
// 使用随机数来决定层级
for rand.Float64() < LEVEL_FACTOR && l < MAX_LEVEL {
l++
}
// 如果层级比当前层级高2级或以上，按照高一级处理，避免浪费
if sl.level+1 < l {
return sl.level + 1
}
return l
}
// 增加一个节点到跳表中
func (sl *SkipList) Add(p Interface) int {
// 如果 head 为空，说明没有初始化
if sl.head == nil {
return NOT_INIT
}
// 找到应该插入的位置
cur := sl.head
// 查找的路径记录
update := [MAX_LEVEL]*node{}
// 从最高级开始查找
i := MAX_LEVEL - 1
for ; i >= 0; i-- {
// 在当前层级向后查找
for nil != cur.forwards[i] {
// 如果相等，那么不允许插入
if cur.forwards[i].data.Equal(p) {
return DUPLICATED
}
// 如果下一个元素 > 要插入的元素
if !cur.forwards[i].data.Less(p) {
// 记录当前层级的元素，跳到下一级
update[i] = cur
break
}
// 向后移动游标
cur = cur.forwards[i]
}
// 如果这个层级遍历结束，还是没有找到对应位置
// 那么就将最后的元素作为当前层级路径
if nil == cur.forwards[i] {
update[i] = cur
}
}
sl.length++ // 找到位置，跳表长度加1
//生成当前节点层级
l := sl.randomLevel()
// 初始化节点
n := newNode(p, l)
// 从最底层开始添加节点和索引
for i := 0; i < n.level; i++ {
next := update[i].forwards[i]
n.forwards[i] = next
update[i].forwards[i] = n
}
// 更新跳表的索引
if n.level > sl.level {
sl.level = n.level
}
return OK
}
跳表删除元素
func (sl *SkipList) Delete(p Interface) int {
// 查找元素
// 与添加不通的是：不需要考虑相等的情况
// 如果某一个层级没有的话，不需要记录层级的最后节点
cur := sl.head
update := [MAX_LEVEL]*node{}
for i := sl.level - 1; i >= 0; i-- {
update[i] = cur
for nil != cur.forwards[i] {
if !cur.forwards[i].data.Less(p) {
update[i] = cur
break
}
cur = cur.forwards[i]
}
}
cur = update[0].forwards[0] // 要删的节点
if cur == nil { // 无此元素
return NOT_EXIST
}
// 从节点所在的最高层级依次向下删除
for i := cur.level - 1; i >= 0; i-- {
// 如果当前节点是某一个层级的最后一个元素
// 那么降低跳表的层级
if update[i] == sl.head && cur.forwards[i] == nil {
sl.level = i
}
// 删除元素
if nil != update[i].forwards[i] {
update[i].forwards[i] = update[i].forwards[i].forwards[i]
}
}
sl.length-- // 长度减1
return OK
}
跳表查找元素
// 查找元素
// 查找过程 同 Add 和 Delete
func (sl *SkipList) Search(p Interface) *node {
cur := sl.head
update := [MAX_LEVEL]*node{}
i := MAX_LEVEL - 1
for ; i >= 0; i-- {
for nil != cur.forwards[i] {
if cur.forwards[i].data.Equal(p) {
return cur
}
if !cur.forwards[i].data.Less(p) {
update[i] = cur
break
}
cur = cur.forwards[i]
}
if nil == cur.forwards[i] {
update[i] = cur
}
}
return nil
}
其他方法
// 按层级打印跳表
func (sl *SkipList) Print() {
cur := sl.head
for i := sl.level; i >= 0; i-- {
fmt.Printf("[level = %d] ", i)
for nil != cur {
fmt.Printf("%+v ", cur.data)
cur = cur.forwards[i]
}
fmt.Println("")
cur = sl.head
}
}
// 获取长度
func (sl *SkipList) Length() uint32 {
return sl.length
}
// 获取高度
func (sl *SkipList) Level() int {
return sl.level
}
尾声
跳表的使用其实比较广泛，在某些场景下，可以替换红黑树，而且比红黑树实现要简单得多。在 Redis 的 SortedSet 中，就用了跳表来实现这一数据结构。
署名-非商业性使用-相同方式共享 4.0
