跳表的原理与实现

  1. 跳表的原理
    1. 跳表的空间时间占用
    2. 跳表的索引生成
  2. 跳表的实现
    1. 跳表定义
    2. 跳表添加元素
    3. 跳表删除元素
    4. 跳表查找元素
    5. 其他方法
  3. 尾声

有时候,我们会说,在计算机世界里,其实只有两种数据结构,一个是数组一个是链表。原因是其他的数据结构都是基于这两种数据结构做的扩展。

数组和链表的优缺点实在是非常的明显。数组可以高效查找,按照下标索引,但是很难进行高效的删除和扩容。链表的优缺点正好相反。很多时候,我们不用链表的原因就是因为它没有办法快速查找和插入。但是,如果我们可以对它进行改造,让它可以使用类似二分查找的方法就很棒了。这个改造的结果就是 SkipList。

跳表的原理

SkipList 的原理是给链表中的某一些元素添加索引,然后建立多级索引达到效果。

每隔几个节点,从链表中提取出一个节点作为一级索引。然后再从一级索引中,每隔几个节点,再提取一个节点作为二级索引。如下图所示:

skiplist

当我们查找时,在最高级索引中查找,依次向下。假如我们要查找数字 18。我们从最高级索引中查找,找到 5,然后找到 27 时,发现它大于 18,我们到下一级查找。在下一级中找到 15,然后 27,发现 27 比 18 大,然后到最低级中查找,15 的后一个就是 18。

skiplist-search

可以看到,即便是在元素很少的时候,这个查找路径也要比从头开始查找要少一个元素。如果想象整个链表的数据是 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}
}

下面是具体的方法实现,主要实现了三个 AddDeleteSearch

跳表添加元素

// 这里随机产生一个 层级
// 在 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