ConcurrentHashMap源码解析_05 get、remove方法

• 前面几篇文章分析了并发HashMap的put方法及其相关方法，transfer方法，那么接下来本篇文章相对之前几篇难度会小一些。
• 本篇文章介绍ConcurrentHashMap的get方法和remove方法。

1、get方法

get方法：获取元素，根据目标key所在桶的第一个元素的不同采用不同的方式获取元素，关键点在于find()方法的重写。

public V get(Object key) { // tab 引用map.table // e 当前元素(用于循环遍历) // p 目标节点 // n table数组长度 // eh 当前元素hash // ek 当前元素key Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek; // 根据key.hashCode()计算hash: 扰动运算后得到得到更散列的hash值 int h = spread(key.hashCode()); // -------------------------------------------------------------------------------- // CASE1: // 如果元素所在的桶存在且里面有元素 // 条件一：(tab = table) != null // 		true -> 表示已经put过数据，并且map内部的table也已经初始化完毕 // 		false -> 表示创建完map后，并没有put过数据，map内部的table是延迟初始化的，只有第一次写数据时会触发初始化创建table逻辑 // 条件二：(n = tab.length) > 0 如果为 true-> 表示table已经初始化 // 条件三：(e = tabAt(tab, (n - 1) & h)) != null // 		true -> 当前key寻址的桶位有值 // 		false -> 当前key寻址的桶位中是null，是null直接返回null if ((tab = table) != null && (n = tab.length) > 0 && (e = tabAt(tab, (n - 1) & h)) != null) { // 进入if代码块内部的前置条件：当前桶位有数据 // 如果第一个元素就是要找的元素，则直接返回 // 对比头结点hash与查询key的hash是否一致 // 条件成立：说明头结点与查询Key的hash值完全一致 if ((eh = e.hash) == h) { // 完全比对 查询key 和 头结点的key // 条件成立：说明头结点就是查询数据 if ((ek = e.key) == key || (ek != null && key.equals(ek))) // 当e的hash值以及e对应的key都匹配目标元素时，则找到了，直接返回~ return e.val; } // -------------------------------------------------------------------------------- // CASE2: eh < 0 // 条件成立：即，hash小于0 分2种情况，是树或者正在扩容,需要借助find方法寻找元素，find的寻找方式依据Node的不同子类有不同的实现方式: // 情况一：eh=-1 是fwd结点 -> 说明当前table正在扩容，且当前查询的这个桶位的数据已经被迁移走了，需要借助fwd结点的内部方法find去查询 // 情况二：eh=-2 是TreeBin节点 -> 需要使用TreeBin 提供的find方法查询。 else if (eh < 0) return (p = e.find(h, key)) != null ? p.val : null; // -------------------------------------------------------------------------------- // CASE3: 前提条件 -> CASE1和CASE2条件不满足！
		// 说明是当前桶位已经形成链表的这种情况: 遍历整个链表寻找元素 while ((e = e.next) != null) { if (e.hash == h && ((ek = e.key) == key || (ek != null && key.equals(ek)))) return e.val; } } return null;
}

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
  
41
  
42
  
43
  
44
  
45
  
46
  
47
  
48
  
49
  
50
  
51
  
52
  
53
  
54
  
55
  
56
 

1.1 ForwardingNode 内部类(FWD结点)

在get方法CASE2中，eh < 0会分2中情况：

• 情况一：eh=-1 是fwd结点 -> 说明当前table正在扩容，且当前查询的这个桶位的数据已经被迁移走了，需要借助fwd结点的内部方法find去查询。
• 情况二：eh = -2 是TreeBin节点 -> 需要使用TreeBin 提供的find方法查询。

下面就分析一下情况一，即当前桶位中是fwd结点。我们来分析一下FWD这个内部类，以及其内部的find方法：

