跳跃表Skip List

skip list的原理

Java中的LinkedList是一种常见的链表结构,这种结构支持O(1)的随机插入及随机删除, 但它的查找复杂度比较糟糕,为O(n)。

假如我们有一个有序链表如下,如果我们想找到值为59的节点,需要查找7次。怎么提高查询效率呢?通常的做法是使用二分法,但LinkedList的随机访问时间复杂度同样为O(n),因此朴素的二分法并不适用。那怎么办呢?

list

我们可以在节点中增加额外的跳跃节点,如下:

list point

这样我们可以根据跳跃节点查询,只需要查找3次。至于查询47,我们先根据跳跃节点来查询,于是在节点22上,它的跳跃指针指向59,比47要大,因此我们可以知道47可能会存在于节点22和节点59之间,这时候再根据普通的指针顺序查找。一共需要查找5次。

随着节点的增多,我们的链表结构会变成这样:

list final

跳跃节点的密度为普通节点的一半,理想情况下,这种结构会比原结构查询性能提高一倍。有没有办法再提高呢?有,我们可以在这基础上再加一层新的跳跃节点,这层节点的密度又为第一层跳跃节点的一半。

list final

更直观点:

skip list 1

进一步限定每一层的跳跃节点都由它下一层的跳跃节点中产生,因此,我们的跳跃表最终看起来像是这样的。

skip list 2

我们不区分每一层是原节点还是跳跃节点,将最底下的那一层节点称为第一层节点,第一层节点上面为第二层节点,然后第三层…以此类推。

这样的结构,称之为跳跃表。假设每一层的节点数为下一层的一半,那么时间复杂度为O(logn)。

实现方案

如上所述,skip list是具有分层结构的有序链表,那每一层的节点应该如何产生呢?

我们可以在新增元素的时候使用随机方法决定这个元素有几层节点。设定该元素有且只有一层节点概率为1/2,有且只有两层节点概率为1/4,有且只有三层节点概率为1/8,以此类推。然后触发随机事件,当概率为1/2的事件发生时该元素有一层节点,概率为1/2的事件发生时该元素有两层节点…另外,我们限定一个跳跃表应该具有一个最大的层数限制。

假设一个跳跃表最大层数限制为4,那么可以设定一个整数区间为[1, 2^(4-1)],即[1, 8]。然后取一个1~8的随机数,当落在[5, 8]区间时有一层节点,落在[3, 4]区间时有两层节点,落在[2, 2]区间时有三层,落在[1, 1]上时有四层。由于我们设定了跳跃表的最大层数,因此概率等式1 = 1/2 + 1/4 + 1/8 + … + 1/2^n的最后两项相同。

Java实现

githup 代码, 见SkipList.java

Written on January 2, 2016