Java进阶系列：深度解析jdk1.8的HashMap红黑树balanceDeletion节点删除平衡算法设计（核心文章）

这可能是全网最期待的jdk1.8的红黑树balanceDeletion的源代码解析技术文章！

其实掌握HashMap红黑树的同学都知道，balanceDeletion方法的源代码是HashMap红黑树部分最复杂也是最难理解的部分，目前少有coder对balanceDeletion有足够深入且可理解的分析，绝大部分关于深入HashMap分析的文章都会跳过balanceDeletion源代码，有部分文章的coder他并不直接给出balanceDeletion的源代码解析，而是自行实现非HashMap的“红黑树删除平衡”代码，如链接，但显然不能跟jdk源码高质量功能相比（HashMap源码里面的removeTreeNode和balanceDeletion的代码设计是最完整的），因此要想真正掌握完整jdk级别的HashMap红黑树的balanceDeletion逻辑，那么源代码解析肯定要搬出来。

目前个人认可的文章是这篇文章，个人也给它留了评论和鼓励（该博客作者能深钻JUC源代码实现），但也发现该文在解析balanceDeletion源码、图示（少部分）不够直观、简约、清晰，因此亲自实现一篇相对高质量且尽量可理解的removeTreeNode和balanceDeletion源代码分析，本文不会跟类似文章图或者文章组织或者思路重复。

1、removeNode

remove方法删除逻辑由内部的removeNode方法代理，如果能找到key对应的删除节点，那么removeNode返回这个节点的value，否则返回null

publicVremove(Objectkey){Node<K,V>e;return(e=removeNode(hash(key),key,null,false,true))==null?null:e.value;}

以下是removeNode源码说明：

finalNode<K,V>removeNode(inthash,Objectkey,Objectvalue,booleanmatchValue,booleanmovable){Node<K,V>[]tab;Node<K,V>p;intn,index;// 显然如果table还未有节点或者key定位到桶位节点p为空，就返回null，否则进入主体逻辑if((tab=table)!=null&&(n=tab.length)>0&&(p=tab[index=(n-1)&hash])!=null){Node<K,V>node=null,e;Kk;Vv;//① 桶位节点p恰好就是要删除的节点，先不执行删除，而是将p节点赋给node引用，统一在后面处理if(p.hash==hash&&((k=p.key)==key||(key!=null&&key.equals(k))))node=p;//② 桶位节点p不是目标删除节点，那么就只能从链表找到目标删除节点或者从红黑树找到目标删除节点elseif((e=p.next)!=null){//③ 若桶位节点p是红黑树节点类型，则从红黑树找到目标删除节点。由getTreeNode负责找出目标删除节点，找到就赋给node引用if(pinstanceofTreeNode)node=((TreeNode<K,V>)p).getTreeNode(hash,key);//④ 若桶位节点p是链表头节点，遍历链表找到目标删除节点，找到就赋给node引用else