1. 为什么删除操作才是HashMap源码的真正分水岭聊JDK1.8的HashMap网上大部分文章都在讲put和扩容好像把红黑树旋转讲完就通关了。但我在实际翻源码和排查线上问题的时候发现真正容易翻车的恰恰是remove这一条链路。原因很简单put是加法最坏情况就是扩容逻辑再复杂也是单向的而remove是减法它要同时处理链表退化、红黑树节点删除、树的退化判断、以及删除后平衡调整这四件事任何一环没想清楚代码读起来就是一团浆糊。这篇文章我打算把remove、removeNode、removeTreeNode、balanceDeletion这四个方法从头到尾拆一遍。它们是一条完整的调用链你调用map.remove(key)进的是removeremove把活交给removeNoderemoveNode在遇到树节点时会调用removeTreeNode而removeTreeNode在删除黑色节点后会触发balanceDeletion做红黑树的平衡修复。四个方法层层递进缺一个都讲不透。适合谁来读如果你已经能看懂HashMap的put流程知道什么是红黑树、什么是TreeNode但每次看到删除相关的代码就跳过去那这篇就是给你补的。我会尽量用生活化的类比把红黑树的删除讲明白同时把源码里那些看起来莫名其妙的判断条件逐个解释清楚。读完你至少能做到两件事一是面试被问到删除流程时能画出完整的调用链和状态变化二是线上遇到删除相关的性能问题或死循环时知道该往哪个方向查。需要提前说明的是红黑树的删除本身是数据结构里的经典难题比插入难一个量级。我不会回避复杂度但会把每一步的为什么讲清楚而不是让你死记硬背旋转方向。2. 删除链路的整体设计与调用关系拆解2.1 四个方法各自的职责边界先把四个方法的定位说清楚不然后面看代码容易串。remove(Object key)是最外层的公开API它做的事情非常少算hash、调removeNode、根据返回值判断是否删除成功。它本身不碰任何数据结构纯粹是个入口。removeNode(int hash, Object key, Object value, boolean matchValue, boolean movable)是真正的执行者。它负责定位桶、遍历链表或树、找到目标节点、执行删除、维护size和modCount。注意它的参数里有matchValue和movable这两个是给remove(key, value)和迭代器删除用的普通remove传的是false和true。removeTreeNode(HashMapK,V map, NodeK,V[] tab, boolean movable)是TreeNode这个内部类的方法专门处理红黑树节点的删除。它要处理的情况比链表复杂得多删除的可能是叶子、可能有一个子节点、可能有两个子节点还要判断删除后树是否太小需要退化成链表。balanceDeletion(TreeNodeK,V root, TreeNodeK,V x)是红黑树删除后的平衡修复函数。当被删除的节点是黑色时会破坏红黑树的性质必须通过旋转和重新着色来恢复。这个方法是整个链路里最难啃的部分。2.2 为什么删除要拆成这么多层有朋友可能会问为什么不把逻辑都塞进一个方法里我理解这么拆有两个考虑。第一是职责分离。removeNode要同时支持链表和树两种结构如果它直接内联树的删除逻辑代码会变得极其臃肿。把树的删除封装到removeTreeNode里removeNode只需要判断这个节点是不是TreeNode是就委托出去不是就走链表逻辑。这样链表和树的处理互不干扰。第二是复用。removeTreeNode和balanceDeletion都是TreeNode类的方法它们操作的是树的结构和HashMap的桶数组没有直接关系。这种设计让树的逻辑相对独立也方便理解。从性能角度看这个拆分没有引入额外开销因为都是方法调用JIT会做内联优化。真正影响性能的是红黑树删除本身的复杂度那是O(log n)级别的和拆分无关。2.3 删除操作要维护的三个不变量在读具体代码之前先记住删除操作必须维护的三个不变量后面每一步都能对上号。第一个是size的准确性。每删除一个节点size必须减1而且只能减1。这个看起来简单但在树退化、节点转移的过程中很容易出错。第二个是modCount的递增。这是fail-fast机制的基础只要结构发生修改modCount就要加1。注意如果matchValue为true但value不匹配是不算修改的modCount不能动。第三个是红黑树性质的保持。删除黑色节点会破坏从任一节点到其叶子的所有路径包含相同数目的黑色节点这条性质必须通过balanceDeletion修复。这是最容易被忽略但最影响正确性的一点。提示很多人读源码时只关注删掉了没有忽略了红黑树性质的维护。实际上如果平衡修复写错树会退化成近似链表查询性能从O(log n)掉到O(n)而且这种问题在数据量小时根本看不出来。3. remove与removeNode的逐行拆解3.1 remove方法一个极简的入口先看remove的源码它短得有点出乎意料public V remove(Object key) { NodeK,V e; return (e removeNode(hash(key), key, null, false, true)) null ? null : e.value; }就这么几行。它做了三件事算key的hash、调用removeNode、如果返回的节点不为null就返回它的value否则返回null。这里有个细节值得说matchValue传的是falsemovable传的是true。matchValuefalse意味着只要key匹配就删除不管value是什么movabletrue意味着删除时允许移动其他节点这个参数在树退化时会用到。为什么remove这么薄因为它的定位就是对外接口真正的逻辑都在removeNode里。这种设计在JDK源码里很常见公开方法尽量简单把复杂度下沉到内部方法。3.2 removeNode的定位阶段找到要删的节点removeNode的前半段是定位逻辑和getNode几乎一样final NodeK,V removeNode(int hash, Object key, Object value, boolean matchValue, boolean movable) { NodeK,V[] tab; NodeK,V p; int n, index; if ((tab table) ! null (n tab.length) 0 (p tab[index (n - 1) hash]) ! null) { NodeK,V node null, e; K k; V v; if (p.hash hash ((k p.key) key || (key ! null key.equals(k)))) node p; else if ((e p.next) ! null) { if (p instanceof TreeNode) node ((TreeNodeK,V)p).getTreeNode(hash, key); else { do { if (e.hash hash ((k e.key) key || (key ! null key.equals(k)))) { node e; break; } p e; } while ((e e.next) ! null); } } // ... 删除阶段 } return null; }定位分三种情况。第一种桶的第一个节点就是目标直接node p。第二种桶里是红黑树调用getTreeNode查找。第三种桶里是链表用do-while遍历。这里有个容易忽略的点链表遍历时p始终指向e的前一个节点。为什么要这样因为删除链表节点需要前驱节点的引用p.next node.next才能把节点摘掉。如果只记录当前节点删除时就没法接上前驱了。这是链表删除的经典技巧一定要记住p的角色。还有一个细节p.hash hash这个判断在链表遍历里也做了。为什么因为hash冲突时不同key可能落在同一个桶但hash值不一定相同。先比hash再比equals能减少equals的调用次数是个性能优化。3.3 removeNode的删除阶段分链表和树两种情况找到node之后进入删除阶段if (node ! null (!matchValue || (v node.value) value || (value ! null value.equals(v)))) { if (node instanceof TreeNode) ((TreeNodeK,V)node).removeTreeNode(this, tab, movable); else if (node p) tab[index] node.next; else p.next node.next; modCount; --size; afterNodeRemoval(node); return node; }先看那个长长的if条件。!matchValue表示不校验value直接删如果matchValue为true则要求value相等用或equals。这就是remove(key, value)能精确删除的原因。删除分三种情况。如果是树节点委托给removeTreeNode。如果node就是桶的第一个节点node p把桶指向node.next。否则把前驱的next指向node的next也就是p.next node.next。注意node p这个判断。在链表遍历时如果第一个节点就是目标p没有被更新过仍然指向第一个节点所以node p成立。如果目标在后面p会被更新成前驱此时node ! p走p.next node.next。这个判断保证了两种情况都能正确处理。删除完成后modCount、--size、afterNodeRemoval这是给LinkedHashMap用的钩子。最后返回被删的node让remove能拿到value。注意afterNodeRemoval在HashMap里是空实现只有LinkedHashMap才重写它来维护双向链表。如果你在读LinkedHashMap的源码这个钩子就是关键。4. removeTreeNode红黑树删除的核心逻辑4.1 树退化的触发条件removeTreeNode一上来就有一段判断是否需要退化的代码这是JDK1.8特有的设计final void removeTreeNode(HashMapK,V map, NodeK,V[] tab, boolean movable) { int n; if (tab null || (n tab.length) 0) return; int index (n - 1) hash; TreeNodeK,V first (TreeNodeK,V)tab[index], root first, rl; TreeNodeK,V succ (TreeNodeK,V)next, pred prev; if (pred null) tab[index] first succ; else pred.next succ; if (succ ! null) succ.prev pred; if (first null) return; if (root.parent ! null) root root.root(); if (root null || (movable (root.right null || (rl root.left) null || rl.left null))) { tab[index] first.untreeify(map); return; } // ... 真正的树删除 }前面几行是维护双向链表。TreeNode既在红黑树里也在一个双向链表里prev和next这是为了方便退化和遍历。删除节点时先把链表指针接好如果pred为null说明删的是头把桶指向succ否则pred.next succ。然后succ.prev pred。接下来是退化判断。root.parent ! null时通过root.root()找到真正的根。然后看这个条件root null || (movable (root.right null || (rl root.left) null || rl.left null))。这个条件的意思是如果根为空或者根太瘦了右子为空或左子为空或左子的左子为空就把树退化成链表。为什么是这几个条件因为红黑树的性质决定了如果根到最远叶子的路径长度是h那么节点数至少是2^h - 1。反过来如果树的结构已经这么稀疏说明节点数很少红黑树的O(log n)优势已经不明显不如退化成链表省去维护树的旋转开销。movable参数在这里起作用只有允许移动时才退化。迭代器删除时可能传false避免在遍历过程中改变结构。4.2 删除节点的三种情况退化判断通过后进入真正的树删除。红黑树的删除和普通二叉搜索树一样分三种情况TreeNodeK,V p this, pl left, pr right, replacement; if (pl ! null pr ! null) { // 情况三有两个子节点 TreeNodeK,V s pr, sl; while ((sl s.left) ! null) s sl; boolean c s.red; s.red p.red; p.red c; TreeNodeK,V sr s.right; TreeNodeK,V pp p.parent; if (s pr) { p.parent s; s.right p; } else { TreeNodeK,V sp s.parent; if ((p.parent sp) ! null) { if (s sp.left) sp.left p; else sp.right p; } if ((s.right pr) ! null) pr.parent s; } p.left null; if ((p.right sr) ! null) sr.parent p; if ((s.left pl) ! null) pl.parent s; if ((s.parent pp) null) root s; else if (p pp.left) pp.left s; else pp.right s; if (sr ! null) replacement sr; else replacement p; } else if (pl ! null) replacement pl; else if (pr ! null) replacement pr; else replacement p;情况三最复杂被删节点p有两个子节点。标准做法是找p的后继s右子树的最左节点用s替换p的位置。但JDK这里的实现不是简单的复制值再删s而是直接做节点交换把s移到p的位置把p移到s原来的位置。为什么要交换而不是复制值因为TreeNode有prev和next指针如果复制值链表里的节点引用就乱了。直接交换节点链表指针不用动更安全。交换的过程分两种子情况。如果s就是p的右子s pr直接把p挂到s的右边。否则先把s从原位置摘下来把p接上去再把s移到p的位置。这段代码看起来绕但本质就是把s和p的位置互换。交换完成后p变成了要被删除的节点它现在最多只有一个子节点原来的sr。replacement就是p的替代者如果sr不为nullreplacement是sr否则replacement是p自己因为p现在是叶子。情况一和情况二简单只有一个子节点时replacement就是那个子节点没有子节点时replacement是p自己。4.3 删除后的平衡修复入口处理完三种情况后进入删除和平衡阶段if (replacement ! p) { TreeNodeK,V pp replacement.parent p.parent; if (pp null) root replacement; else if (p pp.left) pp.left replacement; else pp.right replacement; p.left p.right p.parent null; } TreeNodeK,V r p.red ? root : balanceDeletion(root, replacement); if (replacement p) { TreeNodeK,V pp p.parent; p.parent null; if (pp ! null) { if (p pp.left) pp.left null; else if (p pp.right) pp.right null; } } if (movable) moveRootToFront(tab, r);如果replacement不是p说明p有替代者把replacement接到p的位置上然后清空p的指针。接着是关键的一行TreeNodeK,V r p.red ? root : balanceDeletion(root, replacement);。如果p是红色删除它不影响黑色节点数量红黑树性质保持不需要平衡直接返回root。如果p是黑色删除它会破坏性质必须调用balanceDeletion修复。最后如果replacement就是p说明p是叶子把p从父节点上摘掉。然后如果movable把根节点移到桶的第一个位置moveRootToFront保证桶的头节点是根。提示moveRootToFront这个操作容易被忽略。红黑树的根不一定是桶里的第一个节点但HashMap要求桶的头节点是根这样getTreeNode从根开始查找才高效。每次结构性修改后都要把根移到前面。5. balanceDeletion红黑树删除的平衡修复5.1 为什么删除黑色节点需要修复红黑树有五条性质其中最关键的一条是从任一节点到其所有叶子的路径上黑色节点数量相同。删除一个黑色节点会让经过它的路径少一个黑色节点这条性质就被破坏了。balanceDeletion的任务就是通过旋转和重新着色把这个缺失的黑色补回来。它的思路是把被删节点的替代者x看作额外带了一层黑色然后不断向上调整直到这层额外的黑色被消化掉。这个额外黑色的概念是理解红黑树删除的关键。你可以把它想象成x节点上贴了一张欠一个黑色的标签修复的过程就是把这个标签往上传递或者消除掉。5.2 修复的四种情形balanceDeletion的代码是个大循环处理四种情形。先看整体结构static K,V TreeNodeK,V balanceDeletion(TreeNodeK,V root, TreeNodeK,V x) { for (TreeNodeK,V xp, xpl, xpr;;) { if (x null || x root) return root; else if ((xp x.parent) null) { x.red false; return x; } else if (x.red) { x.red false; return root; } else if ((xpl xp.left) x) { // x是左子 if ((xpr xp.right) ! null xpr.red) { // 情形1兄弟是红色 xpr.red false; xp.red true; root rotateLeft(root, xp); xpr (xp x.parent) null ? null : xp.right; } if (xpr null) x xp; else { TreeNodeK,V sl xpr.left, sr xpr.right; if ((sr null || !sr.red) (sl null || !sl.red)) { // 情形2兄弟的两个子都是黑色 xpr.red true; x xp; } else { if (sr null || !sr.red) { // 情形3兄弟的右子是黑色左子是红色 if (sl ! null) sl.red false; xpr.red true; root rotateRight(root, xpr); xpr (xp x.parent) null ? null : xp.right; } // 情形4兄弟的右子是红色 if (xpr ! null) { xpr.red (xp null) ? false : xp.red; if ((sr xpr.right) ! null) sr.red false; } if (xp ! null) { xp.red false; root rotateLeft(root, xp); } x root; } } } else { // x是右子和上面镜像对称 // ... } } }循环的终止条件有三个x为null、x是根、x是红色。x是红色时直接把它染黑就能补上缺失的黑色修复结束。x是根时根永远是黑色直接返回。下面以x是左子为例讲四种情形。情形1兄弟是红色。兄弟是红色意味着父节点一定是黑色兄弟的两个子一定是黑色。处理方式是兄弟染黑、父节点染红、对父节点左旋。这样做的目的是把兄弟是红色转换成兄弟是黑色的情形因为后面三种情形都假设兄弟是黑色。旋转后x的新兄弟变成了原来兄弟的左子是黑色可以继续处理。情形2兄弟是黑色且兄弟的两个子都是黑色。这种情况没法从兄弟那里借黑色节点只能把兄弟染红然后把额外黑色上移到父节点让父节点成为新的x继续循环。如果父节点原来是红色下一轮循环会因为x.red为true而终止把父节点染黑即可。情形3兄弟是黑色兄弟的右子是黑色左子是红色。这种情形不能直接处理需要先转换。做法是兄弟的左子染黑、兄弟染红、对兄弟右旋。旋转后新的兄弟是原来兄弟的左子红色它的右子变成了原来的兄弟黑色这样就转换成了情形4。情形4兄弟是黑色兄弟的右子是红色。这是最终能解决问题的情形。做法是兄弟继承父节点的颜色、父节点染黑、兄弟的右子染黑、对父节点左旋。旋转后x的额外黑色被消化x指向root循环结束。x是右子的情况完全对称只是旋转方向反过来左右子的判断反过来。5.3 四种情形的转换关系这四种情形不是孤立的它们之间有明确的转换路径。我画个表说明当前情形条件处理转换到情形1兄弟红兄弟黑、父红、左旋父情形2/3/4情形2兄弟黑两子黑兄弟红x上移到父循环继续情形3兄弟黑右子黑左子红左子黑、兄弟红、右旋兄弟情形4情形4兄弟黑右子红兄弟继承父色、父黑、右子黑、左旋父结束理解这个转换关系比死记代码有用得多。实际修复时最多经过情形1→情形3→情形4或情形1→情形2→循环这样的路径不会无限循环因为每次上移x都会让问题规模减小。注意情形2里x上移到父节点后如果父节点是红色下一轮循环直接染黑结束如果父节点是黑色继续按四种情形处理。这个上移过程最多到根所以循环次数是O(log n)。6. 实操验证与常见问题排查6.1 用反射验证删除后的树结构光看源码不够最好动手验证。我写了一段用反射查看HashMap内部结构的代码可以直观看到删除前后树的变化import java.lang.reflect.Field; import java.util.HashMap; public class HashMapDebug { public static void main(String[] args) throws Exception { HashMapInteger, String map new HashMap(); // 构造足够多的冲突key触发树化 for (int i 0; i 32; i) { map.put(i * 16, v i); } printStructure(map); // 删除部分节点观察退化 for (int i 0; i 20; i) { map.remove(i * 16); } printStructure(map); } static void printStructure(HashMap?, ? map) throws Exception { Field tableField HashMap.class.getDeclaredField(table); tableField.setAccessible(true); Object[] table (Object[]) tableField.get(map); for (int i 0; i table.length; i) { if (table[i] ! null) { System.out.println(bucket i : table[i].getClass().getSimpleName()); } } } }运行后你会看到删除到一定程度桶里的节点类型从TreeNode变回了Node这就是退化的效果。这个实验能帮你确认退化条件是否按预期触发。6.2 常见问题速查表实际读源码和排查问题时我遇到过不少坑整理成表方便对照问题现象可能原因排查方向删除后查询变慢树未退化或退化条件判断有误检查removeTreeNode的退化条件迭代时删除抛异常modCount被意外修改检查matchValue分支是否误加modCount删除后树结构错乱balanceDeletion旋转方向写反对照左右子镜像逻辑链表删除后断链前驱指针p未正确维护检查p.next node.next根节点不在桶头未调用moveRootToFront检查movable参数传递6.3 几个容易踩的坑第一个坑是混淆remove(key)和remove(key, value)。前者只要key匹配就删后者要求key和value都匹配。如果你在业务里用remove(key, value)做条件删除要注意value的equals实现如果value是自定义对象且没重写equals可能永远删不掉。第二个坑是在迭代中直接调map.remove。这会触发fail-fast抛ConcurrentModificationException。正确做法是用Iterator的remove方法它内部会同步modCount。迭代器的remove最终也是走removeNode但传的movable可能是false避免在遍历时改变树结构。第三个坑是误以为删除一定会触发平衡修复。实际上只有删除黑色节点才需要balanceDeletion删除红色节点直接返回。如果你在调试时发现没进balanceDeletion先确认被删节点是不是红色。第四个坑是忽略movable参数的影响。movablefalse时不会退化也不会移动根节点。这个参数主要给迭代器和一些内部操作使用普通remove传的是true。如果你自己写代码调用内部方法传错这个参数可能导致结构不一致。提示调试红黑树删除时建议在balanceDeletion的循环里打印每次的x、xp、xpr和旋转方向。红黑树的修复过程是状态机打印出来比单步调试直观得多。7. 从删除链路看JDK1.8的设计取舍把四个方法读完能看出JDK1.8在HashMap删除上的几个设计取舍。第一是用节点交换代替值复制。标准红黑树删除是复制后继的值到被删节点然后删后继但JDK选择交换节点位置。原因是TreeNode同时维护红黑树和双向链表两套结构复制值会破坏链表引用交换节点则两套结构都能保持一致。这个取舍增加了代码复杂度但换来了正确性。第二是退化条件的保守设计。退化条件root.right null || root.left null || root.left.left null看起来很奇怪为什么是这三个条件我理解是为了在节点数很少时尽早退化。红黑树在节点数少于6个左右时维护成本已经超过收益退化成链表反而更快。这个阈值是经验值不是理论推导出来的。第三是balanceDeletion的循环实现。红黑树删除的平衡修复可以用递归实现也可以用循环。JDK选了循环因为循环没有栈开销而且修复过程本身就是向上传递的循环更自然。代价是代码里变量多、分支多读起来费劲。第四是modCount和size的更新时机。注意removeNode里是先删除结构、再modCount、再--size。这个顺序很重要如果先改size再删结构中间出现异常会导致size和实际结构不一致。JDK把结构修改放在前面保证要么都成功要么都不动。这些取舍没有绝对的对错都是在正确性、性能、可读性之间找平衡。读源码的价值不在于背下代码而在于理解这些取舍背后的权衡。下次你自己设计数据结构时遇到类似问题就知道该怎么选了。我个人在实际排查HashMap相关问题时最大的体会是删除链路的问题往往不是逻辑错误而是边界条件没覆盖。比如空桶、单节点桶、树刚好退化到链表的临界点这些边界在正常测试里很难触发但线上数据量一大就可能出现。所以读源码时我会特别关注那些 null和! null的判断它们往往就是边界处理的关键。