深入理解什么是跳跃表
前言
前面的文章我们学习了性能高效的基于二叉搜索树的动态数据结构红黑树，其平均时间复杂度为O（logN），今天我们再来学习另外一种优秀的数据结构跳跃表，其综合性能与红黑树一样，而且功能更强大，从某种意义上来说是可以替代红黑树的。
什么是跳跃表
在介绍跳跃表之前，我们先来思考一个问题，如果现在我们要维护一组有序的整数序列，在支持高效的插入，删除和搜索的同时并能维护序列的有序性，那么应该采用什么什么数据结构？
首先哈希表应该被排除掉，虽然支持O(1)的增，删，查，但是HashMap不能维护有序性。
接着我们思考下使用数组怎么样，使用数组查询很快，但删除和新增比较慢，最坏情况下是O(N)的复杂度，所以也被排除掉。然后我们能想到的就是二叉查找树，但二叉查找树没有维持平衡性，最坏情况下依然是O(N)，所以也被排除掉，最后我们想到了二叉树里面的大佬，没错，它就是红黑树，它可以维持有序性，并且增，删，查都有不错的性能，目前看满足了所有的需求，但红黑树有一个缺点，不支持范围搜索，或者做不到高效的范围搜索，什么是范围搜索？简单点说就是 sql 里面 where 条件里面 between 3 and 100，查询一个区间的数据，数据库里面采用是B+树索引，所以可以支持，但这不是今天讨论的重点，除了B+树索引外，那么还有那种数据结构可以实现有序，支持高效的增，删，查，并支持区间搜索呢？
答案是肯定的，它就是今天的主角跳跃表，跳跃列表是一种数据结构。它允许快速查询一个有序连续元素的数据链表。跳跃表这种结构在Lucene，Redis，Leveldb等框架中都有应用，比如redis里面的zset结构，底层采用的就是跳跃表。
跳跃表的一些性质：
（1）一个跳表应该有几个层（level）组成；（2）跳表的第一层包含所有的元素；（3）每一层都是一个有序的链表；（4）如果元素x出现在第i层，则所有比i小的层都包含x；（5）第i层的元素通过一个down指针指向下一层拥有相同值的元素；（6）Head指针指向最高层的第一个元素。跳跃表图示如下：
如上图在level1层的链表是我们维护的有序序列，但单纯的链表虽然插入和删除可以做到O(1)级别的复杂度，但查询时间复杂度为O(N)，因为不像数组一样可以通过二分法搜索，那么有没有办法支持快速查询，其实是有的如上图，在底层链表之上，又新建了多级索引节点，有点类似于高速公路的多车道，最顶级的level就是快速通道，比如要检索30，在level3直接查到二次就定位到比25大，然后进入下一级中速跑道，又比较一次发现在最低级跑道，然后直接进入查询一次就定位到了，图中的数据数量不大，所以提升不明显，但如果在数据量不断加大的时候，跳跃表的性能优势就凸显出来了，此外由于底层的链表有序，在做范围检索的时候，只要找到开始节点，然后直接向后遍历到结束结点即可，效率非常高。那么跳跃表的时间复杂度究竟是多少呢？我们来分析下，在构建多级节点的索引时，理想情况下提取到极限时对于每一级的链表都是每两个节点之间提取一个索引节点，第k级的节点个数，等于第k-1级的一半，每次向下一级，都能排除一半的无效数据，这种方式类似于二叉查找树的查询，故时间复杂度为O（logN），空间复杂度为O（N），因为理想情况下，最底层每2个节点提取一个索引节点，相当于是n/2，n/4，n/8.....8，4，2把整个节点个数加起来就等于O(N)，到这里不难发现跳跃表其实是采用了空间换时间的策略来保证结构的高效。在最顶级的索引，一直到最低级的链表，整个搜索过程其实有点类似在不断跳跃，因此命名为跳跃表（Skip List）；
此外刚在说理想情况下，每2个节点提取一个，但实际操作中并不是按照这种方式来的，因为随着数据通过逐层比较的大量插入并下沉到最底级，原来上层的索引节点可能就不够用了，比如最早的上一级节点只有1和10000，但新增数据都分布在1和10000之间，如果还不选拔新的节点作为索引节点，那么性能将大打折扣，这时候需要从新插入的节点里面，选取一些节点向上构建索引层，那么应该构建多少级才算合适呢？
关于这一点，跳跃表的设计者采用了抛硬币的策略，也就是通过概率的方式来计算新插入的节点应该向上构建多少层索引，或者有没有机会成为索引节点。因为抛硬币的结果只有正反各占50%，相当于这个节点每向上多构建一级或者有资格成为索引节点，层层都只有50%的概率，如下面的一段代码：
private int getLevel(){ int level=1; while (true){ int r=random.nextInt(); if(r%2==0){ level++; }else { break; } } System.out.println("本次生成的level："+level); return level; }通过随机的奇偶数来模拟抛硬币的概率，如果遇到连续的偶数，就认为是向上跨级成功，但只要又一次出现奇数，就退出循环。如果一个新增加的节点，第一次就遇到了反面，抱歉这个节点就不能成为索引节点，只能放在最底层的链表中。那么我们来思考下，为什么要这样设计选拔的策略呢？
主要原因是因为作为一种动态的数据结构，其删除和添加的节点是不可预测的，而跳跃表又不能像平衡二叉树那样，可以通过染色或者旋转来维持平衡，所以在这种情况下，就需要一种概率随机化的方式来自动均衡跳跃表的多级索引，通过这种方式虽然不能完全保证跳跃表的均匀性，但总体上可以使得跳跃表趋于平衡，从而能够达到较高的综合性能。
跳跃表的操作
跳跃表的主要支持高效的操作如下：
（1）添加
（2）删除
（3）查找
（3）最小值
（4）最大值
（5）区间检索
（6）获取有序序列
这里面简单说下查找的步骤，查找的步骤从最高层开始，判断要查找的节点与当前链上的节点的大小做比较，如果下一个节点大于当前查找的节点，那么就需要从前一个节点上向下下沉一级继续做搜索，反复如此最终下降到最底层级，然后得到值返回，同理添加也类似，主要就是找到位置，然后根据概率规则判断是否让当前节点选拔为索引节点，如果是就要构建多级索引节点，在删除的时候也类似，如果这个节点在多级level里面都存在，那么就需要在所有的level里面进行删除，同时让其前驱节点连接到删除节点的后一个节点，这样就完成了删除。关于剩下的几个操作，其实比较简单，只要理解了查找就可以。
跳跃表的实现
跳跃表在实现上有两种方式，第一种采用链表实现，第二种采用数组实现，不管那种实现，代码相比红黑树的实现是非常简洁的，红黑树里面关于维持平衡的代码非常复杂，相比之下跳跃表的实现就更加轻松了。
采用多级链表的方式构建，每个节点中包含了当前节点的指针，以及向前，向下节点的指针，这种方式比较容易理解。但相对来说耗的空间会更大一点，因为除了O（N）空间复杂度外，还要包含多个指针来连接节点，其节点定义如下：
class Node{
public K key;//数据的key，通常情况下需要可比较排序
public V value;//数据的value
public long level;//记录当前节点的层级
public Node next;//水平方向上的下一个节点的指针
public Node down;//垂直方向上的下一个节点的指针
public Node(K key, V value, long level, Node next, Node down) { this.key = key; this.value = value; this.level = level; this.next = next; this.down = down; } }而数组实现的方式，则相对来说不容易理解，每个节点都包含了一个节点数组用来表示当前节点的下一个节点，同时这个数组还维持了多个层级的数据，而完成数据的查找，则是通过，数组的嵌套来获取的，故不容易理解，其节点定义如下：
public class Node{
private int value; private Node next[];//指向下一个节点，并维持多个层级数据 private int level;//跨越几层
public Node(int value, int level ){ this.value=value; this.level=level; this.next=new Node[level]; } }这里我给出使用链表实现的Java代码，完整的如下：
package data_structure.skip_list;
import java.util.ArrayList;import java.util.List;import java.util.Random;
/** * 跳跃表的一种实现方法，使用的是链表实现 * * https://github.com/dineshappavoo/SkipList/blob/master/src/skiplist/SkipList.java * https://github.com/kjiwa/java-skip-list/blob/master/SkipList.java * @param <K> * @param <V> */public class SkipList<K extends Comparable<K>, V> {
//head节点不存储实际数据，表示层级 private Node head; //构建随机数对象 private Random random; //当前已经添加的数量 private long size; //采用抛硬币的概率=0.5 private double p;
public SkipList(){ head=new Node(null,null,0,null,null); random=new Random(); size=0; p=0.5; }
/**** * 抛硬币策略决定新添加的数据，在第几层之下构建索引节点 * 利用0-1之间的随机数是否小于0.5作为概率事件，如果大于 * 0.5直接返回，否则就一直抛直到出现大于0.5概率事件，在 * 不断抛的过程，使用level计数，level最大受限于当前的节点个数， * @return */ private long level(){
long level=0; double randomNumber=random.nextDouble(); while (level<=size&&randomNumber<p){ level++; randomNumber=random.nextDouble(); } return level;
}
public void add(K key,V value){
//抛硬币决定当然节点要构建的索引节点的层级 long level=level(); //如果新构建的level大于原head的层级，需要使用新的层级作为head， //旧的head，作为新的down节点 if(level>head.level){ head=new Node(null,null,level,null,head); }
Node current=head; Node last=null;
while (current!=null){ //判断,下一个节点的key是否大于当前要插入的key if(current.next==null||current.next.key.compareTo(key)>0){ //在大于的情况下判断新节点的层级是否大于当前对比的层级 if(level>=current.level){ Node newNode=new Node(key,value,current.level,current.next,null); if(last!=null){ last.down=newNode; } //追加当前节点 current.next=newNode; last=newNode; } //下降一级更新 current=current.down; continue;
}else if(current.next.key.equals(key)){ //如果是等于，就更新值，然后返回 current.next.value=value; return; } //到这一步，说明新插入的值大于当前节点，那就继续向后遍历查询 current=current.next;
} //每新增一个节点，数量就加一 size++; }
public V serach(K key){
Node current=head; while (current!=null){ //如果next的值大于当前要查询的值，说明当前的值在左边，然后就下降，继续查找 if(current.next==null||current.next.key.compareTo(key)>0){ current=current.down; continue; //如果找到就返回 }else if(current.next.key.equals(key)){ return current.next.value; } //继续向后搜索 current=current.next; }
return null;
}
public V remove(K key){ V value=null; Node current=head; while (current!=null){ //判断是否在左边 if(current.next==null||current.next.key.compareTo(key)>=0){ //是的情况下，判断是否相等 if(current.next!=null&¤t.next.key.equals(key)){ //如果相等，就获取值 value=current.next.value; //然后将引用覆盖掉 current.next=current.next.next; size--; } //下沉继续处理 current=current.down; continue; } //继续向右查询 current=current.next; } return value; }
public boolean containsKey(K key){ return serach(key)!=null; }
//统计当前跳跃表的节点个数，，可以使用size属性代替 public long size(){ Node current=head; long count=0; //head不为null if(current!=null){ //一直下沉到最下面的一级 while (current.down!=null){ current=current.down; } //从左向右遍历统计 while (current.next!=null){ count++; current=current.next; }
}
return count; }
//查询最小值 public V findMin(){ Node current=head; if(current==null){ return null; } //下沉下去，最底层链表的第一个值 while (current.down!=null){ current=current.down; } return current.next.value; }
//查询最大值 public V findMax(){ Node current=head; if(current==null){ return null; }
while (current.next.next!=null){ current=current.next; }
while (current.down!=null){ current=current.down; }
while (current.next.next!=null){ current=current.next; }
return current.next.value;
}
/*** * 范围检索 * @param start * @param end * @return */ public List<V> findRange(K start,K end){
List<V> list=new ArrayList<>();
Node current=head; while (current!=null){ //如果next的值大于当前要查询的值，说明当前的值在左边，然后就下降，继续查找 if(current.next==null||current.next.key.compareTo(start)>0){ current=current.down; continue; //如果找到就返回 }else if(current.next.key.equals(start)){
Node temp=current.next; //搜索范围 while (temp!=null&&temp.key.compareTo(end)<=0){ list.add(temp.value); temp=temp.next; } return list; } //继续向后搜索 current=current.next; } return list;
}
public static void main(String[] args) {
SkipList<Integer,String> skipList=new SkipList<>();
skipList.add(3,"3"); skipList.add(1,"1"); skipList.add(11,"11"); skipList.add(16,"16"); skipList.add(4,"4"); skipList.add(2,"2"); skipList.add(8,"8");
System.out.println();// skipList.remove(4);// System.out.println(skipList.serach(4));// System.out.println(skipList.size);;// System.out.println(skipList.findMin());// System.out.println(skipList.findMax());
System.out.println(skipList.findRange(3,11));
}
class Node{
public K key;//数据的key，通常情况下需要可比较排序
public V value;//数据的value
public long level;//记录当前节点的层级
public Node next;//水平方向上的下一个节点的指针
public Node down;//垂直方向上的下一个节点的指针
public Node(K key, V value, long level, Node next, Node down) { this.key = key; this.value = value; this.level = level; this.next = next; this.down = down; } }
}总结
本文主要深入的介绍了跳跃表的相关原理和实现，跳跃表作为一种动态的数据结构，其综合性能和红黑树一样高效并支持范围检索，能做到这一点的目前的数据结构里面还有B+树，B+树的实现其实与跳跃表的结构比较类似，但B+树是通过树的方式组织的索引，不夸张的说，如果不考虑内存的占用情况，那么跳跃表是完全也可以替代B+树并实现B+树索引的所有功能的，但B+树作为文件系统索引，是专门针对磁盘系统作过优化的，尤其是通过一个节点可以有多个孩子的特征并结合了文件页page缓存，大大降低了树的高度，减少了查找磁盘的io次数，使得其比较适合数据量比较大的数据库系统，算是各有所长，总体来说跳跃表是一种非常优秀的数据结构，值得每一个开发者学习了解。