1.c++ splice 使用
2.简单说说ConcurrentSkipListMap

c++ splice 使用

       å¦‚果你想验证的话就把你第一次调用splice的语句用//注释调，然后把第二次调用的语句改成我给你写的那样，然后你就会得到你要的答案了

简单说说ConcurrentSkipListMap

       åŸºæœ¬ä»‹ç»

       è·³è·ƒè¡¨çš„性质如下：

       æœ€åº•å±‚的数据节点按照关键字key升序排列；

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

       é«˜çº§åˆ«ç´¢å¼•æ˜¯å…¶ä½Žçº§åˆ«ç´¢å¼•çš„子集；

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

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

源码分析核心字段分析

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

/***The源码必翻倍指标源码topmostheadindexoftheskiplist.*/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节点指向的数据节点为，节点的key比6节点的key大，此时需要执行如下代码：

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

       æ­¤æ—¶r节点指向的数据节点为5，5节点的key比6节点的key小，q、r节点向右移动，如下图所示

       æ­¤æ—¶r节点指向的数据节点为，节点的key比6节点的key大，同理需要往下级索引走，如下图所示：

       æ­¤æ—¶r节点指向的数据节点为，节点的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节点指向数据节点，节点的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 & 0x) == 0就给新插入的z节点创建索引，我们知道0x = 即最高位和最后一位为1，其余全部是0，

       æ¡ä»¶ï¼š(rnd & 0x) == 0什么时候成立？

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

       ä¸¾ä¸ªä¾‹å­ï¼šä¾‹å¦‚rnd = = 3条件就成立。

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

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

       é€šè¿‡while条件((rnd >>>= 1) & 1) != 0满足几次就创建几级索引。例如：

       rnd = 计算出来的level => 3

       rnd = 计算出来的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节点的索引一一删除完，最终的图下所示