跳表SkipList
SkipList
概念
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 各个层的链表都插入元素。
删除
在各个层中找到要删除的节点，然后各层分别删除该节点。
SkipList的Java实现
TODO
为什么要有跳表
在上面的实现中，节点存储的是单值，但是假如我们已经知道了拿到了一个节点，又为什么费劲周折去跳表中寻找它呢？
其实，跳表的实际应用中，节点存储的是键值对<key, value>，一般会根据key，来查找节点，以便获取节点的value。
如果不考虑排序问题，HashMap是查找速度最快的，如果考虑排序（按照key），则可以使用TreeMap，此时跳表的唯一优势可能就是实现起来比较简单。
但是在并发的情况下，如果仍然使用红黑树这种结构，由于红黑树的平衡操作要求对整个树形结构的锁定，性能明显不会很高。所以，Java的中并没有TreeMap的并发版本，但是有基于跳表这种数据结构实现的支持排序的并发<K, V>容器ConcurrentSkipListMap。其目的就是为了替代基于平衡树形结构的索引数据结构。
参考
Last updated
