HashMap集合--基本操作流程的源码可视化

本文主要包含：HashMap 插入过程、扩容过程、查询过程和删除过程的源码可视化
文章对应的视频连接：https://www.bilibili.com/video/BV1wM3KzaE3d/

1. 操作流程

1.1. 插入过程（put(K key, V value)）

插入流程主要涉及四种操作：扩容（首层扩容和阈值扩容）、单节点插入（无哈希冲突的情况）、链表遍历插入（冲突节点不超8个的情况）、红黑树插入。
插入节点的全流程图：

1.2. 扩容过程（resize()）

扩容条件、扩容涉及到的链表挂载、链表树化、树转链表等等，都在前一篇四次扩容的文章中讲到，渐进式的学习HashMap扩容。
HashMap扩容源码可视化
文章链接：https://mp.weixin.qq.com/s/J3kU51hb-GcM4Rsp7QCIFw
视频链接：https://www.bilibili.com/video/BV1wM3KzaE3d/
1.3. 查询过程（get(Object key)）

• 空表或 key == null ：立即返回 null（null key 存储在索引 0）。
  
• 计算 hash、下标 i
  
• 遍历
  
  
  
  • 如果 table 为单链表，逐节点比较 hash 与 key.equals；
    
  • 如果为红黑树，调用 TreeNode 的 getTreeNode，按树结构快速查找（对数复杂度）。
    
  
  

查找元素全流程图：

1.4. 删除过程（remove(Object key)）

最后将展示单链表的节点删除和红黑树节点的删除可视化过程。

• 计算 hash、下标 i。
  
• 定位到槽位的链表或树，找到目标节点。
  
• 单链表：直接断链跳过；红黑树：调用 removeTreeNode 完成删除。
  
• size--，更新 modCount，返回被删节点的值。
  

删除链表节点

跟普通链表删除节点一样简单，下面直接通过动图来理解

删除红黑树节点

对于链表的删除处理是很简单很好理解，但是对于红黑树的删除就会比较复杂。在HashMap中，红黑树节点删除的可视化：

关键步骤大致分为四步：寻找替换节点、进入待删除状态、红黑树平衡调整和最终删除节点。
最主要的两步源码如下，其次就是红黑树数据结构删除过程的理解：
寻找替换：寻找中序后继节点作为替换节点。比如：红黑树左中右序为1、2、3、4，删除了2节点，那么就找3节点作为替换节点；如果删除3节点，那么就找4节点作为替换。对应的源代码如下

1. if (pl != null && pr != null) {
2.         // 如果左右都不为空，找中序的后继节点替换，（右子树最靠左的节点）
3.         TreeNode<K,V> s = pr, sl;
4.         while ((sl = s.left) != null)
5.                 s = sl;
6.                
7.         ...
8. }

复制代码

删除黑节点树平衡：
删除的主要源码如下，已为每一行源码附上注释。

