在前面的《jdk1.8的HashMap源码分析》文章已经给出HashMap中数组+链表这一部分的内容，本篇文章将剩余的HashMap里面红黑树及其相关操作源码进行解析，内容较多，因此单独放在一篇文章进行讨论。一、背景知识由于红黑树的插入、删除、扩容等操作相对复杂，因此建议先熟悉基本数据结构，例如二叉树、二叉搜索树及其关于它的查找、插入、删除操作、2-3节点树等。本人假定看此文章的同学已经具备基本的数据结构知识，因此，关于红黑树的背景知识，这里不再累赘。冷知识：红黑树为什么叫红黑？节点为什么被标记为红色和黑色， 可以改为蓝黄树、绿蓝树等吗？首先红黑树第一版在1972年由[Rudolf Bayer](https://baike.baidu.com/item/Rudolf Bayer/3014716)发明，当时的学名是平衡二叉B树（symmetric binary B-trees），还不是被称为Red Black Trees。后来平衡二叉B树在1978年被 Leo J. Guibas 和 Robert Sedgewick 修改为现在版本的红黑树，他们之所以称之为“红黑”树，因为他们在研究这种树型数据结构过程中，需要在草稿纸上作图，用的恰是红色笔和黑色笔，红黑笔非常方便给相关节点标记颜色以便可视化设计相关逻辑，因此“红黑树”的红黑来源于此。二、红黑树性质：以下5个性质结合基于序列3，7，11，15，19，23，27，31，35，构成的一棵红黑树进行理解（这里给出的是有序序列，其实即使原序列是无序的， 被重构成为红黑树后，在红黑树也会形成二叉树搜索树的有序序列）1、树上的所有节点都被标记颜色，节点可以被标记位黑色，也可以被标记为红色，2、root根节点必须被标记为黑色3、所有的叶子节点都被标记为黑色，而且是NIL节点（需要注意：在JDK1.8的HashMap中，没有NIL命名的节点，也不是所谓的用null来表示NIL节点，在分析原理上可以将其当做虚构的null节点来对待，不影响结构，在平常作图中，NIL叶子节点可以忽略，在这里只是为了说明红黑树有NIL这种设计，因此在图中显式画出）4、每个被标记为红色的节点，它的两子节点一定都是黑色第4点也可以推出这样的结论：两个红节点一定不会直接相连，也即：红色节点与红色节点不能直接连接，或者说，红色节点的父节点及其子节点都不能是红色节点5、任一节点到每个叶子结点的路径都包含数量相等的黑色节点，俗称：黑色平衡或者黑高，BlackHeight，如 下图的5条路径，每条路径经过黑色节点数都是2，NIL节点不作为黑色节点计数。以上5条特点也是红黑树的构成规则优势：（1）自平衡。红黑树从根到叶子的最长路径不会超过最短路径的2倍，解决了二叉查找树容易不平衡的缺陷（在某些情况下会退化成一个线性结构），提高了读取性能（树越平衡，读取性能就越好）。（2）虽然AVL树具有更高的读取性能（因为平衡性更好），但是当插入或删除节点时，AVL树要复杂很多，红黑树在插入或删除节点方面具有更高的效率。在什么情况下需要变色，在什么情况下需要旋转？在红黑二叉树中插入节点或删除节点后，如果破坏了红黑树的规则（也就是上述的特性），则需要对修改后的红黑树进行调整，使其重新符合红黑树的规则。首先是变色（往往需要多次变色，一次改变一个节点的颜色），当变色无法使得当前红黑树平衡时，就使用左旋或者右旋，旋转一次之后，然后再继续多次变色，如此反复循环，直到修改后的红黑树重新符合规则。三、为何要对红黑树进行变色、左旋、右旋操作？1）首先若要生成一棵符合红黑树特点的红黑树，那么必然需要插入一定的节点（插入过程就包含了变色、左旋、右旋操作），从而构成一棵“固化平衡”的红黑树，如果已经构成这颗红黑树不再对其插入新节点或者删除节点，则无需再对其进行各种方式的调整。2）对于一棵已经存在的红黑树，若要对其再插入新节点或者删除节点操作，那么这些操作可能会破坏红黑树的平衡约束，导致插入节点或者删除节点之后的“红黑树”不是一棵“平衡”的红黑树，那么怎么办？这么办：根据红黑树的特点，需要额外设计一些补充操作来使得插入节点或删除节点之后的“不正常红黑树”变成正常的、平衡的红黑树，发明者经过研究，其实这些额外的操作无非就三种：变色、左旋、右旋3）为何会有变色（颜色改变）操作？举个特殊例子，对于序列3，7，11，15，19，23，27，31，35当插入首个节点3时。如下图所示：（需要明确的的一点是：红黑树的待插入节点必须先标记位红色。）这张图会让体现出：红黑树的平衡维护在视觉上好像也需要这样的变色操作。4）为何会左旋操作？在这里暂且不深入论证左旋操作，看下面的图简要说明：可能有人会问，为何在最后需要将3节点黑色变成红色？可以保持红色吗？将黑3改为红3，本质是为了这颗树看起来更加平衡，而且是黑色平衡，同时在未来的不断插入、删除节点条件下形成的红黑树也会持续保持“优良传统”的树平衡，若节点3改为红色，在之后不断插入节点、不断调整红黑树结构的条件下最终得到的树将不是一棵符合红黑树特点的树，那么这个“无名树”也无法实现像红黑树的所有性能。5）为何会右旋操作？插入3节点，若不进行右旋，树的重心会偏向左边，看起来不平衡，通过右旋，树看起来平衡多了（其实是防止树结构变成长链表形状）正是对一棵树建立“变色、左旋、右旋”的约束机制，使得该树结构符合我们期望的性能。四、红黑树左旋、右旋完整操作第三节的内容则给出相对节点的结构，有助于理解红黑树是通过不断变色、左旋、右旋操作，以维持自身树的平衡，最终实现高效的查询、插入、和删除性能，因此掌握红黑树的5点特点对于红黑树所有操作才能真正理解。在解释完整左旋和右旋操作前，先做以下基本约定，如下图所示：以下约定是从l节点、r节点的视角来看其他位置节点的角色，l：left的缩写，r：right的缩写pp节点：l节点、r节点的祖父节点（Grand parent node）p节点：l节点、r节点的父节点（parent node）l节点：p节点的左节点（或左子节点）r节点：p节点的右节点（或右子节点）ll节点：l节点的左子节点lr节点：l节点右子节点rl节点：r节点左子节点rl节点：r节点右子节点4.1 理解左旋以下的左旋图示，就像有这样拟人化操作：将r节点“提起来”放在p节点所在位置，将r的左子节点rl“剪下来”。将p节点“挂在”r节点左子节点位置。前面被“剪枝”的rl节点“挂到”p节点的右子节点位置——可以这样节点理解为：拿多的一侧“补给”少的一侧，以使得树两边“重量”相对接近，从而构成比上一次更加平衡的红黑树结构。为何这样的操作是“可行的”的，首先红黑树本身具有二叉搜索树的一些特征：左子树上所有结点的值均小于等于它的根结点的值（若左子树不空时）右子树上所有结点的值均大于等于它的根结点的值（若右子树不空时）从上图也可以观察出（只考察pp、p、r、rl节点），左旋前后四个节点排序保持不变：左旋前：这四个节点值的大小排序为p=rl=r=pp`左旋后：这四个节点值的大小排序为p=rl=r=pp`或者有可以采用投影法——从上方垂直投影到下方的方法进行考察：上图清晰说明左旋操作节点值排序不变，另外一个更为重要的收益则是：左旋操作竟然可以让树的两边更加平衡左旋、右旋源码做的事情无非以下三类：p节点下来后要和下方rl建立关系r节点上去后要和上方pp建立关系再把r节点和p节点建立关系，从而实现完整的关系链源码解析如下：//在插入节点代码片段引用了左旋、右旋操作 root = rotateLeft(root, x = xp);staticK,VTreeNodeK,VrotateLeft(TreeNodeK,Vroot,TreeNodeK,Vp){TreeNodeK,Vr,pp,rl;/* r=p.right; if(p !=null r !=null){ 1) p与rl建立关系：p的右节点r的左子节点rl变成p的右节点 p.right=r.left; rl=r.left; if(rl!=null) rl.parent=p; 2) r与pp建立关系： p节点的父节点pp为空的情况，说明p本来就是根节点，旋转后，r变成根节点，若p原来是pp的左节点，则r取代p后也要保持左节点位置 // rl = p.right = r.left 看不懂？ 其实是这种表达式：a=b=1,也即a=1,b=1 r.parent=p.parent pp=p.parent if(pp ==null) { root=r; root.red=false; } if (pp.left=p) pp.left=r else pp.right=r 3)r与p建立关系：p作为r的左节点，r作为p的父节点 r.left=p p.parent=r; } */if(p!=null(r=p.right)!=null){if((rl=p.right=r.left)!=null)rl.parent=p;// 此类连续赋值变量写法一定要自行拆开多个，否则不容易理解代码逻辑if((pp=r.parent=p.parent)==null)(root=r).red=false;elseif(pp.left==p)pp.left=r;elsepp.right=r;r.left=p;p.parent=r;}// 如果p节点为空说明现在是空树，直接返回rootreturnroot;// 返回根节点 因为根节点在旋转的过程中可能会改变 就需要返回改变后的}4.2 理解右旋右旋：以某个点（h）旋转，旋转点(h)左节点的右子节点变为旋转点的左节点，旋转点之前的左节点变为父节点右旋的工作机制其实跟左旋一样，只不过方向相反，如下图所示，文字说明以及源码分析则不再累赘。五、插入红黑树节点5.1 插入总体思路设计在解析插入红黑树节点及其自平衡处理前，先从put源码快速回忆HashMap插入一个元素过程：如下面注释的4种插入情况publicVput(Kkey,Vvalue){returnputVal(hash(key),key,value,false,true);}finalVputVal(inthash,Kkey,Vvalue,...//......//1、如果key定位到空的桶位上，则直接在桶位放入该新节点if((p=tab[i=(n-1)hash])==null)tab[i]=newNode(hash,key,value,null);else{//2、如果插入的key刚好与桶位节点（头节点）的key相同，不做插入操作，在后面更新value即可if(p.hash==hash((k=p.key)==key||(key!=nullkey.equals(k))))e=p;//3、如果插入的key与p哈希碰撞（当然key不等于p.key），且桶位节点p为红黑树节点，那么需要使用putTreeVal将key新节点插入到红黑树里面，这里是本节重点分析内容elseif(pinstanceofTreeNode)e=((TreeNodeK,V)p).putTreeVal(this,tab,hash,key,value);else{//4、如果桶位上p是一条冲突链，进行冲突链插入、树化等操作for(intbinCount=0;;++binCount){if((e=p.next)==null){p.next=newNode(hash,key,value,null);if(binCount=TREEIFY_THRESHOLD-1)// -1 for 1sttreeifyBin(tab,hash);break;}//....对应第3种插入情况，插入的为红黑树节点，再来看看putTreeVal的内部主要3个逻辑：1）待插入key节点恰好能在红黑树里面找到则返回该节点，否则进入2）步骤2）待插入key节点不在红黑树里面，就需要找到合适的父节点p，再将key节点插入父节点p的左边或者右边红黑树新增key节点后需要对红黑树做自平衡操作// e = ((TreeNodeK,V)p).putTreeVal(this, tab, hash, key, value);finalTreeNodeK,VputTreeVal(HashMapK,Vmap,NodeK,V[]tab,inth,Kk,Vv){// ......// 1) 遍历红黑树，找与待插入key相等的节点booleansearched=false;//这个searched为true时表示待插入key节点能在红黑树里找到TreeNodeK,Vroot=(parent!=null)?root():this;for(TreeNodeK,Vp=root;;){intdir,ph;Kpk;if((ph=p.hash)h)dir=-1;elseif(phh)dir=1;// 找与待插入key相等的节点elseif((pk=p.key)==k||(k!=nullk.equals(pk)))returnp;// .......if(((ch=p.left)!=null(q=ch.find(h,k,kc))!=null)||((ch=p.right)!=null(q=ch.find(h,k,kc))!=null))returnq;}// .......// 2) 如果1)前面未找到，说明该key为新节点，需要在红黑树里面找正确的位置父节点xp，在父节点xp左边或者右边新增一个该节点，双向链表也要同时新增该节点。TreeNodeK,Vxp=p;if((p=(dir=0)?p.left:p.right)==null){NodeK,Vxpn=xp.next;// 此操作非常容易被忽略：由于红黑树还本身也是一条双向链表，当红黑树新增节点时，双向链表也要新增对应的新节点TreeNodeK,Vx=map.newTreeNode(h,k,v,xpn);if(dir=0)xp.left=x;elsexp.right=x;// .......// 3) 收尾工作：代码执行到这里，说明已经在红黑树插入了新节点， 需对红黑树做平衡操作,moveRootToFront在后面的小节给出moveRootToFront(tab,balanceInsertion(root,x));returnnull;}}}HashMap在put一个节点恰好put到红黑树里面的流程：map.put(key,value)-putval-putTreeVal-balanceInsertion-moveRootToFront插入节点putTreeVal源码并不难理解，复杂的是后面的平衡处理：balanceInsertion5.2 平衡操作的设计解析在第三节提到红黑树平衡操作就是“变色、左旋、右旋”，其实在balanceInsertion内部实现也可以看出这些关键字：x.red = false、rotateLeft、rotateRight，当然对应下面的问题：插入节点后，在什么情况下需要变色？插入节点后，在什么情况下需要左旋？插入节点后，在什么情况下需要右旋？插入节点后，在什么情况下需要进行以上多种组合操作？当然，每种平衡处理都是基于这样的前提：1、对于balanceInsertion(root, x)入参root引用，拿到这个root节点，说明就拿到了一棵红黑树，因此对root为根结点的红黑树施加平衡调整2、对于balanceInsertion(root, x)入参x引用，这个节点x已经在balanceInsertion执行前完成了位置插入，一定要记着：节点x的位置插入，不是在``balanceInsertion`里面完成！为了能将原理分析和源码分析的节点标识一一对应，这里做了如下约定：示意图的节点标识来源于源码balanceInsertion里面的临时TreeNode类型的引用：TreeNodeK,V xp, xpp, xppl, xpprx节点：新插入的节点，在balanceInsertion调用前，x已经完成了插入。xp节点：插入节点x的父节点xpp节点：插入节点x的祖父节点xppl节点（x的左变叔叔节点）：若xp节点位于xpp右边（此时xppr就是xp），那么xppl节点就是x节点的左边叔叔节点，xppr节点（x的右边叔叔节点）：若xp节点位于xpp左边（此时xppl就是xp），那么xppr节点就是x节点的右边叔叔节点5.3 balanceInsertion图解+源码分析有了5.2的基础知识铺垫，则能很好理解按分类讨论的方式去分析每种情况的平衡操作5.3.1 若原root节点是null时原root节点是null时说明是空红黑树，因此插入节点x就作为root节点：root=x，从红黑树特点可知，balanceInsertion(root, x)里面会对x进行变色操作x.red=false,平衡调整结束，并返回x节点，同时它也是root节点该情况对应的源码片段（仅对应第一次循环的情况）staticK,VTreeNodeK,VbalanceInsertion(TreeNodeK,Vroot,TreeNodeK,Vx){x.red=true;// 插入节点x默认是红色节点for(TreeNodeK,Vxp,xpp,xppl,xppr;;){// 若root为空树，这里的for循环执行一次就退出if((xp=x.parent)==null){