static final class ForwardingNode<K,V> extends Node<K,V> { final Node<K,V>[] nextTable; ForwardingNode(Node<K,V>[] tab) { super(MOVED, null, null, null); this.nextTable = tab; } // fwd结点的find方法： Node<K,V> find(int h, Object k) { // loop to avoid arbitrarily deep recursion on forwarding nodes // tab 一定不为空：整个ConcurrentHashMap源码中，只有一个地方实例化ForwardingNode，就是在transfer迁移数据方法中执行了：ForwardingNode<K,V> fwd = new ForwardingNode<K,V>(nextTab);（当某个桶位数据处理完毕后，将此桶位设置为fwd节点，其它写线程或读线程看到后，会有不同逻辑） Node<K,V>[] tab = nextTable; // ------------------------------------------------------------------------------ // 自旋1 outer: for (;;) { // n 表示为扩容而创建的新表的长度 // e 表示在扩容而创建新表时，使用寻址算法得到的桶位头结点 Node<K,V> e; int n; // 条件一：永远不成立 // 条件二：永远不成立 // 条件三：永远不成立 // 条件四：在新扩容表中重新路由定位 hash 对应的头结点 // true ->  1.在oldTable中对应的桶位在迁移之前就是null // false -> 2.扩容完成后，有其它写线程，将此桶位设置为了null if (k == null || tab == null || (n = tab.length) == 0 || (e = tabAt(tab, (n - 1) & h)) == null) return null; // --------------------------------------------------------------------------- // 自旋2 // 前置条件：扩容后的表对应hash的桶位一定不是null，e为此桶位的头结点 // e可能为哪些node类型？ //		1.node 类型 //		2.TreeBin 类型 //		3.FWD类型 for (;;) { // eh 新扩容后表指定桶位的当前节点的hash // ek 新扩容后表指定桶位的当前节点的key int eh; K ek; // CASE1条件成立：说明新扩容后的表，当前命中桶位中的数据，即为查询想要数据。 if ((eh = e.hash) == h && ((ek = e.key) == k || (ek != null && k.equals(ek)))) // 直接将e返回~ return e; // CASE2: eh < 0 时 // 1.TreeBin 类型  // 2.FWD类型（新扩容的表，在并发很大的情况下，可能在此方法再次拿到FWD类型），即可能又发生了扩容 if (eh < 0) { // 判断是否是FWD结点 if (e instanceof ForwardingNode) { // 是FWD结点 tab = ((ForwardingNode<K,V>)e).nextTable; // 跳转到自旋1 continue outer; } else// 不是FWD结点 // 说明此桶位 为 TreeBin 节点，使用TreeBin.find 查找红黑树中相应节点。 return e.find(h, k); } // 前置条件：当前桶位头结点 并没有命中查询，说明此桶位是链表 // 1.将当前元素指向链表的下一个元素 // 2.判断当前元素的下一个位置是否为空 // true -> 说明迭代到链表末尾，未找到对应的数据，返回Null if ((e = e.next) == null) return null; } } }
}

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
  
41
  
42
  
43
  
44
  
45
  
46
  
47
  
48
  
49
  
50
  
51
  
52
  
53
  
54
  
55
  
56
  
57
  
58
  
59
  
60
  
61
  
62
  
63
  
64
  
65
  
66
  
67
  
68
  
69
  
70
  
71
  
72
  
73
 

小节：

（1）hash到元素所在的桶；

（2）如果桶中第一个元素就是该找的元素，直接返回；

（3）如果是树或者正在迁移元素，则调用各自Node子类的find()方法寻找元素；

（4）如果是链表，遍历整个链表寻找元素；

（5）获取元素没有加锁；

2、remove方法

remove方法：删除元素跟添加元素一样，都是先找到元素所在的桶，然后采用分段锁的思想锁住整个桶，再进行操作。

public V remove(Object key) {
	// 调用替换节点方法 return replaceNode(key, null, null);
}

/**
 * 结点替换：
 * 参数1：Object key -> 就表示当前结点的key
 * 参数2：V value -> 要替换的目标值
 * 参数3：Object cv（compare Value） -> 
 * 如果cv不为null，则需要既比对key，还要比对cv，这样个参数都一致，才能替换成目标值
 */
