从零单排JavaConcurrency,SkipList&ConcurrnetSkipListMap

感概

好久没有写博客，自从上次已经有7,8个月了吧，在7,8个月里面接触的东西，学习到的东西也挺多的，由于没有写博客，或者是缺少总结的原因，很多东西都慢慢地遗忘了。还有就是时间确实不够，时间从来就没有够过。不管了，从这次开始要慢慢地拾起这些东西，慢慢地做出些改变。

概述

这次给大家带来的 ConcurrentSkipListMap, 首先它是一个线程安全的Map, 这个就类似于ConcurrentHashMap, 可以用于并发的场景，其次它保证了绝大多数操作都在O(log(n))之类完成，并且它还保证 存储的顺序，可以设置Comparator来做Key的排序，这些好处都来源于 Skip List, 俗称跳表。

跳表介绍

Skip List是 William Pugh 在1989年创建出来的(又见一个位神牛), 主要的目的就像他描述的那样，是用来替代平衡树的。跳表是一种随机性的数据结构，相对于平衡树来说，跳表更加的简单，能一口气实现红黑树,AVL这样的平衡树的人，还是太少了，而且内部确实复杂，调试, 用起来太麻烦。 同样跳表还可以做到平衡树那样的查找时间，特别是在并发的场景下面，由于红黑树的插入或者删除会做rebalance这样操作，那么影响的数据就会变多，锁的粒度就变大。但是跳表的插入或者删除操作影响的数据会很小，锁的粒度就会小，这样在大数据量的情况下，跳表的性能自然就会比红黑树要好。

跳表细节

先看下面这张图：

这就是一个跳表，看图说话可以得到的是底部是含有所有元素的链表，并且是有序的。 设想我们如果需要在一个有序的链表上查找一个数，一般的做法就是顺序遍历一下列表，然后拿查找的元素来比较各个存在元素，时间复杂度为O(n)

后来二分查找出现了，先选取中间的元素来判断，如果大于就抛弃左边的，直接进入右边进行比较，时间复杂度为O(logn). 其实跳表也是利用了这样的特性(找出一个合适的值来跟当前值进行比较，不一定就是中间值)，概率性抽取一部分数字提取出来，优先做比较，假设这个概率为p, 抽取一层过后，又抽取一层，直到最后只剩首元素和最后的NIL. 就像上图一样： a. 我们有 20， 30， 40， 50， 70， 90 这样的数组 b. 假设P等于1/2概率, 就只有40, 70, 90中奖了，有幸升级了 c. 又来一次1/2概率, 就只有40中奖，有幸升级 d. 再来一次1/2概率, 40不幸没有升上去，这时候就到顶了。

那么来看下查找的过程是怎么样的 假设我们需要查找70，步骤如下：

• 首先从Top层出发，70 > 20, 并且 70 ！= NIL, 继续往下查找


• 到了第2层的20，然后发现 70 > 20, 这时候往右走，来到40的节点， 70 > 40, 但是70 ！= NIL，继续往下查找


• 到了第3层的40，然后发现70 > 40, 继续往右边走，这时候来到 70，发现 70 = 70，查找结束。

经过一堆长串公式得到，跳表的查找时间复杂度为 O(log(n)).

跳表的插入，其实整个插入的过程跟查找的过程类似，不一样的是，插入的元素肯定会出现在底部的链表中，所以当确定了插入的位置后，这时候会有个叫做“Coin Flip”的过程，丢硬币，就是根据概率公式(求出P那个)，那计算下这时候这个新的节点需不需要往上”升级”, 如果需要就往上升，不需要就算了。重复这个”Coin Flip”的操作，直到不”升级”，当然升级上去之后，也需要和当前这一层的元素前后连接起来。

删除操作，类似先找到该元素，然后把它和它上层的元素都进行删除。 不像平衡树一样，跳表并不能保证查找的最坏情况，而平衡树却保证最坏也是O(logn), 确实有可能性，coin-flips的过程会让跳表产生不平衡的结构，但是这种情况只有要” 被到家”才发生，并且在实际情况下，大家都会选择如此简单的跳表而不是平衡树。

跳表也有一些O(n)的操作，强制我们去遍历一次整个表，例如打印所有元素呀，算下size()之类的。

ConcurrnetSkipListMap的实现

其实ConcurrentSkipListMap的实现就是实现了一个无锁版的跳表，主要是利用无锁的链表的实现来管理跳表底层，同样利用CAS来完成替换。以后会带来无锁的设计实现。

Summary

简单介绍了跳表设计思想和应用，以及在高并发的情况下，优于平衡树的原因，所以跳表在并发计算领域出现了，redis, leveldb都用应用，并且在分布式里面可以利用跳表的无锁特性来实现优先级队列。跳表其实也是一种利用空间换取时间的方法，所以这里P 概率的选择，至关重要。