跳表论文解读

跳表出现背景:

利用二叉树可以表示各种抽象数据类型,比如字典(TreeMap)和有序列表.当元素是随机插入时,这种数据结构可以拥有很好的性能.但当元素是大量顺序插入时,这种数据结构会退化为线性时间复杂度.解决这种问题的一种方法是打乱元素顺序,但这样做在要求快速响应的场景下十分吃力.因此出现了平衡树的概念,平衡树通过不断平衡左右子树的高度来确保优秀的性能.而跳表,可以作为一种基于概率的平衡树的替代品,并且它拥有更简单的操作

跳表的实现思路:

考虑一种有序链表:

在这样一个链表中查找元素的时间复杂度为O(n).然而,当我们每两个节点都有额外加上的一个指针,这个指针指向它前面两个节点处的位置,即

那么在这样一条链表上查找元素的时间复杂度为O(n/2+1)

如果每四个节点都有一个指向前面四个节点处位置的指针,那么查找的时间复杂度将降低为O(n/4+2)

.以此类推,如果每2ⁱ个节点都有一个指向前面2ⁱ位置的指针,如下图,每个(2⁰)节点都有指向前面一个节点的指针(图中所有节点都有),每2个(2¹)节点都有指向前面两个位置处的指针(图中6,9,17,21,26节点有),每4(2²)个节点都有指向前面四个位置处的指针(图中9,21节点有),每8(2³)个节点都有指向前面八个位置处的指针(图中21节点有)

那么在这种链表中查找元素的时间复杂度为O(log2 n),一个拥有k个指针的节点被定义为k级节点,在这种数据结构中,50%节点 是level 1, 25% 节点是 level 2, 12.5%节点是level 3…但是,如果数据结构仅仅被设计成这样,进行查找是没有任何问题的,但进行插入和删除将变得不可实践.怎么解决这个问题呢?如果我们允许每个节点的level可以被随机选择,但是比例不变,会发生什么?那么,就有可能出现下面这种情况

降低了限制因素后(每个节点的level是固定的),插入和删除变得可行

跳表查找,插入,删除的具体实现

跳表的最大level被限制为小于MaxLevel这个常量,这个常量根据不同的数据量可以自由配置.而跳表的level等于此时跳表的最大level,比如一开始跳表的level是1.

首先是查找,我们通过遍历向前的指针来查找元素，指针指向的元素不能超出要搜索的元素。一旦当前指针无法取得更多进展时，搜索将向下移动一个级别。当我们无法在level 1上取得更多进展时，下一个节点必须就是要查找的节点(如果那个节点存在).下图为查找元素17所应该出现的位置

查找伪代码

插入和删除的操作与查找刚开始的步骤一致,只不过在查找的过程中需要维护一个update数组,这个数组的含义为:update[i]是在待插入/删除位置左边的所有level i节点中最右边的一个.一旦完成查找,就会对update[i]进行更新.下图展示了节点指针的更新

插入和删除伪代码

当我们插入一个节点时,会随机指派它的level,指派的方法为

p是一个分布因子,我们讨论的链表的p = 0.5
由于本篇只对跳表概念,原理进行入门讲解,关于p的设定和后序如何挑选search最佳开始的level,以及MaxLevel的选择, 请参考论文 Skip Lists: A Probabilistic Alternative to Balanced Trees

skiplist与平衡树、哈希表的比较

skiplist和各种平衡树（如AVL、红黑树等）的元素是有序排列的，而哈希表不是有序的。因此，在哈希表上只能做单个key的查找，不适宜做范围查找。所谓范围查找，指的是查找那些大小在指定的两个值之间的所有节点。

在做范围查找的时候，平衡树比skiplist操作要复杂。在平衡树上，我们找到指定范围的小值之后，还需要以中序遍历的顺序继续寻找其它不超过大值的节点。如果不对平衡树进行一定的改造，这里的中序遍历并不容易实现。而在skiplist上进行范围查找就非常简单，只需要在找到小值之后，对第1层链表进行若干步的遍历就可以实现。

平衡树的插入和删除操作可能引发子树的调整，逻辑复杂，而skiplist的插入和删除只需要修改相邻节点的指针，操作简单又快速。

从内存占用上来说，skiplist比平衡树更灵活一些。一般来说，平衡树每个节点包含2个指针（分别指向左右子树），而skiplist每个节点包含的指针数目平均为1/(1-p)，具体取决于参数p的大小。如果像Redis里的实现一样，取p=1/4，那么平均每个节点包含1.33个指针，比平衡树更有优势。

查找单个key，skiplist和平衡树的时间复杂度都为O(log n)，大体相当；而哈希表在保持较低的哈希值冲突概率的前提下，查找时间复杂度接近O(1)，性能更高一些。所以我们平常使用的各种Map或dictionary结构，大都是基于哈希表实现的。

从算法实现难度上来比较，skiplist比平衡树要简单得多。