跳表也叫跳跃表，是一种动态的数据结构。如果我们需要在有序链表中进行查找某个值，需要遍历整个链表，二分查找对链表不支持，二分查找的底层要求为数组，遍历整个链表的时间复杂度为O(n)。我们可以把链表改造成B树、红黑树、AVL树等数据结构来提升查询效率，但是B树、红黑树、AVL树这些数据结构实现起来非常复杂，里面的细节也比较多。跳表就是为了提升有序链表的查询速度产生的一种动态数据结构，跳表相对B树、红黑树、AVL树这些数据结构实现起来比较简单，但时间复杂度与B树、红黑树、AVL树这些数据结构不相上下，时间复杂度能够达到O(logn)。
如何理解跳表？
要理解跳表，我们先从有序链表开始，对于上图中的有序链表，我们要查找值为150的节点，我们需要遍历到链表的最后一个元素才能找到，用大O表示时间复杂度就为O(n)。时间复杂度比较高，有没有优化空间呢？答案是肯定的，我们采取空间换时间的概念，对链表抽取出索引层，比如每两个元素抽取一个元素构成新的有序链表，这样索引层的有序链表相对底层的链表来说长度更短、间距更大，改造之后的链表入下图所示：
我们在新的链表中查询150，先从最上层Level3开始查找，遍历Level3有序链表，遍历两次就查询到了150这个节点。相对于初始链表来说，改造后的链表对查询效率有了不少的提升。
改造后的链表就是跳表，跳表采用的是以空间换时间的概念，将有序链表随机抽出好几层有序链表，查找的时候先从最上层开始，然后一直下沉到最底层链表。
现在我们对跳表有了一定的认识，总结一下跳表的性质：
由很多层结构组成每一层都是一个有序的链表最底层(Level1)的链表包含所有元素如果一个元素出现在Leveli的链表中，则它在Leveli之下的链表也都会出现。跳表的实现
跳表一般使用单链表来实现，这样比较节约空间。我使用双向链表来实现跳表，因为双向链表相对单向链表来说比较容易理解跳表的实现。
链表定义//头节点privatefinalstaticbyteHEAD_NODE=(byte)-1;//数据节点privatefinalstaticbyteDATA_NODE=(byte)0;//尾节点privatefinalstaticbyteTAIL_NODE=(byte)-1;privatestaticclassNode{privateIntegervalue;//上下左右节点privateNodeup,down,left,right;privatebytebit;publicNode(Integervalue,bytebit){this.value=value;this.bit=bit;}publicNode(Integervalue){this(value,DATA_NODE);}}跳表的搜索
跳表的搜索从最上层开始查询，最开始的节点p指向最顶层的head节点，如果p.right.value小于等于带查询元素，则p指向p.right，否则指向p.down。直到p.down为空，返回该节点。
跳表查找示意图：1）p=head，head.right.value=15,15<30,继续往右边查找，p=head.right
2）p.right.value=150，150>30，往下一层查找,p=p.down
3）p.right.value=30，30=30，继续往右边查找,p=p.right
4）p.right.value=150，150>30，往下一层查找,p=p.down
5）p.right.value=50，50>30，由于p.down为空，所以就返回该节点
代码实现/***通用查找*查找出最后一个小于该元素或者等于元素的节点*@paramelement 待查找的数*@return*/privateNodefind(Integerelement){Nodecurrent=head;for(;;){while(current.right.bit!=TAIL_NODE&¤t.right.value<=element){current=current.right;}if(current.down!=null){//找到最底层节点current=current.down;}else{break;}}returncurrent;//current.value<=element<current.right.value}/***获取某个元素*@paramelement *@return*/publicIntegerget(Integerelement){Nodenode=this.find(element);return(node.value==element)?node.value:null;}跳表的插入
理解了跳表的查找后，在来看跳表的插入就相对来说比较简单，我们先找出最后一个小于等于插入值的节点，我们将值插入到该节点的右边。除了最底层链表上的插入外，每个新插入的节点都会有一个随机的层高，我们还需要维护层高之间的节点关系，因为新节点的左边第一个元素不一定有层高，所以我们要往左边查找到第一个node.up不为空的节点，维护节点之间的关系，然后将节点作为新的节点，继续往上加层。
我们以值55，层高为2的新节点为例，演示索引建立的过程。１）我们先找出最后一个小于或者等于插入值的节点,即图中的node节点，然后将新节点插入到node的右边，即newnode节点。
２）node=50时，node.up为空，所以node=node.left
３）node=30时，node.up不为空，此时node=node.up
４）此时node已经移到level2的30节点上，在node的右边建立indexNode节点，作为新插入值的lebel2层的索引
５）将indexNode节点作为新的newnode节点继续向上添加索引，由于我们新插入节点的层高为2,所以将结束循环，新增元素完毕。
代码实现/***添加元素*@paramelement*/publicvoidadd(Integerelement){//查找出前一个节点Nodenode=this.find(element);//新建节点NodenewNode=newNode(element);//新节点与前后两节点建立关系newNode.left=node;newNode.right=node.right;node.right.left=newNode;node.right=newNode;intcurrentLevel=1;//建立索引层，随机建立层高while(random.nextDouble()<0.5d){//索引大于当前索引层if(currentLevel>=level){level++;//最顶层索引的头指针NodetopHead=newNode(null,HEAD_NODE);//最顶层索引的尾指针NodetopTail=newNode(null,TAIL_NODE);topHead.right=topTail;topHead.down=head;head.up=topHead;topTail.left=topHead;topTail.down=tail;tail.up=topTail;head=topHead;tail=topTail;}//一直往左边找到索引层while(node!=null&&node.up==null){node=node.left;}node=node.up;//新建索引节点，与当前左边节点建立关系NodeindexNode=newNode(element);indexNode.left=node;indexNode.right=node.right;indexNode.down=newNode;node.right.left=indexNode;node.right=indexNode;newNode.up=indexNode;//将索引节点作为新的节点，继续往上建立索引（如果有索引的话）newNode=indexNode;currentLevel++;//当前层高大于最高层高时，跳出循环if(currentLevel>MAX_LEVEL)break;}size++;}跳表的删除
跳表的删除就比较简单，找到该节点，从最底层开始删除，直到node.up为空。
代码实现/***删除跳表*@paramelement 待删除的元素*/publicvoiddelete(Integerelement){Nodenode=this.find(element);//没有找到该元素,直接返回if(node.value!=element)return;//删除元素，将元素的左右链表建立关系node.left.right=node.right;node.right.left=node.left;//判断是否有索引层，while(node.up!=null){node.up.left.right=node.up.right;node.up.right.left=node.up.left;node=node.up;}}跳表的时间复杂度
对于有序链表来说，时间复杂度为O(n),我们将链表改造成跳表之后，时间复杂度为多少呢？首先来分析对于有n个节点的链表，需要建立多少级索引？如果我们每两个节点会提取一个节点作为一个索引节点，那么第一级索引节点的个数为n/2，第二级索引节点的个数为n/4，依此类推，则第K级的索引节点的个数为n/(2^k)。
假设索引有h级，且第h级的索引节点个数为2，如下图所示。则我们可以得出n/(2^h)=2,这样可以得到h=logn-1（这里的log是指以2为底）,加上链表本身的一层，则整个跳表的高度为logn。我们在跳表中查询某个数据时，如果每一层都需要遍历m个节点，那么在跳表中查询某个数的时间复杂度为O(m*log(n))。
跳表的空间复杂度
比起单纯的单链表，跳表需要存储多级索引，肯定要消耗更多的存储空间。我们来看看跳表的空间复杂度，假设原始链表大小为n，每两个元素直接提取一个索引，那第一级索引大约有n/2个结点，第二级索引大约有n/4个结点，以此类推，每上升一级就减少一半，直到剩下2个结点。如果我们把每层索引的结点数写出来，就是一个等比数列。这几级索引的结点总和就是n/2+n/4+n/8…+8+4+2=n-2。所以，跳表的空间复杂度是O(n)。也就是说，如果将包含n个结点的单链表构造成跳表，我们需要额外再用接近n个结点的存储空间。
以上就是跳表相关的知识，我使用双向链表来实现跳表，相对来说能够更好的理解跳表的思想，在使用是用单链表实现就可以了，单链表比双链表节约空间。
示例代码：GitHub
如果您发现文中错误，还请多多指教。欢迎关注个人公众号，一起交流学习。
最后
打个小广告，金九银十跳槽季，平头哥给大家整理了一份较全面的Java学习资料，欢迎扫码关注微信公众号：「平头哥的技术博文」领取，祝各位升职加薪。
