基本介绍

跳跃表的性质如下：

最底层的数据节点按照关键字key升序排列；

包含多级索引，每个级别的索引节点按照其关联的数据节点的关键字key升序排列；

高级别索引是其低级别索引的子集；

如果关键字key在级别level=i的索引中出现，则级别level<=i的所有索引都包含该key。

跳跃表ConcurrentSkipListMap的数据结构如下图所示，下图一共有三层索引，最底下为数据节点，同一层索引中，索引节点之间使用right指针相连，上层索引节点的down指针指向下层的索引节点。

源码分析

核心字段分析

head 指向 node(BASE_HEADER) 的顶层索引。

/***Thetopmostheadindexoftheskiplist.*/privatetransientvolatileHeadIndex<K,V>head;

BASE_HEADER 头结点，即最顶层索引的头节点的value值

/***Specialvalueusedtoidentifybase-levelheader*/privatestaticfinalObjectBASE_HEADER=newObject()

Node 静态内部类，即数据节点

/***数据节点*/staticfinalclassNode<K,V>{finalKkey;//数据节点的keyvolatileObjectvalue;//数据节点的valuevolatileNode<K,V>next;//指向下一个数据节点/***Createsanewregularnode.*/Node(Kkey,Objectvalue,Node<K,V>next){this.key=key;this.value=value;this.next=next;}}

Index 静态内部类，即普通索引节点

/***普通索引节点*/staticclassIndex<K,V>{finalNode<K,V>node;//索引节点指向的数据节点finalIndex<K,V>down;//当前索引节点的正下方索引节点volatileIndex<K,V>right;//当前索引节点的右索引节点/***Createsindexnodewithgivenvalues.*/Index(Node<K,V>node,Index<K,V>down,Index<K,V>right){this.node=node;this.down=down;this.right=right;}}

HeadIndex 静态内部类，即当前级别索引的头节点

/***当前级别索引的头节点*/staticfinalclassHeadIndex<K,V>extendsIndex<K,V>{finalintlevel;//所处索引级别/***node：当前索引指向的数据节点*down：当前索引节点的正下方索引节点*right：当前索引节点的右索引节点*level：当前索引头节点所处的索引级别*/HeadIndex(Node<K,V>node,Index<K,V>down,Index<K,V>right,intlevel){super(node,down,right);this.level=level;}}

查询

根据指定的key查询节点，源码如下：

publicVget(Objectkey){//调用doGet方法returndoGet(key);}/***真正实现查询方法*/privateVdoGet(Objectkey){if(key==null)thrownewNullPointerException();Comparator<?superK>cmp=comparator;outer:for(;;){for(Node<K,V>b=findPredecessor(key,cmp),n=b.next;;){Objectv;intc;if(n==null)breakouter;Node<K,V>f=n.next;if(n!=b.next)//inconsistentreadbreak;if((v=n.value)==null){//nisdeletedn.helpDelete(b,f);break;}if(b.value==null||v==n)//bisdeletedbreak;if((c=cpr(cmp,key,n.key))==0){@SuppressWarnings("unchecked")Vvv=(V)v;returnvv;}if(c<0)breakouter;b=n;n=f;}}returnnull;}

在上述代码中，outer处的for自旋中，首先查看findPredecessor：查询指定key节点的前驱节点。该方法在下面的好多地方会调用，例如插入元素，删除元素以及删除元素对应的索引时都会调用。

findPredecessor方法源码如下：

/***作用1：找到key对应节点的前驱节点，不一定的真的前驱节点，也可能是前驱结点的前驱节点*作用2：删除无效的索引，即要删除节点时，将节点的索引也删除掉*/privateNode<K,V>findPredecessor(Objectkey,Comparator<?superK>cmp){if(key==null)thrownewNullPointerException();//don'tpostponeerrorsfor(;;){//r为q节点的右指针指向的节点，r为当前比较节点,每次都比较r节点的key跟查找的key的大小关系for(Index<K,V>q=head,r=q.right,d;;){if(r!=null){Node<K,V>n=r.node;Kk=n.key;//该节点已经删除，需要删除其对应的索引if(n.value==null){//该节点已经删除，需要删除其对应的索引if(!q.unlink(r))break;//restartr=q.right;//rereadrcontinue;}//当前查找的key比r节点的key大，所以r、q节点都向右移动if(cpr(cmp,key,k)>0){q=r;r=r.right;continue;}}//当q的下方索引节点为空，则说明已经到数据节点层了，需要退出进行后续查找处理if((d=q.down)==null)returnq.node;/***此时当前查找的key小于r节点的key，需要往下一级索引查找*d节点赋值为为q节点为正下方节点，即下一级索引的正下方节点*/q=d;r=d.right;}}}

findPredecessor方法的查找过程图示如下：假设要查找节点6

由于当前r节点的key比查询的key小，所以，r、q节点都向右移动，即执行如下代码：

//当前查找的key比r节点的key大，所以r、q节点都向右移动if(cpr(cmp,key,k)>0){q=r;r=r.right;continue;}

此时r节点指向的数据节点为10，10节点的key比6节点的key大，此时需要执行如下代码：

/***此时当前查找的key小于r节点的key，需要往下一级索引查找*d节点赋值为为q节点为正下方节点，即下一级索引的正下方节点*/q=d;r=d.right;

此时r节点指向的数据节点为5，5节点的key比6节点的key小，q、r节点向右移动，如下图所示

此时r节点指向的数据节点为10，10节点的key比6节点的key大，同理需要往下级索引走，如下图所示：

此时r节点指向的数据节点为10，10节点的key比6节点的key大，同理需要往下级索引走，但是此时下一级索引为空了，即(d = q.down) == null了，此时执行的代码如下， 返回q索引指向的节点，即返回节点5.

//当q的下方索引节点为空，则说明已经到数据节点层了，需要退出进行后续查找处理if((d=q.down)==null)returnq.node;

以上就是方法findPredecessor的查找流程，咱们接着继续看上面的doGet方法

/***Specialvalueusedtoidentifybase-levelheader*/privatestaticfinalObjectBASE_HEADER=newObject()0

首先初始化b、n、f三个节点，如下图所示

发现此时n节点指向的节点就是要查询的节点，于是执行如下代码：

/***Specialvalueusedtoidentifybase-levelheader*/privatestaticfinalObjectBASE_HEADER=newObject()1

直接返回n节点的value值。查询操作完成。

插入

跳跃表的插入操作分以下四种情况：

情况1：跳跃表内存在key一致元素，做替换

情况2：插入新元素，无须给新元素生成索引节点

情况3：插入新元素，需要给新元素生成索引节点，且索引高度 < maxLevel

情况4：插入新元素，需要给新元素生成索引节点，且索引高度 > maxLevel

源码如下：

/***Specialvalueusedtoidentifybase-levelheader*/privatestaticfinalObjectBASE_HEADER=newObject()2

首先还是跟查询操作类似，调用findPredecessor方法先查找到待插入key的前驱节点，举个例子，例如我们想要插入节点7，如下图所示：

接着跟查询操作一样的步骤如下，直接看图：

此时r节点指向数据节点1，节点1的key小于待插入的节点7的key，于是节点q、r同时向右移动。

此时r节点指向数据节点10，节点10的key大于待插入节点7的key，于是往下一层索引继续查找，执行的代码如下：

/***Specialvalueusedtoidentifybase-levelheader*/privatestaticfinalObjectBASE_HEADER=newObject()3

后面的操作类似

此时r节点的key大于待插入的节点6的key，但是q节点的down指针已为空，此时直接返回q节点指向的节点5。

接着回到doPut方法，先来查看outer循环，如下：

/***Specialvalueusedtoidentifybase-levelheader*/privatestaticfinalObjectBASE_HEADER=newObject()4

首先初始化三个节点b、n、f，n节点为b节点的下一个节点，而f节点为n节点的下一个节点，如下图所示

接着比较节点n与待插入的key的大小，此时n节点的key小于待插入节点的key，于是b、n、f三个节点均向下移动如下图所示

此时n节点的key大于待插入的key，此时执行如下代码，通过cas方式修改b节点的下一个节点为z节点，接着跳出outer循环。

/***Specialvalueusedtoidentifybase-levelheader*/privatestaticfinalObjectBASE_HEADER=newObject()5

然后我们知道doPut剩下的代码无非就是判断是否给新插入的节点z创建索引，如果需要创建对应的索引。

首先通过int rnd = ThreadLocalRandom.nextSecondarySeed();计算出一个随机数，接着进行如下判断：

/***Specialvalueusedtoidentifybase-levelheader*/privatestaticfinalObjectBASE_HEADER=newObject()6

如果rnd & 0x80000001) == 0就给新插入的z节点创建索引，我们知道0x80000001 = 000 0000 0000 0000 0000 0000 0000 0001即最高位和最后一位为1，其余全部是0，

条件：(rnd & 0x80000001) == 0什么时候成立？

rnd这个随机数最低位和最高位同时是0的时候，条件成立，概率是1/4

举个例子：例如rnd = 0000 0000 0000 0000 0000 0000 0000 0110 = 3条件就成立。

如果条件成立的话，接着计算到底给z节点创建几级索引，代码如下：

/***Specialvalueusedtoidentifybase-levelheader*/privatestaticfinalObjectBASE_HEADER=newObject()7

通过while条件((rnd >>>= 1) & 1) != 0满足几次就创建几级索引。例如：

rnd = 0000 0000 0000 0000 0000 0000 0000 0110计算出来的level => 3

rnd = 0000 0000 0000 0000 0000 0000 1111 1110 计算出来的level => 8

然后接着比较计算出来的z节点的索引跟现有的跳跃表的索引级别大小。

情况一：z节点计算出来的索引level比跳跃表的level小

情况二：z节点计算处理的索引level比跳跃表的level大。此时会选择最终的level为原来的调表的level + 1

情况一

给z节点创建索引的步骤如下图所示，此时z节点的索引还没有加入跳跃表现有的索引队列中

接着继续执行splice循环，代码如下：

/***Specialvalueusedtoidentifybase-levelheader*/privatestaticfinalObjectBASE_HEADER=newObject()8

初始化q、r节点如下图所示

此时r节点的key比新插入z节点，即7节点小，于是两个节点q、t都向右移动如下图所示

此时r节点的key比新插入z节点，即7节点大，执行如下代码：

/***Specialvalueusedtoidentifybase-levelheader*/privatestaticfinalObjectBASE_HEADER=newObject()9

此时r节点的key比新插入z节点，即7节点小，于是两个节点q、t都向右移动如下图所示

此时r节点的key比新插入z节点，即7节点大,同理，直接看图

情况二

跟情况一类似，这里就不一一画图了

删除

删除方法完成的任务如下：

设置指定元素value为null

将指定node从node链表移除

将指定node的index节点 从 对应的 index 链表移除

/***数据节点*/staticfinalclassNode<K,V>{finalKkey;//数据节点的keyvolatileObjectvalue;//数据节点的valuevolatileNode<K,V>next;//指向下一个数据节点/***Createsanewregularnode.*/Node(Kkey,Objectvalue,Node<K,V>next){this.key=key;this.value=value;this.next=next;}}0

同样，首先通过findPredecessor方法查找到要删除key的前驱节点，就不一一画图了，直接看找到的前驱节点的图，如下：

接比较n节点的key与待删除的key的大小，此时n节点的key小于待删除的key，即7节点的key，于是将b、n、f三个节点都向右移动，如下图：

此时n节点的key跟待删除的key一样，于是执行如下代码：

/***数据节点*/staticfinalclassNode<K,V>{finalKkey;//数据节点的keyvolatileObjectvalue;//数据节点的valuevolatileNode<K,V>next;//指向下一个数据节点/***Createsanewregularnode.*/Node(Kkey,Objectvalue,Node<K,V>next){this.key=key;this.value=value;this.next=next;}}1

最后再调用findPredecessor清楚无效的索引，即上面删除的节点的索引。

/***数据节点*/staticfinalclassNode<K,V>{finalKkey;//数据节点的keyvolatileObjectvalue;//数据节点的valuevolatileNode<K,V>next;//指向下一个数据节点/***Createsanewregularnode.*/Node(Kkey,Objectvalue,Node<K,V>next){this.key=key;this.value=value;this.next=next;}}2

重点靠如下代码块删除索引的：

/***数据节点*/staticfinalclassNode<K,V>{finalKkey;//数据节点的keyvolatileObjectvalue;//数据节点的valuevolatileNode<K,V>next;//指向下一个数据节点/***Createsanewregularnode.*/Node(Kkey,Objectvalue,Node<K,V>next){this.key=key;this.value=value;this.next=next;}}3

我们知道在上面已经将待删除的7节点的value置为null了，直接看图：

此时r节点的key小于待删除节点的key，于是r、q节点都向右移动。

此时r,n节点指向的数据节点的value值为null于是执行上面的q.unlink(r)代码，将q的右指针指向r的右指针指向的节点，即就是删除了该level上的7节点的索引节点，如下图所示

此时r节点的key大于待删除节点的key，于是往下一索引走，如下图所示

此时r节点的key小于待删除节点的key，于是r、q节点都向右移动。

此时r,n节点指向的数据节点的value值为null于是执行上面的q.unlink(r)代码，将q的右指针指向r的右指针指向的节点，即就是删除了该level上的7节点的索引节点，如下图所示

后续操作同理，最终将7节点的索引一一删除完，最终的图下所示