今天在看redis的基本数据，结构时候，看到有一个跳跃表的数据结构，这之前我一直没听说过这种结构，于是先把redis的跳跃表结构的实现看了，然后他的名称是skiplist，这让我想起在java8的并发包下有带skiplist字样的2个实现类，我才明白，原来java也有这种数据结构，于是先百度了一些关于跳跃表的算法的原理，个人觉得下面这篇文章写的浅显易懂，对于入门可谓非常合适。先贴链接：http://blog.csdn.net/a1259109679/article/details/46442895。然后顺便看看java里面的这种数据结构是怎么实现的。
jdk8下有2个这种实现类，一个是本文介绍的ConcurrentSkipListMap，还有一个是ConcurrentSkipListSet，二者的区别在写本文之时还未阅读后者的源码。
这里需要先明白几个组成元素：node节点是真正用来存放我们存入的数据的，其中的key和value不必多说，同时还持有一个指向下一个node节点的指针。
index，这个对象有3个属性，第一个是一个node节点，第二个是down是指向下一个层级的index，right就是指向本层级的下一个index的指针。
头节点，第一个属性是代表所在的层级，跳跃表的快速定位依赖与此，然后还有一个指向下一个头结点的
下图是一个拥有12个node的分成2层的示意图，从图中蓝色的线表示一次寻找k7的过程，当然本次数据少，所以优势并未那么明显，但是如果数据量大的时候，能大大减少寻找次数。当然这里如果把一排node放在最先会更直观。
从上图可以看出，其实整个结构分为2块，一块是由我们的node的节点组成的基础数据，而另外一块是由一个多层level2组成的数据结构，且寻找过程总是从level最高的开始，然后先找到满足条件的最后一个index,然后通过index指向下一层对应的index,然后继续向右向下寻找，直到找到level1且满足了右边的node的key比我们需要查找的key大或者为null，然后进入到我们最先的node节点，然后去遍历链表。如下图所示
对整个结构以及寻找过程清楚以后，我们来看看源码中怎么样形成这个结构的。
首先来了解第一个API，put方法。put方法首先验证value为不为Null,也就是这不允许value为Null，这与map是不同的。真正做加入操作是交给我们的doPut方法操作的。如果度过spring的源码的同学知道，spring中很多的对外的API也都是做一个必要性验证，然后真正的操作都交给do**方法操作，而这一的方法一般要么是private的要么是protect的。
下面我们看doput方法。第三个参数是一个布尔值，从名字可以看到应该是一个仅仅在缺席时候加入，这里是不是可以猜测如果已经存在当前key，有2种操作，一种是修改，一种是加入。进来看这里首先验证了key不能为null，结合上一步的验证可以知道在我们这个跳跃表里是不允许键值为null.然后通过一个findPredecessor，传入当前新加入的key，和比较的方式来进行寻址。真正的寻找应该放在那里是在这里实现的。
findpredecessor从名字可以理解为寻找前辈，寻找前任。这个寻找过程是从最高level的headIndex开始的，然后先向右开始找，直到右为Null或者，右边Index的Node的key大于了当前需要加入的key为止，然后再向下寻找，同样也是直到下为null为止才是出口。通过一系列向右向下寻找，最后会落到我们的需要加入节点的前辈或者前任Node上，然后返回。
然后我们来看看找到这个前辈后我们做什么。首先取得这个前辈的next，如果它的下一个Next节点不为空的时候，我们继续依着这个next去继续向下寻找，直到下一个节点为空为止。这里看最后一个if判断，如果c为0（代表找到了一个key一模一样的node），然后判断onlyIfAbsent，一般情况下默认传入的是false，如果是false，则执行第二个CAS替换，如果为true则不会执行。这验证了我们前面的猜测。这里有多2个判断，主要是在并发下的一些判断吧。能够完全做到线程安全。
下面看看如果下个节点以后的做法，直接把我们新传入的key和value包装成node，然后通过cas来完成next指向，然后就加到了我们的链中去了。到目前为止，其实整个加入过程最终操作的是我们的第一块，也就是整个node链条。
下面我们看加入完成后还做了些什么？如果让你想，你认为接下来会干什么呢？到目前为止，我们整个数据结构是怎么建立的？对，应该到了拆分层次的过程了。在原来的跳跃表原理中拆分解释了随机的，也就是掷骰子的方式，这在常理看来是不是有点不靠谱啊，在java中呢？通过源码可以知道，java中也是随机的。不过这个随机是由线程生成的唯一一个数字与一个16禁止数字做与操作后的结果来决定的。看下图：如果通过判断为true后，首先将level设置默认为1，然后对rnd进行一个右位移操作后在与1进行与操作后来确定需要分为几层。具体为什么用这个算法，我看的时候也不大明白，等将来搞明白后在补上。然后通过多次对level++后，就确定了我们需要分成几层了。确定最终需要的层次后首先判断，需要分成的level与当前的最大level比较，如果比后者小的话，然后对小于level的每层初始化一个index，每层的node都指向新加入的node,down指向下一层的同样的自己，右侧全部初始化为null。其实也就是如果不需要扩大层的时候，为每层初始化一个这个index，然后准备加入到原来的index链条中去
如果需要扩容的话，首先确定的是每次是扩容一层，然后初始化一个对应的indxs的数组，然后为每层都创建包含新加入z的node，并且指向下一层的自己的index。然后通过for循环来进行扩层操作。扩容是从目前最高的那一层开始的，先加一层，包装一个node指向当前head的node指向的node，第二个参数是down指向当前的head，index指向刚刚创建的对应层次的index，以及最后一个确定层次的编号。这样就完成了一层中的headindex的创建。然后通过cas吧当前的head与新加入层的head进行替换。这里用语言描述的肯定有些头晕，我们下面用个图来讲述一下
但是我们发现完成了新加入，但是对于新加入的Node，只有最顶层建立了指针指向，其他层并未进行加入操作。接下来我们就要完成为每层加入index的操作。由名字可以看到就是插入层次的概念。
此时的h已经指向了我们最新的最高的层的headIndex，然后首先r指向第一个右侧index，如果这个index不为null,则先取出这个index的node，然后与当前新加入的key比较，拿到返回值额c，然后判断node的value不能为null，如果为null则先解除二者之间的关系，解除成功后从新建立right的指向，最后如果新加入的key比当前index的node的key大的话然后顺延继续找下一个index继续比较，下图1是横向的找，找到后进入第二个图。
然后判断如果当前是最顶层，则把最后的r指向新加入的Index。然后对标志的插入层进行减减操作，然后同时对j(也是当前插入层)，进行减减操作，且j必须必代表最高层的level小，然后把t指向了下一层(也就是为新加入的key包装的index，之前为每一层都建立一个且建立了down指向关系)。然后同样把headIndex和right同步下移。用文字描述同样比较苍白，用一张图来说明
黑色线代表当前操作，红色线代表完成建立关系后的操作，都开始指向下一层。
通过上面，就完成了新加入对象的寻址，分层，新关系建立的流程。
下面看remove方法，也很简单，是通过doremove完成的。
从renmove方法可以看出，即可以通过key移除，也可以通过同时满足key和value完成。
进来首先也是需要寻找到前key，这里一定是返回的是index所指向的node，也就是上一步一定是仅仅找到index，然后这里通过下面的代码继续向下寻找，找到后首先用CAS把value替换为null,然后判断是不是这层唯一的一个index，如果是的话就把这层给干掉。然后就完成了删除，从这里看出，它仅仅是把node的value设置为null或者删除掉本层。
size()方法，全局并没有维护一个总数，所以每次都会去遍历，这里的findFirst也就是直接找到第一个node，然后利用node的next去统计。最后最多能返回Integer.MAX_VALUE.这里在线程并发下是安全的
get方法，也是通过doGet方法完成的。这里不具体列代码了，也是很简单，通过findpredecessor方法定位到最近的index，然后继续顺延node去寻找定位返回。
replace方法是可以指定key和value来指定替换，也就是必须满足value是oldvalue。首先通过findNode找到对应的node。
读完这里也就完成了整个代码解读。但是这里肯定会有疑问，也就是移除操作，其实真正的移除操作都是在其他操作里借用判断value是不是为null来进行操作的。这里最重要的是helpdelete方法。其实很简单，就是一个链条解除的关系。
