1. 拆解删除逻辑为什么remove比put更值得逐行读很多人读HashMap源码put那条线读得滚瓜烂熟扩容、树化、红黑树旋转都能讲得头头是道但一到remove就含糊了。我早期也是这样觉得删除嘛找到节点摘掉就完事了。直到有一次在模拟项目里排查一个“删了元素但size对不上”的诡异问题才回头把remove这条链路完整啃了一遍发现里面的坑比put还密。这篇要聊的就是JDK1.8里HashMap删除操作的完整实现核心围绕四个方法展开remove、removeNode、removeTreeNode、balanceDeletion。前两个负责定位和摘除节点后两个专门处理红黑树退化场景下的删除与再平衡。适合已经了解HashMap基本结构、想深入理解删除路径的开发者也适合正在准备技术面试、需要把红黑树删除讲清楚的人。先说结论HashMap的删除不是“找到就删”这么简单它要同时维护三件事——链表/红黑树的结构完整性、size和modCount的一致性、以及树节点过少时的退化逻辑。这三件事任何一件处理不好都会导致后续get、put出现难以复现的bug。下面我按实际阅读顺序把每个方法的意图、参数、边界条件和踩坑点全部摊开讲。2. remove与removeNode定位与摘除的完整链路2.1 remove的两个重载与返回值语义remove对外暴露两个重载public V remove(Object key) public boolean remove(Object key, Object value)第一个只按key删返回被删除的旧value如果key不存在返回null。第二个是JDK1.8新增的只有key和value都匹配才删返回boolean表示是否删除成功。这个双参数版本在并发场景下做“检查再删除”很有用但要注意它本身不是原子操作别指望它能替代并发容器。两个重载最终都汇聚到removeNodepublic V remove(Object key) { NodeK,V e; return (e removeNode(hash(key), key, null, false, true)) null ? null : e.value; } public boolean remove(Object key, Object value) { return removeNode(hash(key), key, value, true, true) ! null; }这里有个细节值得注意单参数版本传的value是nullmatchValue是false双参数版本传真实valuematchValue是true。removeNode内部靠matchValue决定要不要比对value。我第一次读的时候没注意这个标志位以为两个方法走的是不同分支其实核心逻辑完全复用。提示remove(Object key, Object value)在value为null时有歧义风险。如果map里存了key对应null值传null进去matchValue为true会匹配成功并删除。这个行为符合规范但业务代码里要小心。2.2 removeNode的参数设计与查找逻辑removeNode的签名是final NodeK,V removeNode(int hash, Object key, Object value, boolean matchValue, boolean movable)五个参数各有用途。hash是预先算好的避免重复计算key和value是目标matchValue决定是否比对valuemovable这个参数最容易被忽略它控制删除树节点时是否移动根节点后面讲removeTreeNode会重点说。方法体前半段是标准的查找流程和getNode几乎一样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); } } ... }这段逻辑分三种情况头节点命中、树节点查找、链表遍历。注意链表遍历时用p记录前驱节点因为删除需要改前驱的next指针。树节点则直接调getTreeNode不需要前驱因为树删除有自己的处理方式。查找命中后进入删除分支这里先做matchValue校验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; }三种删除方式树节点走removeTreeNode头节点直接改桶数组中间节点改前驱next。删完统一modCount、size--再调afterNodeRemoval钩子LinkedHashMap靠它维护双向链表。注意afterNodeRemoval在HashMap里是空实现但如果你自定义了子类覆盖它要保证不抛异常否则size已经减了但钩子失败状态就不一致了。2.3 链表删除的指针操作细节链表删除看着简单但有个容易写错的地方。当删除的是头节点时直接tab[index] node.next把桶指向第二个节点。当删除的是中间或尾部节点时p.next node.nextp是遍历时保留的前驱。我见过有人在手写类似逻辑时遍历用e删除时却用e.next去改结果删错了节点。关键就是前驱p必须在循环里及时更新每次p e再e e.next这样e命中时p正好是它的前驱。还有一个边界如果链表只有一个节点且被删除node p成立因为p初始就是头节点走tab[index] node.nextnode.next是null桶被置空。这个分支同时覆盖了“头节点”和“单节点”两种情况写得很紧凑。2.4 modCount与size的维护时机modCount和--size放在实际摘除之后、钩子之前。这个顺序是有讲究的先改结构再改计数保证任何时刻读到的size都和实际节点数一致。如果反过来先减size再摘节点中间态就会出现size偏小的情况虽然单线程下无所谓但迭代器的fail-fast检查依赖modCount顺序错了可能影响快速失败行为。modCount的作用是给迭代器做版本标记。每次结构变化都自增迭代器在next和remove时比对expectedModCount不一致就抛ConcurrentModificationException。删除操作自然也要自增否则迭代过程中删除不会被检测到。3. removeTreeNode树节点删除与退化触发3.1 树节点删除的三种结构情况removeTreeNode是TreeNode类的方法处理红黑树节点的摘除。它的逻辑比链表复杂得多因为要维护红黑树性质还要判断是否退化成链表。方法开头先做退化判断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 || root.right null || (rl root.left) null || rl.left null) { tab[index] first.untreeify(map); return; } ... }这里先处理双向链表指针TreeNode同时维护next/prev和left/right/parent把节点从链表里摘掉。然后判断树是否太小如果root为null或者root.right为null或者root.left为null或者root.left.left为null就调用untreeify退化成链表。这个退化条件很宽松只要树看起来“不够深”就退化。为什么这么设计因为红黑树删除的再平衡成本高当节点数少到一定程度链表反而更快。JDK选择在删除时主动检查而不是等节点数精确降到6才退化是为了避免复杂的计数维护。提示退化阈值不是固定的6。put时的树化阈值是8删除时的退化判断用的是结构条件而非计数。这意味着树可能在节点数还大于6时就退化了这是正常的。3.2 untreeify的转换过程untreeify把TreeNode链表转回普通Node链表final NodeK,V untreeify(HashMapK,V map) { NodeK,V hd null, tl null; for (NodeK,V q this; q ! null; q q.next) { NodeK,V p map.replacementNode(q, null); if (tl null) hd p; else tl.next p; tl p; } return hd; }它从当前节点开始沿着next指针遍历把每个TreeNode替换成普通Node重新串成链表。replacementNode就是new一个Node把hash、key、value拷过去。注意这里用的是next链而非树结构因为TreeNode本身维护了链表顺序直接复用即可。这个转换是单向的转完就回不去了除非后续put又触发树化。所以频繁在树化和退化之间摇摆的map性能会有波动。实际业务里如果key的hash分布均匀很少走到这一步。3.3 红黑树删除的节点替换逻辑如果没触发退化就进入真正的红黑树删除。删除分两种情况被删节点有两个孩子或者至多一个孩子。TreeNodeK,V r this, p, pl, pr; if (r.left ! null r.right ! null) { TreeNodeK,V s r.successor(); ... }当节点有两个孩子时找后继节点s右子树最左节点把s的key和value复制到当前节点然后转而删除s。这样就把“删双子节点”转化成“删至多单子节点”简化后续处理。TreeNodeK,V replacement; if ((pl p.left) ! null (pr p.right) ! null) { ... } else if (pl ! null) replacement pl; else if (pr ! null) replacement pr; else replacement p;如果p至多一个孩子replacement就是那个孩子或p自己。然后根据p的颜色和replacement的情况决定是否调用balanceDeletion。3.4 movable参数的真实作用movable这个参数在removeNode里传进来一路传到removeTreeNode。它的作用是当删除导致根节点变化时是否把新根移到桶数组的第一个位置。if (movable) moveRootToFront(tab, r);moveRootToFront把红黑树根节点移到链表头部保证tab[index]始终指向根。这样后续查找可以直接从根开始不用先遍历链表找根。如果movable为false就不移动根可能不在头部查找时需要先找到根。什么时候movable为false在split、computeIfAbsent等内部操作里会传false因为这些场景下已经持有根引用不需要额外移动。普通remove传true保证外部视角的一致性。注意moveRootToFront会同时调整双向链表指针把root移到first位置。这个操作本身不改变树结构只改链表顺序但会影响迭代顺序。4. balanceDeletion红黑树删除后的再平衡4.1 为什么删除比插入更难平衡红黑树插入最多两次旋转就能恢复性质删除却可能一路向上回溯到根。原因是删除一个黑色节点会破坏“黑高”性质从根到叶子的黑色节点数不一致了。修复这个问题的核心思路是“把缺失的黑色向上推”直到遇到红色节点或根节点。balanceDeletion就是干这个的。它的入参是root和xx是替换上来的节点可能为null。方法体是一个大循环x不断上移直到x是根或者x是红色。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; } ... } }三个终止条件x为null、x是根、x是红色。x是红色时直接染黑因为红色节点不贡献黑高染黑后正好补上缺失的那一层黑色。4.2 四种兄弟节点情况的处理循环主体根据x是左孩子还是右孩子以及兄弟节点的颜色分四种情况。以x是左孩子为例情况一兄弟xpr是红色。此时xp必为黑色。把xpr染黑、xp染红对xp左旋然后更新xpr为xp的右孩子。这样把红色兄弟转成黑色兄弟进入后续情况。if ((xpr xp.right) ! null xpr.red) { xpr.red false; xp.red true; root rotateLeft(root, xp); xpr (xp x.parent) null ? null : xp.right; }情况二兄弟是黑色且两个侄子都是黑色。把兄弟染红x上移到xp继续循环。这相当于把缺失的黑色推到父节点让父节点去处理。if (xpr null) x xp; else { TreeNodeK,V sl xpr.left, sr xpr.right; if ((sr null || !sr.red) (sl null || !sl.red)) { xpr.red true; x xp; } ... }情况三兄弟是黑色远侄子黑色、近侄子红色。把近侄子染黑、兄弟染红对兄弟右旋更新xpr。这样把情况三转成情况四。else { if (sr null || !sr.red) { if (sl ! null) sl.red false; xpr.red true; root rotateRight(root, xpr); xpr (xp x.parent) null ? null : xp.right; } ... }情况四兄弟是黑色远侄子红色。兄弟继承父节点颜色父节点染黑远侄子染黑对父节点左旋然后x置为root结束循环。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;x是右孩子时完全对称左右对调即可。这四种情况的顺序不能乱因为情况一和情况三都是为了转化成情况二或情况四最终由情况二向上推或情况四终结。4.3 旋转操作与颜色维护的配合balanceDeletion里调用了rotateLeft和rotateRight。这两个旋转方法不仅调整指针还会更新parent引用和根节点。旋转本身不改变颜色颜色由调用方在旋转前后设置。以情况四为例旋转前先把xpr染成xp的颜色xp染黑sr染黑然后左旋。左旋后xpr上位成为新的子树根继承原来的颜色xp成为xpr的左孩子且是黑色sr保持黑色。这样从根到各叶子的黑高就恢复了。我读这段时最大的困惑是为什么情况四旋转后x直接置为root因为情况四处理完整棵树的红黑性质已经恢复不需要再向上回溯。xroot只是让循环条件x root成立直接返回。4.4 删除再平衡的复杂度分析balanceDeletion最坏情况是O(log n)因为x每次上移一层最多到根。每次循环内的旋转是O(1)。整体删除操作查找O(log n)或O(1)链表删除O(1)再平衡O(log n)所以树节点删除是O(log n)。对比链表删除O(n)查找树化后的删除在节点多时有优势。但节点少时树退化成链表又回到O(n)。JDK用结构条件控制退化就是在平衡两种结构的开销。提示红黑树删除的再平衡路径可能很长但实际触发旋转的次数很少。大部分情况是情况二一路向上染红直到遇到红色节点或根。这也是红黑树适合频繁增删的原因。5. 常见问题与排查技巧实录5.1 删除后size不对的排查思路如果发现删除后size和实际元素数不符按这个顺序查确认是否走了removeNode。如果自定义了子类覆盖remove可能没调super。检查afterNodeRemoval钩子是否抛异常。钩子在size--之后调用抛异常会导致size已减但节点还在。多线程环境下HashMap本身不安全size错乱是正常的换ConcurrentHashMap。检查是否有并发修改导致modCount异常迭代器可能提前退出。我遇到的那次是自定义子类在afterNodeRemoval里做了耗时操作中间被中断抛了异常导致状态不一致。后来把钩子逻辑改成异步才解决。5.2 树退化后get变慢的原因树退化成链表后get从O(log n)变成O(n)。如果发现某个桶的get突然变慢可能是该桶的树退化了。用反射或调试器看tab[index]的类型如果是普通Node而非TreeNode就是退化了。退化本身是正常的但如果频繁退化又树化说明key的hash分布有问题。检查key的hashCode实现避免大量key落在同一个桶。理想情况下hash应该均匀分布。5.3 removeTreeNode里root为null的处理removeTreeNode开头有if (root null || ...)的判断root为null时直接退化。什么情况下root为null当树只有一个节点且被删除时first可能为nullroot也失去引用。这个分支保证不会NPE。但要注意root.parent ! null时调root.root()找真正的根。因为TreeNode的parent链可能指向的不是根需要一路向上找。这个操作是O(log n)但只在删除时做一次可以接受。5.4 balanceDeletion的null安全balanceDeletion里大量判断null因为x可能是null删除的是叶子节点xpr也可能为null兄弟不存在。这些null检查不是防御性编程而是真实会发生的场景。比如删除一个没有兄弟的黑色叶子x为nullxpr也为null直接走x xp上移。写类似红黑树代码时null检查必须完备否则很容易NPE。我建议在纸上画出所有可能的结构逐个验证null分支。5.5 常见问题速查表问题现象可能原因排查方法删除后size偏大钩子异常或未调removeNode检查afterNodeRemoval和子类覆盖删除后get返回null节点未真正摘除断点看tab[index]结构迭代时抛CMEmodCount未更新确认删除走了标准路径树频繁退化树化hash分布差检查key的hashCode删除性能差树退化或链表长看桶结构优化hashNPE在balanceDeletionnull分支未覆盖补全x和xpr的null判断5.6 实操心得如何验证删除逻辑正确我验证HashMap删除逻辑时用了一个笨办法但很有效构造大量随机key先put再remove每次remove后遍历整个map比对size和实际节点数同时用反射检查每个桶的结构是否合法链表无环、树满足红黑性质。这个测试跑了几万次抓出过两个问题一个是自定义key的equals和hashCode不一致导致删不掉另一个是并发环境下size错乱。单线程下JDK的实现是可靠的问题基本都出在使用方式上。提示如果要在生产环境验证建议用JMH做基准测试别用System.currentTimeMillis粗测。删除性能受JIT和GC影响很大粗测数据不可靠。6. 从删除链路看JDK的设计取舍把remove、removeNode、removeTreeNode、balanceDeletion串起来看能看出JDK在几个地方的取舍。第一查找逻辑在removeNode里内联没有复用getNode因为删除需要前驱节点getNode不需要复用反而要额外传参。第二树退化的判断用结构条件而非精确计数省去了维护节点数的开销代价是可能提前退化。第三balanceDeletion用循环而非递归避免栈溢出但代码可读性下降。这些取舍没有绝对的对错都是为通用场景服务的。如果你在自己的项目里实现类似结构可以根据实际数据分布调整策略。比如key的hash很均匀树化几乎不会发生那删除路径的树处理代码就是死代码可以简化。我个人在实际操作中的体会是读源码不要只读主流程边界分支往往藏着最多的设计信息。removeTreeNode里那个root.left.left null的退化条件我看了三遍才明白它的意图——用最少的判断覆盖大多数“树太小”的情况。这种写法在业务代码里也值得借鉴用近似条件换性能只要误差可控就行。最后分享一个小技巧调试HashMap删除时可以在removeNode的返回处打条件断点条件是size和实际节点数不符。这样能快速定位到出问题的删除操作比全量日志高效得多。