跳表是一种概率性的数据结构，是一种多层次的有序链表结构，可以用来替代平衡二叉树，下面这张图是跳表paper中的图片描述：
跳表是一种用空间换时间的数据结构，它的核心思想就在于高度，比如：
图中的跳表，总共有1，2，3，4，5个节点，1节点的高度为5，2节点为2，3节点为3，4节点为1，5节点为3。
为什么说跳表是概率性或者随机性的数据结构，原因就在跳表的高度是随机的，比如paper中给的例子，这段代码是用来计算插入节点的高度的。
高度默认为1，如果p的值为1/4，那么高度为2的概率便为1/4，高度为3便为1/8。
JDK中的跳表也是通过链表实现的，但JDK跳表的高度增加的概率要远比paper中要小的多。
JDK中的跳表类为ConcurrentSkipListMap，是线程安全的有序链表，链表的结点为Node。
Node存储数据，为key-velue对，和指向下一个节点的指针。
Index包含node节点，并保存向下和向右的指针。
HeadIndex继承自Index，保存跳表的高度，比如第一层高度为1，第五层高度为5。HeaderIndex是跳表的头节点，代表跳表的第一个节点，所有操作都是从HeadIndex开始的。
因为是概率性的（随机性的），所以以一个略极端的例子为例，例子中只有两个key，1和2。
当skipList.put("1","1")的时候，结构是这样的：
HeadIndex记录高度为1，node节点指向key为1的节点，因为高度为1，所以down和right都为空。node=1的节点next为空。
当继续skipList.put("2","2")的时候，需要找到放置2的节点，从headIndex入手，因为headIndex的down和right都为空，所以直接返回 key=1 的node，暂且称它为node1。
node1的next为空，所以直接将next设置为 key=2 的node，node2。（这个过程涉及到casnext的操作，其实JDK的跳表是设计成了线程安全的，所以所有的操作过程都有大量的cas操作，暂且忽略这些线程安全的细节）
这步完成之后，需要计算node2的高度，便是下面的代码
ThreadLocalRandom.nextSecondarySeed()方法是xorshift算法，返回的是32位的有符号整数。
if ((rnd & 0x80000001) == 0) ，0x80000001的二进制为10000000000000000000000000000001，也就是排除了负数和奇数，所以要达到调整高度的条件，概率便为1/4。
当前高度为1，高度想要变成2，那便需要rnd的倒数第二位为1，概率为1/2。
level=1的条件就是10000000000000000000000000000001，
level=2的条件就是10000000000000000000000000000011，
level=3的条件就是10000000000000000000000000000111，以此类推。
假设，put("2","2")的时候，rnd的数字刚好为10000000000000000000000000111111，通过上面的方法计算的高度刚为5，但HeadIndex记录的目前的高度为1，JDK也不会直接将高度扩展到5，而是2，看下面的代码：
JDK的跳表的高度概率
应该为条件概率
：P(2) = P(2|1)=(1/4*1/2*/1/2)，所以P(n) = 1/4*(1/2)^n。
假设node2计算出的高度为2，当前高度为，那么就需要增加高度，首先建立两层的Index，right都为空，第二层的Index的down为第一层的Index。
创建新的HeadIndex，level为2，down为level=1的HeadIndex，right为第二层的Index。
Redis的高度的索引是使用数组存储的，JDK的跳表是链表存储的。
Redis默认开辟了一个64的数组来保存高度，新增加节点时，节点的高度，JDK的实现是一层一层的增加的，Redis就是按照随机数算法算的高度。比如跳表当然高度为2，JDK新增节点的话最大高度为3，而Redis的最大高度也有可能为64（概率很低）。
在随机算法上也有些不同，redis每增加一层都会调用一次随机数函数。
先看下Redis跳表的结构：
Redis的跳表为zskiplist，是跳表的根结构，保存头节点和尾节点两个节点，还有跳表的长度（节点的个数），还有跳表的高度。
Redis的跳表节点包含，一个char*字符串ele（旧版本sds为一个带长度的结构体，新版本就是字符串)，score就是用来比较顺序的字段，
backward是指向前面节点的指针。
zskiplistLevel 是高度元素，forward是指向下一个节点，span是这个节点距离下个的节点的个数。
首先创建一个zskiplist，高度为1，长度为0，尾节点为null。
创建头节点zskiplistNode，内容为null，score为0，前节点为null，level数组为64。
64个zskiplistNode初始化，后置节点为null，span为0
Redis获取到zkiplist，取header元素，根据zskiplist的当前高度循环遍历，当前高度为1，所以从level0开始遍历，level0的forward，也就是下一个节点为空，所以结束。
我们需要将score=1的节点加到它的后面，也就是需要加到header的forward。
第三步，添加加到header的forward，需要计算score=1的节点的高度。关键代码：
计算高度的函数是一个while循环，不停的调用随机函数，随机概率P为0.25，1/4。
所以，高度为1的概率为 (1-p)，高度为2的概率为p*(1-p)，高度为n的概率为p^n-1(1-p)。
Redis的高度概率函数基本与paper的方式相同。
假设计算得到的高度 level=3，大于目前skiplist的level，将zskiplist的高度设置为3。
将score=1的节点添加到header的forward中，循环遍历level0-level2，将forward指向当前节点。
找到zskiplist
拿到zskiplist的header节点，当前高度为3，遍历forward数组，从level2开始遍历，level2->level1->level0。
level2的forwared[2]不为空，为score=1的节点，并且score 5 >1 ，所以 header 节点变为 score=1 的节点。
score=1的level2的forward为空，继续往下找，寻找level1的forward，也为空，继续level0的forward，也为空，所以需要插入的地方就是score=1的节点。
创建新节点，计算score=5的高度，假设高度为1，那么就将 score=1的节点的 level0 的forward指向 新节点。
如果再插入一个score=8的元素，高度为2，便是下面这样的结构：
另外在删除节点的时候，都会有调整高度的逻辑，Redis的跳表删除逻辑比较简单，比如在删除score=1的节点时，发现level2没有指向了，便可以降低高度。
但是JDK跳表删除节点比较复杂，因为涉及到线程安全所以有很多的细节，也是应用了一些论文的思想，可以仔细研究一下。
