跳表解析-基础篇
跳表是一个随机化的数据结构，实质就是一种可以进行二分查找的有序链表。跳表在原有的有序链表上面增加了多级索引，通过索引来实现快速查找。跳表不仅能提高搜索性能，同时也可以提高插入和删除操作的性能。
跳表用途
平衡树可以用于表示抽象的数据类型如字典和有序链表，它通过树旋转（Tree Rotation）操作强制使树结构保持平衡来保证节点搜索的效率。在数据为随机插入的情况下，平衡树性能表现良好；但数据为顺序插入或者需要删除节点的情况下，平衡树的性能就会有些糟糕。但是在并发场景下，平衡树由于需要旋转自平衡，因此在并发环境下性能和伸缩性并不好；
跳表可以作为平衡树的一种替代选择。它使用随机的平衡策略取代平衡树严格的强制的树平衡策略。因此它具有更简单有效的插入/删除方法以及更快的搜索速度，在并发场景下，跳表相对来说更加适用。
跳表详解
对于一个单链表来说，即使链表中的数据是有序的，如果我们想要查找某个数据，也必须从头到尾的遍历链表，很显然这种查找效率是十分低效的，时间复杂度为O(n)。
跳表的演进
我们可以对链表建立一级“索引”，每两个结点提取一个结点到上一级，我们把抽取出来的那一级叫做索引或者索引层，如下图所示，down表示down指针。
比如现在我们需要查找11这个元素，相对于有序链表是不是有了根快的查询速度！
同样地，一级索引也可以往上再提取一层，组成二级索引，如下：
这时候我们再查找11这个元素只需要经过1、9、11这几个元素就可以找到了。这基本上就是跳表的核心思想，其实这也是一个“空间换时间”的算法，通过向上提取索引增加了查找的效率。
跳表的插入
上边所讲的是跳表的查询，那对于跳表，我们应该如何插入一个元素？
eg:我们添加一个值为10的节点，首先我们会先根据一个随机算法获取到一个索引等级，这里比如level=2，然后找到10这个节点在下边两层对应的 前置节点，在其后边进行插入操作，如下图：
跳表的删除
eg:删除元素5，具体操作如下图：
标准化跳表
可以看到，上一级元素的个数是下一级的一半，这样每次减少一半，就很接近平衡二叉树了
时间复杂度
单链表查询的时间复杂度为O(n)，而插入、删除操作需要先找到对应的位置，所以插入、删除的时间复杂度也是O(n)
假设链表有n个结点，按照标准跳表结构，每两个结点都会抽出一个结点作为上一级索引的结点。
第一级索引的个数大约就是n/2,
第二级的索引大约就是n/4,
第三级的索引就是n/8,
依次类推，也就是说，第k级索引的结点个数是第k-1级索引的结点个数的1/2，那么第k级的索引结点个数为：n/2k
假设索引有h级，最高级的索引有2个结点，通过上面的公式，我们可以得到，从而可得：h =log2n-1 。如果包含原始链表这一层，整个跳表的高度就是。我们在跳表中查找某个数据的时候，如果每一层都要遍历m个结点，那么在跳表中查询一个数据的时间复杂度就为：O(m*logn)。
空间复杂度
比起单纯的单链表，跳表就需要额外的存储空间去存储多级索引。假设原始链表的大小为n，那么第一级索引大约有n/2个结点，第二级索引大约有4/n个结点，依次类推，每上升一级索引结点的个数就减少一半，直到剩下最后2个结点，如下图所示，其实就是一个等比数列。
这几级索引结点总和为：n/2 + n/4 + n/8 + … + 8 + 4 + 2 = n - 2。也就是说如果将包含n个结点的单链表构造成跳表，我们需要额外再用接近n个结点的存储空间。所以，跳表的空间复杂度为O(n)
降低跳表空间复杂度：
如果我们想要降低跳表的空间复杂度，可以将索引节点抽取的距离增大，上边的我们是按照标准的两个几点抽取一个节点作为上层索引，比如我们改成三个节点抽取一个节点作为上层索引:
通过等比数列的求和公式，总的索引结点大约是：n/3 + n /9 + n/27 + … + 9 + 3 + 1 = n/2。尽管空间复杂度还是O(n)，但是比之前的每两个结点抽一个结点的索引构建方法，可以减少了一半的索引结点存储空间。
实际上，在软件开发中，我们不必太在意索引占用的额外空间。在讲数据结构的时候，我们习惯性地把要处理的数据看成整数，但是在实际的软件开发中，原始链表中存储的有可能是很大的对象，而索引结点只需要存储关键值和几个指针，并不需要存储对象，所以当对象比索引结点大很多时，那索引占用的额外空间就可以忽略了。
跳表索引的动态更新
当我们不断地往跳表中插入数据时，我们如果不更新索引，就有可能出现某2个索引节点之间的数据非常多的情况，在极端情况下，跳表还会退化成单链表。
作为一种动态数据结构，我们需要某种手段来维护索引与原始链表大小之间的平衡，也就是说，如果链表中的结点多了，索引结点就相应地增加一些，避免复杂度退化，以及查找、插入和删除操作性能的下降。
如果你了解红黑树、AVL树这样的平衡二叉树，你就会知道它们是通过左右旋的方式保持左右子树的大小平衡，而跳表是通过随机函数来维护“平衡性”。
当我们往跳表中插入数据的时候，我们可以通过一个 随机函数，来决定这个结点插入到哪几级索引层中，比如随机函数生成了值K，那我们就将这个结点添加到第一级到第K级这个K级索引中。随机函数的选择是非常有讲究的，从概率上讲，能够保证跳表的索引大小和数据大小平衡性，不至于性能的过度退化。
跳表的性质
(1) 由多层索引组成，level是通过一定的概率随机产生的；
(2) 每一层都是一个有序的链表，默认是升序；
(3) 最底层的链表包含所有元素；
(4) 如果一个元素出现在Level i 的链表中，则它在Level i 之下的链表也都会出现；
(5) 每个索引节点包含两个指针，一个向下，一个向右；
(6) 跳表查询、插入、删除的时间复杂度为O(log n)，与平衡二叉树接近；
引用文献：
1.拜托，面试别再问我跳表了！
2.【数据结构与算法】之跳表（Java实现）—第九篇