HashMap 的 remove 方法是如何实现的？

结论先行：remove 先用扰动后的 hash 定位桶，再沿链表或红黑树找到 hash 与 equals 都匹配的节点，把它从链上摘掉（或在树中删除），最后 modCount++、size--、回调 afterNodeRemoval。它不会缩容：空出来的桶只是置为 null，数组本身要等下一次扩容或重建才释放。

1. 两个公开入口

matchValue 为 true 时要求 value 也相等，常用于“值符合预期才删除”的 CAS 式清理；movable 为 false 表示删除时不要移动其他节点，迭代器场景会用到。

2. 链表删除的指针操作

情况一：删除的不是桶头
  tab[i] -> A -> B -> C -> D
                  ^node
  p 停在 B 的前驱 A 上，执行 p.next = node.next
  结果：A -> C -> D
情况二：删除的就是桶头
  tab[i] -> A -> B -> C
            ^node == p
  执行 tab[index] = node.next
  结果：tab[i] -> B -> C

源码里用一个 node == p 的判断同时覆盖两种情况：p 既是遍历指针，也是命中节点的前驱。

3. 源码：removeNode

final Node<K,V> removeNode(int hash, Object key, Object value,
                           boolean matchValue, boolean movable) {
    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 {                                     // p 始终是 node 的前驱
                    if (e.hash == hash && ((k = e.key) == key ||
                            (key != null && key.equals(k)))) {
                        node = e;
                        break;
                    }
                    p = e;
                } while ((e = e.next) != null);
            }
        }
        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;
        }
    }
    return null;
}

4. 红黑树删除的两个特殊点

• 不搬 key/value：普通红黑树删除常把后继节点的值搬到待删节点上，但 HashMap 的 next 链被迭代器独立引用着，搬值会破坏遍历，所以 removeTreeNode 改为交换树中节点的链接关系。
• 可能顺手退化：删除后如果树太小（根为空、左右子树不足），直接把整棵树 untreeify 成链表，避免小桶继续维护平衡。

5. 代码：遍历删除的三种写法

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Map;

public class RemoveDemo {
    public static void main(String[] args) {
        Map<String, Integer> map = new HashMap<>();
        map.put("a", 1);
        map.put("b", 2);
        map.put("c", 3);

        // 错误写法：for (String k : map.keySet()) if (k.equals("a")) map.remove(k);
        // 会抛 ConcurrentModificationException

        // 写法一：迭代器，remove 会同步 expectedModCount
        Iterator<String> it = map.keySet().iterator();
        while (it.hasNext()) {
            if (it.next().equals("a")) it.remove();
        }

        // 写法二：JDK 8 的 removeIf，内部同样走迭代器
        map.entrySet().removeIf(e -> e.getValue() >= 3);

        // 写法三：先收集 key，再统一删除（适合复杂条件）
        List<String> toRemove = new ArrayList<>();
        for (Map.Entry<String, Integer> e : map.entrySet()) {
            if (e.getValue() < 0) toRemove.add(e.getKey());
        }
        toRemove.forEach(map::remove);

        System.out.println(map); // 输出：{b=2}
    }
}

6. 删除之后容量会变吗

• 不会缩容。size 减一，table.length 与 threshold 都不变。
• 被删节点所在的桶置为 null，但数组对象本身仍占内存；大量 put/remove 交替后，表可能长期维持在高水位。
• clear() 也只把每个桶置空、size 归零，不会缩小数组；长期存活的小 Map 若曾膨胀过，重建实例比等它缩容更实际。
• 树桶删除到阈值以下会退化为链表，这是结构变化，但同样不影响数组长度。

常见追问

• 删除时为什么要重新计算 hash？ 表里存的是扰动后的 hash，remove 拿到的是原始 key，必须重新 spread 才能定位。
• null key 能删吗？ 能，hash(null) = 0，走同一条流程。
• 删除不存在的 key 返回什么？ 返回 null；但如果 key 存在而值为 null，也返回 null，需要 containsKey 区分。
• 改了 key 的字段后再删会怎样？ hashCode 变了，定位不到原桶，删不掉也查不到，等价于内存泄漏。
• LinkedHashMap 删除时做了什么额外动作？ afterNodeRemoval 里把节点从维护插入顺序的双向链表上摘掉。

小结

remove 的流程与 get 高度对称：定位桶 → 找节点 → 摘链/删树 → 更新计数。真正需要记住的细节是三个：node == p 区分删桶头还是删中间节点；树删除不搬值、只改链接；删除不缩容，长期高水位的小 Map 应考虑重建。写业务代码时，遍历删除统一用迭代器或 removeIf，不要直接调 map.remove。