final V replaceNode(Object key, V value, Object cv) { // 计算key经过扰动运算后得到的hash int hash = spread(key.hashCode()); // 自旋 for (Node<K,V>[] tab = table;;) { // f表示桶位头结点 // n表示当前table数组长度 // i表示hash命中桶位下标 // fh表示桶位头结点hash Node<K,V> f; int n, i, fh; // ---------------------------------------------------------------------------- // CASE1： // 条件一：tab == null   // true -> 表示当前map.table尚未初始化..   // false -> 表示当前map.table已经初始化 // 条件二：(n = tab.length) == 0   // true -> 表示当前map.table尚未初始化..   // false -> 已经初始化 // 条件三：(f = tabAt(tab, i = (n - 1) & hash)) == null  // true -> 表示命中桶位中为null，直接break if (tab == null || (n = tab.length) == 0 || (f = tabAt(tab, i = (n - 1) & hash)) == null) // 如果目标key所在的桶不存在，跳出循环返回null break; // ---------------------------------------------------------------------------- // CASE2： // 前置条件CASE2 ~ CASE3：当前桶位不是null // 条件成立：fwd结点，说明当前table正在扩容中，当前是个写操作，所以当前线程需要协助table完成扩容。 else if ((fh = f.hash) == MOVED) // 如果正在扩容中，则协助扩容 tab = helpTransfer(tab, f); // ---------------------------------------------------------------------------- // CASE3: // 前置条件CASE2 ~ CASE3：当前桶位不是null // 当前桶位是一个有数据的桶位，桶中可能是 "链表"也可能是"红黑树"TreeBin else { // 保留替换之前的数据引用 V oldVal = null; // 校验标记,在下面的CASEn中的if判断使用：标记是否处理过 boolean validated = false; // 加锁当前桶位头结点，加锁成功之后会进入代码块。 synchronized (f) { // 判断sync加锁是否为当前桶位头节点，防止其它线程，在当前线程加锁成功之前，修改过桶位 的头结点，导致锁错对象！ // -------------------------------------------------------------------- // CASE4:  tabAt(tab, i) == f 再次验证当前桶第一个元素是否被修改过 // 条件成立：说明当前桶位头结点仍然为f，其它线程没修改过！ if (tabAt(tab, i) == f) { // -------------------------------------------------------------------- // CASE5:  fh >= 0  // 条件成立：说明桶位为链表或者单个node if (fh >= 0) { // 校验标记置为true validated = true; // e 表示当前循环处理结点 // pred 表示当前循环节点的上一个节点 Node<K,V> e = f, pred = null; // 遍历链表寻找目标节点 for (;;) { // 表示当前节点key K ek; // ------------------------------------------------------------ // CASE6: // 条件一：e.hash == hash  //			true->说明当前节点的hash与查找节点hash一致 // 条件二：((ek = e.key) == key || (ek != null && key.equals(ek))) // CASE6的if条件成立，说明key 与查询的key完全一致。 if (e.hash == hash && ((ek = e.key) == key || (ek != null && key.equals(ek)))) { // 找到了目标节点：当前节点的value， V ev = e.val; // ----------------------------------------------------- // CASE7:  检查目标节点旧value是否等于cv // 条件一：cv == null  //			true -> 替换的值为null那么就是一个删除操作 // 条件二：cv == ev || (ev != null && cv.equals(ev))  //			true -> 那么是一个替换操作 if (cv == null || cv == ev || (ev != null && cv.equals(ev))) { // 删除 或者 替换 // 将当前节点的值 赋值给 oldVal 后续返回会用到~ oldVal = ev; // 目标value不等于null // 如果条件成立：说明当前是一个替换操作 if (value != null) // 直接替换 e.val = value; // 条件成立：说明当前节点非头结点 else if (pred != null) // 如果前置节点不为空，删除当前节点： // 让当前节点的上一个节点，指向当前节点的下一个节点。 pred.next = e.next; // 条件成里：说明当前节点即为头结点 else // 如果前置节点为空，说明是桶中第一个元素，删除之： // 只需要将桶位设置为头结点的下一个节点。 setTabAt(tab, i, e.next); } break; } pred = e; // 遍历到链表尾部还没找到元素，跳出循环 if ((e = e.next) == null) break; } } // -------------------------------------------------------------------- // CASE8:  f instanceof TreeBin // 条件成立：TreeBin节点。 else if (f instanceof TreeBin) { // 校验标记置为true validated = true; // 转换为实际类型 TreeBin t TreeBin<K,V> t = (TreeBin<K,V>)f; // r 表示 红黑树根节点 // p 表示 红黑树中查找到对应key 一致的node TreeNode<K,V> r, p; // 遍历树找到了目标节点： // 条件一：(r = t.root) != null 理论上是成立 // 条件二：TreeNode.findTreeNode 以当前节点为入口，向下查找key（包括本身节点） // true->说明查找到相应key 对应的node节点，会赋值给p if ((r = t.root) != null && (p = r.findTreeNode(hash, key, null)) != null) { // 保存p.val 到pv V pv = p.val; // 检查目标节点旧value是否等于cv： // 条件一：cv == null 成立：不必对比value，就做替换或者删除操作 // 条件二：cv == pv ||(pv != null && cv.equals(pv)) 成立：说明“对比值”与当前p节点的值 一致 if (cv == null || cv == pv || (pv != null && cv.equals(pv))) { // 替换或者删除操作 oldVal = pv; // 如果value不为空则替换旧值 // 条件成立：替换操作 if (value != null) p.val = value; // 如果value为空则删除元素 // 删除操作 else if (t.removeTreeNode(p)) // 如果删除后树的元素个数较少则退化成链表 // t.removeTreeNode(p)这个方法返回true表示删除节点后树的元素个数较少 setTabAt(tab, i, untreeify(t.first)); } } } } } // ---------------------------------------------------------------------------- // CASEn: 如果处理过，不管有没有找到元素都返回 // 当其他线程修改过桶位头结点时，当前线程 sync 头结点 锁错对象时，validated 为false，会进入下次for自旋: if (validated) { // 如果找到了元素，返回其旧值 if (oldVal != null) { // 替换的值 为null，说明当前是一次删除操作，oldVal ！=null 成立，说明删除成功，更新当前元素个数计数器。 // 如果要替换的值为空，元素个数减1 if (value == null) addCount(-1L, -1); return oldVal; } break; } } } // 没找到元素返回空 return null;
}

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
  
