跳表SkipList
Last updated
Last updated
SkipList是基于链表的数据结构，且是一种多层次的链表结构。它通过容许一定的数据冗余，达到 “以空间换时间” 的目的。
我们从单链表开始，看看跳表是怎么得来的。
以下是一个有序单链表
假如要从该有序单向链表中搜索元素 < 19, 41, 91 > ，因为链表不能使用二分查找，只能从表头遍历对比，所以需要比较的次数分别为 < 3, 5, 8>。
最后这个3层的链表，就是跳表的雏形了。
跳表的主要性质或者定义如下：
(1) 由很多层结构组成，level是通过一定的概率随机产生的； (2) 每一层都是一个有序的链表，默认是升序； (3) 最底层(Level 1)的链表包含所有元素； (4) 如果一个元素出现在Level i 的链表中，则它在Level j（j < i） 的链表也都会出现； (5) 每个节点包含两个指针，一个指向同一链表中的下一个元素，一个指向下面一层的元素；
查找
(1) 比较13，目标比13大，往后面找
(2) 比较41, 目标比41大，比链表最大值106小，则从41进入下面一层，从41的下一个元素开始找
(3) 比较77, 目标比41大，比链表最大值106小，则从77进入下面一层，从77的下一个元素开始找
(4) 比较91，目标与之相等，结束
插入
先确定该元素要占据的层数 K（采用丢硬币的方式，即随机），然后在Level 1 ... Level K 各个层的链表都插入元素。
删除
在各个层中找到要删除的节点，然后各层分别删除该节点。
TODO
在上面的实现中，节点存储的是单值，但是假如我们已经知道了拿到了一个节点，又为什么费劲周折去跳表中寻找它呢？
其实，跳表的实际应用中，节点存储的是键值对<key, value>，一般会根据key，来查找节点，以便获取节点的value。
如果不考虑排序问题，HashMap是查找速度最快的，如果考虑排序（按照key），则可以使用TreeMap，此时跳表的唯一优势可能就是实现起来比较简单。
但是在并发的情况下，如果仍然使用红黑树这种结构，由于红黑树的平衡操作要求对整个树形结构的锁定，性能明显不会很高。所以，Java的中并没有TreeMap的并发版本，但是有基于跳表这种数据结构实现的支持排序的并发<K, V>容器ConcurrentSkipListMap。其目的就是为了替代基于平衡树形结构的索引数据结构。
现在，我们将<13, 19, 53, 91>提取出来，在原始链表上加上一层链表，如下所示：此时，从该有序单向链表中搜索元素 < 19, 41, 91 >，先从上层查找，19和41恰好都在上层，分别查找2次和3次即可。对于91，在上层需要依次比较13>19>41>77，此时77仍小于目标91，当比较到106时，发现目标91小于106，则从77这个节点进入下一层，进入下一层后继续向右比较，所以一共需要比较6次。即通过建立上层索引，查找<19, 41, 91>需要查找的次数为<2, 3, 6>，比原来的< 3, 5, 8>次数要少很多。
现在，我们将<13, 41, 106>提取出来，在上层再加上一层链表，如下所示：此时，从该有序单向链表中搜索元素 < 19, 41, 91 >，按照上面的规则，可知次数为<2, 2, 6>，相比<2, 3, 6>，次数又减少了。
以上面查找91为例：整个过程如下：
