HashMap删除源码深度解析：remove、removeNode与红黑树再平衡

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表示是否删除成功。这个双参数版本在并发场景下做“检查再删除”很有用，但要注意它本身不是原子操作，别指望它能替代并发容器。

两个重载最终都汇聚到removeNode：

public V remove(Object key) { Node<K,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是null，matchValue是false；双参数版本传真实value，matchValue是true。removeNode内部靠matchValue决定要不要比对value。我第一次读的时候没注意这个标志位，以为两个方法走的是不同分支，其实核心逻辑完全复用。

提示：remove(Object key, Object value)在value为null时有歧义风险。如果map里存了key对应null值，传null进去matchValue为true，会匹配成功并删除。这个行为符合规范，但业务代码里要小心。

2.2 removeNode的参数设计与查找逻辑

removeNode的签名是：

final Node<K,V> removeNode(int hash, Object key, Object value, boolean matchValue, boolean movable)

五个参数各有用途。hash是预先算好的，避免重复计算；key和value是目标；matchValue决定是否比对value；movable这个参数最容易被忽略，它控制删除树节点时是否移动根节点，后面讲removeTreeNode会重点说。

方法体前半段是标准的查找流程，和getNode几乎一样：

Node<K,V>[] tab; Node<K,V> p; int n, index; if ((tab = table) != null && (n = tab.length) > 0 && (p = tab[index = (n - 1) & hash]) != null) { Node<K,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 = ((TreeNode<K,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) ((TreeNode<K,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.next，p是遍历时保留的前驱。

我见过有人在手写类似逻辑时，遍历用e，删除时却用e.next去改，结果删错了节点。关键就是前驱p必须在循环里及时更新：每次p = e再e = e.next，这样e命中时p正好是它的前驱。

还有一个边界：如果链表只有一个节点且被删除，node == p成立（因为p初始就是头节点），走tab[index] = node.next，node.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(HashMap<K,V> map, Node<K,V>[] tab, boolean movable) { int n; if (tab == null || (n = tab.length) == 0) return; int index = (n - 1) & hash; TreeNode<K,V> first = (TreeNode<K,V>)tab[index], root = first, rl; TreeNode<K,V> succ = (TreeNode<K,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 Node<K,V> untreeify(HashMap<K,V> map) { Node<K,V> hd = null, tl = null; for (Node<K,V> q = this; q != null; q = q.next) { Node<K,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 红黑树删除的节点替换逻辑

如果没触发退化，就进入真正的红黑树删除。删除分两种情况：被删节点有两个孩子，或者至多一个孩子。

TreeNode<K,V> r = this, p, pl, pr; if (r.left != null && r.right != null) { TreeNode<K,V> s = r.successor(); ... }

当节点有两个孩子时，找后继节点s（右子树最左节点），把s的key和value复制到当前节点，然后转而删除s。这样就把“删双子节点”转化成“删至多单子节点”，简化后续处理。

TreeNode<K,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和x，x是替换上来的节点（可能为null）。方法体是一个大循环，x不断上移，直到x是根或者x是红色。

static <K,V> TreeNode<K,V> balanceDeletion(TreeNode<K,V> root, TreeNode<K,V> x) { for (TreeNode<K,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 { TreeNode<K,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？因为情况四处理完，整棵树的红黑性质已经恢复，不需要再向上回溯。x=root只是让循环条件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和实际元素数不符，按这个顺序查：

1. 确认是否走了removeNode。如果自定义了子类覆盖remove，可能没调super。
2. 检查afterNodeRemoval钩子是否抛异常。钩子在size--之后调用，抛异常会导致size已减但节点还在。
3. 多线程环境下，HashMap本身不安全，size错乱是正常的，换ConcurrentHashMap。
4. 检查是否有并发修改导致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可能为null，root也失去引用。这个分支保证不会NPE。

但要注意，root.parent != null时调root.root()找真正的根。因为TreeNode的parent链可能指向的不是根，需要一路向上找。这个操作是O(log n)，但只在删除时做一次，可以接受。

5.4 balanceDeletion的null安全

balanceDeletion里大量判断null，因为x可能是null（删除的是叶子节点），xpr也可能为null（兄弟不存在）。这些null检查不是防御性编程，而是真实会发生的场景。比如删除一个没有兄弟的黑色叶子，x为null，xpr也为null，直接走x = xp上移。

写类似红黑树代码时，null检查必须完备，否则很容易NPE。我建议在纸上画出所有可能的结构，逐个验证null分支。

5.5 常见问题速查表

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和实际节点数不符。这样能快速定位到出问题的删除操作，比全量日志高效得多。