SkipList 跳表
介绍
skiplist本质上也是一种查找结构，用于解决算法中的查找问题（Searching），即根据给定的key，快速查到它所在的位置（或者对应的value）。
这种数据结构是由William Pugh发明的，最早出现于他在1990年发表的论文《Skip Lists: A Probabilistic Alternative to Balanced Trees》。有兴趣的可以阅读一下。
有序表的搜索
入坑先阅读帅地的公众号文章 《以后有面试官问你「跳跃表」，你就把这篇文章扔给他》
写的挺不错的文章。文章末尾附有代码
跳表具有如下性质：
- 由很多层结构组成
- 每一层都是一个有序的链表
- 最底层的链表包含所有元素
- 如果一个元素出现在 Level i 的链表中，则它在 Level i 之下的链表也都会出现。
- 每个节点包含两个指针，一个指向同一链表中的下一个元素，一个指向下面一层的元素。
总结
下面我们使用一些通用的标准对skiplis进行一下简单的评价：
是否支持范围查找
因为是有序结构，所以能够很好的支持范围查找。集合是否能够随着数据的增长而自动扩展
可以，因为核心数据结构是链表，所以是可以很好的支持数据的不断增长的读写性能如何
因为从宏观上可以做到一次排除一半的数据，并且在写入时也没有进行其他额外的数据查找性工作，所以对于skiplist来说，其读写的时间复杂度都是O(log n)是否面向磁盘结构
磁盘要求顺序写，顺序读，一次读写必须是一整块的数据。而对于skiplist来说，查询中每一次从高层跳跃到底层的操作，都会对应一次磁盘随机读，而skiplist的层数从宏观上来看一定是O(log n)层。因此也就对应了O(log n)次磁盘随机读。
因此这个数据结构不适合于磁盘结构。并行指标
终于来到这个指标了， skiplist的并行指标是非常好的，只要不是在同一个目标插入点插入数据，所有插入都可以并行进行，而就算在同一个插入点，插入本身也可以使用无锁自旋来提升写入效率。因此skiplist是个并行度非常高的数据结构。内存占用
与平衡二叉树的内存消耗基本一致。
应用
在Java的API中已经有了实现：分别是
- ConcurrentSkipListMap. 在功能上对应HashTable、HashMap、TreeMap。 在并发环境下，Java也提供ConcurrentHashMap这样的类来完成hashmap功能。
- ConcurrentSkipListSet . 在功能上对应HashSet.
HashMap是基于散列表实现的，时间复杂度平均能达到O(1)。ConcurrentSkipListMap是基于跳表实现的，时间复杂度平均能达到O(log n)。
ConcurrentHashMap不能排序，容器类中可以排序的Map和Set是TreeMap和TreeSet，但它们不是线程安全的。Java并发包中与TreeMap/TreeSet对应的并发版本是ConcurrentSkipListMap和ConcurrentSkipListSet
有兴趣的可以阅读《并发容器 - 基于SkipList的Map和Set / 计算机程序的思维逻辑》
最近学习HBase源码时发现HRegion在sotre管理上用到了跳表数据结构ConcurrentSkipListMap
延伸
skiplist里面一个最大的创新点，就是引入了一个新条件：概率。与传统的根据临近元素的来决定是否上推的avl或红黑树相比。Skiplist则使用概率这个完全不需要依托集合内其他元素的因素来决定这个元素是否要上推。
这种方式的最大好处，就是可以让每一次的插入都变得更“独立”，而不需要依托于其他元素插入的结果。 这样就能够让冲突只发生在数据真正写入的那一步操作上，而我们已经在前面的文章里面知道了，对于链表来说，数据的写入是能够做到无锁的写入新数据的，于是，利用skiplist,就能成功的做到无锁的有序平衡“树”（多层级）结构。
为了阐述清楚如何能够做到并发写，我们需要先对什么叫”一致性的写”，进行一下说明。
一般的人理解数据的一致性写的定义可能是：如果写成功了你就让我看到，而如果没写成功，你就不让我看到呗。
但实际上这个定义在计算机里面是无法操作的，因为我们之前也提到过，计算机其实就是个打字机，一次只能进行一个操作，针对复杂的操作，只能通过加锁来实现一致性。但加锁本身的代价又很大，这就形成了个悖论，如何能够既保证性能，又能够实现一致性呢？
这时候就需要我们对一致性的定义针对多线程环境进行一下完善：在之前的定义，我们是把写入的过程分为两个时间点的，一个时间点是调用写入接口前，另一个时间点是调用写入接口后。但其实在多线程环境下，应该分为三个时间点，第一个是调用写入接口前，第二个是调用写入接口，但还未返回结果的那段时间，第三个是调用写入接口，返回结果后。
然后我们来看看，针对这三个时间点应该如何选择，才能保证数据的一致性：
对于第一个时间点，因为还没有调用写入接口，所以所有线程（包含调用写入的线程）都不应该能够从这个映射中读取到待写入的数据。
第二个时间点，也就是写入操作过程中，我们需要能够保证：如果数据已经被其他线程看到过了，那么再这个时间点之后的所有时间点，数据应该都能够被其他线程看到，也就是说不能出现先被看到但又被删掉的情况。
第三个时间点，这个写入的操作应该能够被所有人看到。
已经定义好了一致性的规范，下面就来看看这个无锁并发的skiplist是如何处理好并发一致性的。
首先我们需要先了解一下链表是如何能够做到无锁写入的：
对于链表类的数据结构来说，如果想做到无锁，主要就是解决以下的问题，如何能够让当前线程知道，目前要插入新元素的位置，是否有其他人正在插入？ 如果有的话，那么就自旋等待，如果没有，那么就插入。利用这个原理，把原来的多步指针变更操作利用compare and set的方式转换为一个伪原子操作。这样就可以有效的减少锁导致的上下文切换开销，在争用不频繁的情况下，极大的提升性能。（这只是思路，关于linkedlist的无锁编程细节，可以参照A pragmatic implementation of non-blocking linked lists，这篇文章）
利用上面链表的无锁写入，我们就能够保证，数据在每一个level内的写是保证无锁写入的。并且，因为每一次有新的数据写入的时候其他尝试写入的线程也都能感知的到，所以这些并行写入的数据可以通过不断相互比较的方式来了解到，自己这个要写入的数据与其他并行写入的数据之间的大小关系，从而可以动态的进行调整以保证在每一层内，数据都是绝对有序的。
同一个level的一致性解决了，那么不同level之间的一致性是如何得到解决的呢？这就与我们刚才定义的一致性规范紧密相关了。因为数据的写入是从低层级开始，一层一层的往更高的层级推送的。而数据读取的时候，则是从最高层级往下读取的。又因为数据是绝对有序的，那么我们就一定可以认为，只要最低层级（level0）内存在了的数据，那么他就一定能够被所有线程看到。而如果在上推的过程中出现了任何异常，其实都是没关系的，因为上推的唯一目的在于加快检索速度，所以就算因为异常没有上推，也只是降低了查询的效率，对数据的可见性完全没有影响。
这个设计确实是非常的巧妙~
无锁完成多线程链表写入的算法，有兴趣的可以看看 cas （使用cas 实现无锁的skiplist）
C++版
参考链接