41
  
42
  
43
  
44
  
45
  
46
  
47
  
48
  
49
  
50
  
51
  
52
  
53
  
54
  
55
  
56
  
57
  
58
  
59
  
60
  
61
  
62
  
63
  
64
  
65
  
66
  
67
  
68
  
69
  
70
  
71
  
72
  
73
  
74
  
75
  
76
  
77
  
78
  
79
  
80
  
81
  
82
  
83
  
84
  
85
  
86
  
87
  
88
  
89
  
90
  
91
  
92
  
93
  
94
  
95
  
96
  
97
  
98
  
99
  
100
  
101
  
102
  
103
  
104
  
105
  
106
  
107
  
108
  
109
  
110
  
111
  
112
  
113
  
114
  
115
  
116
  
117
  
118
  
119
  
120
  
121
  
122
  
123
  
124
  
125
  
126
  
127
  
128
  
129
  
130
  
131
  
132
  
133
  
134
  
135
  
136
  
137
  
138
  
139
  
140
  
141
  
142
  
143
  
144
  
145
  
146
  
147
  
148
  
149
  
150
  
151
  
152
  
153
  
154
  
155
  
156
  
157
  
158
  
159
  
160
  
161
  
162
  
163
  
164
  
165
  
166
  
167
  
168
  
169
  
170
  
171
  
172
  
173
  
174
  
175
  
176
  
177
  
178
  
179
  
180
  
181
  
182
  
183
  
184
  
185
  
186
  
187
  
188
  
189
  
190
  
191
  
192
  
193
 

小节：

（1）计算hash；

（2）如果所在的桶不存在，表示没有找到目标元素，返回；

（3）如果正在扩容，则协助扩容完成后再进行删除操作；

（4）如果是以链表形式存储的，则遍历整个链表查找元素，找到之后再删除；

（5）如果是以树形式存储的，则遍历树查找元素，找到之后再删除；

（6）如果是以树形式存储的，删除元素之后树较小，则退化成链表；

（7）如果确实删除了元素，则整个map元素个数减1，并返回旧值；

（8）如果没有删除元素，则返回null；

本篇文章结束，ConcurrentHashMap的大部分知识点分析完毕，下面一篇文章最后再分析一下TreeBin就收尾了！

文章来源: csp1999.blog.csdn.net，作者：兴趣使然の草帽路飞，版权归原作者所有，如需转载，请联系作者。

原文链接：csp1999.blog.csdn.net/article/details/116487477