skip list原理与实现
May 25, 2022
原理 #
跳表作为一个没有被正规教材收录的数据结构，在工业场景下的用途非常广泛，常常用来媲美红黑树等一系列平衡二叉查找树。其核心的原理是通过多级索引层层二分构建一个支持二分查找的有序链表。
有序链表无法进行二分查找的原因在于无法随机访问，一个完美的跳表应该类似一个平衡二叉树的模样。
我们通过间隔一个选一个点复制出来，构成一个一级索引，针对一级索引链表，再通过间隔一个的方式构建二级索引，以此类推，最多$$log_2 n$$层就可以只剩两个点，这就是一个极其类似平衡二叉查找树的结构。查询的复杂度必然也是$$$log_2 n$$$。
但是上述的结构在insert和delete的时候动态调整的代价非常大，甚至无法通过log级别的复杂度完成。因此在实现的时候，并没有按照这个完美的结构来实现。而是采用了一个随机化抽点的方式来构建索引。事实验证的效率是令人满意的。
顺带提一下空间复杂度，虽然复制了一些点，但是依然是$O(n)$的复杂度，计算方式非常简单。并且索引部分并不需要记录完整的数据，只需要记录用于比较大小的score即可，因此索引与数据节点之间的空间比起来微不足道了。
实现原理 #
我们定义最底层的链表是原始的有序链表，向上一层为一级索引，再上一层为二级索引，以此类推。
我们基于完美形态的跳表可以发现，一级索引的点数为$n$， 二级索引点数为$n/2$, 三级索引的点数为$n/4$, 换个角度来看，一个点出现在一级索引中的概率是1， 出现在二级索引中的概率是1/2， 出现在三级索引中的概率是1/4。因此在插入数据的时候，我们只要按照概率分布，随机出这个点需要出现在哪几级索引中，然后按照索引层去查找和插入即可。
如何随机出一个点需要被插入的索引层？直接看代码：
// 该 randomLevel 方法会随机生成 1~MAX_LEVEL 之间的数，且 ：
// 1/2 的概率返回 1
// 1/4 的概率返回 2
// 1/8 的概率返回 3 以此类推
private int randomLevel() {
int level = 1;
// 当 level < MAX_LEVEL，且随机数小于设定的晋升概率时，level + 1
while (Math.random() < 0.5 && level < MAX_LEVEL)
level += 1;
return level;
}
代码的逻辑非常简单：
- 第一次循环有1/2的概率退出，则level=1 的概率是1/2；
- 第二次循环有1/2的概率退出，则level=2 的概率是1/2 * 1/2 = 1/4；
- …
针对返回的结果，有一点需要说明：
- 当函数返回1的时候，我们只需要添加原始节点即可；
- 当函数返回2的时候，我们需要将其添加到一级索引中，但是此刻的概率是1/4；与我们前文讲的1/2概率作为一级索引不符。
上述问题是一个不容易发现的隐藏bug，如果不是这样实现或许会导致跳表的体积膨大，索引膨胀一倍。
原因很简单，因为如果当我们返回1的时候，我们要构建一级索引，当我们返回2的时候，我们构建二级索引的同时也会新增一级索引节点，因此导致当返回值>=1 的时候都会出现一级索引点。则一级索引的实际概率是1， 而不是1/2.
那么按照上述正确的方式来处理，只有当level > 1 的时候才会产生一级索引点，而这个概率是1/2， 满足设计需求。当level > 2 的时候会产生二级索引点，其概率是 1/2 - 1/4 = 1/4。
由此，跳表的全部实现逻辑就结束了。
性能对比 #
百万次随机写入与std::map对比， 速度降低为map的1/3， 但是空间占用是map的3倍
- map: 1100 ms
- skipList: 380 ms