1. // map: 当前所在的 HashMap 实例
2. // tab: 哈希表数组（即 table）
3. // movable=true
4. final void removeTreeNode(HashMap<K,V> map, Node<K,V>[] tab,
5.                           boolean movable) {
6.     int n;
7.     // 如果表为 null 或长度为 0，直接返回（无操作）
8.     if (tab == null || (n = tab.length) == 0)
9.         return;
10.     // 用哈希值定位当前节点所在的桶 index
11.     int index = (n - 1) & hash;
12.     // 获取根节点
13.     TreeNode<K,V> first = (TreeNode<K,V>)tab[index], root = first, rl;
14.     // 从链表中断开当前节点（this），红黑树同时是双向链表这点必须知道，所以才有维护链表的操作
15.     TreeNode<K,V> succ = (TreeNode<K,V>)next, pred = prev;
16.     if (pred == null)
17.         tab[index] = first = succ;
18.     else
19.         pred.next = succ;
20.     if (succ != null)
21.         succ.prev = pred;
22.     // 如果断链后没有剩余节点（即只有当前一个节点），直接返回
23.     if (first == null)
24.         return;
26.     if (root.parent != null)
27.         root = root.root();
28.     if (root == null
29.         || (movable
30.             && (root.right == null
31.                 || (rl = root.left) == null
32.                 || rl.left == null))) {
33.         tab[index] = first.untreeify(map);  // too small
34.         return;
35.     }
36.     // 红黑树删除操作
37.     TreeNode<K,V> p = this, pl = left, pr = right, replacement;
38.     //  处理删除节点p 同时有左右子节点的情况
39.     if (pl != null && pr != null) {
41.         // 如果左右都不为空，找中序的后继替换，（右子树最靠左的节点）
42.         TreeNode<K,V> s = pr, sl;
43.         while ((sl = s.left) != null) // find successor
44.             s = sl;
46.         // 节点颜色交换
47.         boolean c = s.red; s.red = p.red; p.red = c; // swap colors
49.         // 交换结构：把后继节点换上来
50.         TreeNode<K,V> sr = s.right;
51.         TreeNode<K,V> pp = p.parent;
52.         // p 是 s 的直接父节点
53.         if (s == pr) {
54.             p.parent = s;
55.             s.right = p;
56.         }
57.         else {
58.             TreeNode<K,V> sp = s.parent;
59.             if ((p.parent = sp) != null) {
60.                 if (s == sp.left)
61.                     sp.left = p;
62.                 else
63.                     sp.right = p;
64.             }
65.             if ((s.right = pr) != null)
66.                 pr.parent = s;
67.         }
68.         // 调整左子树与父指针：p 的左右清空（它即将被删），s 左右指针都设置好（接替 p）
69.         p.left = null;
70.         if ((p.right = sr) != null)
71.             sr.parent = p;
72.         if ((s.left = pl) != null)
73.             pl.parent = s;
75.         // s 接替 p 成为新的 root 的子节点
76.         if ((s.parent = pp) == null)
77.             root = s;
78.         else if (p == pp.left)
79.             pp.left = s;
80.         else
81.             pp.right = s;
83.         // 设置替换节点
84.         if (sr != null)
85.             replacement = sr;
86.         else
87.             replacement = p;
88.     }
90.     //  处理删除节点p 有一个或没有子节点情况
91.     else if (pl != null)
92.         replacement = pl;
93.     else if (pr != null)
94.         replacement = pr;
95.     else
96.         replacement = p;
98.     // 让 replacement 替换掉 删除节点p 的位置
99.     if (replacement != p) {
100.         TreeNode<K,V> pp = replacement.parent = p.parent;
101.         if (pp == null)
102.             root = replacement;
103.         else if (p == pp.left)
104.             pp.left = replacement;
105.         else
106.             pp.right = replacement;
107.         p.left = p.right = p.parent = null;
108.     }
110.     // 如果删除节点p 是黑节点，需要平衡红黑树
111.     TreeNode<K,V> r = p.red ? root : balanceDeletion(root, replacement);
113.     // 如果 p 等于 replacement，说明删除的节点是叶子节点，断开叶子节点
114.     if (replacement == p) {
115.         TreeNode<K,V> pp = p.parent;
116.         p.parent = null;
117.         if (pp != null) {
118.             if (p == pp.left)
119.                 pp.left = null;
120.             else if (p == pp.right)
121.                 pp.right = null;
122.         }
123.     }
125.     // 将新的 root 移动到链表最前（优化访问）
126.     if (movable)
127.         moveRootToFront(tab, r);
128. }

复制代码

2. 性能与并发考虑

时间复杂度
操作平均时间复杂度最坏时间复杂度备注getO(1)O(log n)红黑树查找最坏 O(log n)putO(1)O(log n)链表树化后插树最坏 O(log n)removeO(1)O(log n)红黑树删除维护平衡 O(log n)resizeO(1)O(n)摊销成本后每次插入 O(1)遍历全部元素O(n)O(n)并发风险
HashMap 非线程安全，在多线程无外部同步时可能出现数据丢失或死循环（扩容时环路）。
多线程并发场景推荐使用 ConcurrentHashMap，或者对 HashMap 外层加锁（如 Collections.synchronizedMap，串行效率低）
3. 在 HashMap 中红黑树同时是双向链表？

链表节点（未树化）：Node 类型，只包含：

1. Node<K,V> {
2.     final int hash;
3.     final K key;
4.     V value;
5.     Node<K,V> next;
6. }

复制代码

✅ 是 单向链表。
树化节点（TreeNode）：扩展自 Node，添加了：
[code]TreeNode extends Node {    TreeNode parent;    TreeNode left;    TreeNode right;    TreeNode prev; //
来源：豆瓜网用户自行投稿发布，如果侵权，请联系站长删除