concurrenthashmap源码解析（Java1.7）
使用与获取全局信息的方法并不频繁的时候
01.在 ConcurrentHashMap 中，不允许用 null 作为键和值。
02.ConcurrentHashMap 使用分段锁（减少锁粒度）技术，将数据分成一段一段的存储，然后给每一段数据配一把锁，当一个线程占用锁访问其中一个段数据的时候，其他段的数据也能被其他线程访问，能够实现真正的并发访问。
1.源码结构（从上往下）
重要字段
字段
ConcurrentHashMap列表条目。请注意，这从来没有导出
hash函数，段定义
构造函数
常用的方法：
迭代器支持
序列化支持
2.数据结构
默认情况下分为16个段。
|
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
|
static
final
class
HashEntry<K,V> {
final
int
hash;
final
K key;
volatile
V value;
volatile
HashEntry<K,V> next;
HashEntry(
int
hash, K key, V value, HashEntry<K,V> next) {
this
.hash = hash;
this
.key = key;
this
.value = value;
this
.next = next;
}
/**
* Sets next field with volatile write semantics. (See above
* about use of putOrderedObject.)
*/
final
void
setNext(HashEntry<K,V> n) {
UNSAFE.putOrderedObject(
this
, nextOffset, n);
}
// Unsafe mechanics
static
final
sun.misc.Unsafe UNSAFE;
static
final
long
nextOffset;
static
{
try
{
UNSAFE = sun.misc.Unsafe.getUnsafe();
Class k = HashEntry.
class
;
nextOffset = UNSAFE.objectFieldOffset
(k.getDeclaredField(
"next"
));
}
catch
(Exception e) {
throw
new
Error(e);
}
}
}
|
|
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
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
|
static
final
class
Segment<K,V>
extends
ReentrantLock
implements
Serializable {
private
static
final
long
serialVersionUID = 2249069246763182397L;
static
final
int
MAX_SCAN_RETRIES =
Runtime.getRuntime().availableProcessors() >
1
?
64
:
1
;
transient
volatile
HashEntry<K,V>[] table;
transient
int
count;
transient
int
modCount;
transient
int
threshold;
final
float
loadFactor;
Segment(
float
lf,
int
threshold, HashEntry<K,V>[] tab) {
this
.loadFactor = lf;
this
.threshold = threshold;
this
.table = tab;
}
final
V put(K key,
int
hash, V value,
boolean
onlyIfAbsent) {
HashEntry<K,V> node = tryLock() ?
null
:
scanAndLockForPut(key, hash, value);
V oldValue;
try
{
HashEntry<K,V>[] tab = table;
int
index = (tab.length -
1
) & hash;
HashEntry<K,V> first = entryAt(tab, index);
for
(HashEntry<K,V> e = first;;) {
if
(e !=
null
) {
K k;
if
((k = e.key) == key ||
(e.hash == hash && key.equals(k))) {
oldValue = e.value;
if
(!onlyIfAbsent) {
e.value = value;
++modCount;
}
break
;
}
e = e.next;
}
else
{
if
(node !=
null
)
node.setNext(first);
else
node =
new
HashEntry<K,V>(hash, key, value, first);
int
c = count +
1
;
if
(c > threshold && tab.length < MAXIMUM_CAPACITY)
rehash(node);
else
setEntryAt(tab, index, node);
++modCount;
count = c;
oldValue =
null
;
break
;
}
}
}
finally
{
unlock();
}
return
oldValue;
}
/**
* Doubles size of table and repacks entries, also adding the
* given node to new table
*/
@SuppressWarnings
(
"unchecked"
)
private
void
rehash(HashEntry<K,V> node) {
HashEntry<K,V>[] oldTable = table;
int
oldCapacity = oldTable.length;
int
newCapacity = oldCapacity <<
1
;
threshold = (
int
)(newCapacity * loadFactor);
HashEntry<K,V>[] newTable =
(HashEntry<K,V>[])
new
HashEntry[newCapacity];
int
sizeMask = newCapacity -
1
;
for
(
int
i =
0
; i < oldCapacity ; i++) {
HashEntry<K,V> e = oldTable[i];
if
(e !=
null
) {
HashEntry<K,V> next = e.next;
int
idx = e.hash & sizeMask;
if
(next ==
null
)
// Single node on list
newTable[idx] = e;
else
{
// Reuse consecutive sequence at same slot
HashEntry<K,V> lastRun = e;
int
lastIdx = idx;
for
(HashEntry<K,V> last = next;
last !=
null
;
last = last.next) {
int
k = last.hash & sizeMask;
if
(k != lastIdx) {
lastIdx = k;
lastRun = last;
}
}
newTable[lastIdx] = lastRun;
// Clone remaining nodes
for
(HashEntry<K,V> p = e; p != lastRun; p = p.next) {
V v = p.value;
int
h = p.hash;
int
k = h & sizeMask;
HashEntry<K,V> n = newTable[k];
newTable[k] =
new
HashEntry<K,V>(h, p.key, v, n);
}
}
}
}
int
nodeIndex = node.hash & sizeMask;
// add the new node
node.setNext(newTable[nodeIndex]);
newTable[nodeIndex] = node;
table = newTable;
}
private
HashEntry<K,V> scanAndLockForPut(K key,
int
hash, V value) {
HashEntry<K,V> first = entryForHash(
this
, hash);
HashEntry<K,V> e = first;
HashEntry<K,V> node =
null
;
int
retries = -
1
;
// negative while locating node
while
(!tryLock()) {
HashEntry<K,V> f;
// to recheck first below
if
(retries <
0
) {
if
(e ==
null
) {
if
(node ==
null
)
// speculatively create node
node =
new
HashEntry<K,V>(hash, key, value,
null
);
retries =
0
;
}
else
if
(key.equals(e.key))
retries =
0
;
else
e = e.next;
}
else
if
(++retries > MAX_SCAN_RETRIES) {
lock();
break
;
}
else
if
((retries &
1
) ==
0
&&
(f = entryForHash(
this
, hash)) != first) {
e = first = f;
// re-traverse if entry changed
retries = -
1
;
}
}
return
node;
}
private
void
scanAndLock(Object key,
int
hash) {
// similar to but simpler than scanAndLockForPut
HashEntry<K,V> first = entryForHash(
this
, hash);
HashEntry<K,V> e = first;
int
retries = -
1
;
while
(!tryLock()) {
HashEntry<K,V> f;
if
(retries <
0
) {
if
(e ==
null
|| key.equals(e.key))
retries =
0
;
else
e = e.next;
}
else
if
(++retries > MAX_SCAN_RETRIES) {
lock();
break
;
}
else
if
((retries &
1
) ==
0
&&
(f = entryForHash(
this
, hash)) != first) {
e = first = f;
retries = -
1
;
}
}
}
final
V remove(Object key,
int
hash, Object value) {
if
(!tryLock())
scanAndLock(key, hash);
V oldValue =
null
;
try
{
HashEntry<K,V>[] tab = table;
int
index = (tab.length -
1
) & hash;
HashEntry<K,V> e = entryAt(tab, index);
HashEntry<K,V> pred =
null
;
while
(e !=
null
) {
K k;
HashEntry<K,V> next = e.next;
if
((k = e.key) == key ||
(e.hash == hash && key.equals(k))) {
V v = e.value;
if
(value ==
null
|| value == v || value.equals(v)) {
if
(pred ==
null
)
setEntryAt(tab, index, next);
else
pred.setNext(next);
++modCount;
--count;
oldValue = v;
}
break
;
}
pred = e;
e = next;
}
}
finally
{
unlock();
}
return
oldValue;
}
final
boolean
replace(K key,
int
hash, V oldValue, V newValue) {
if
(!tryLock())
scanAndLock(key, hash);
boolean
replaced =
false
;
try
{
HashEntry<K,V> e;
for
(e = entryForHash(
this
, hash); e !=
null
; e = e.next) {
K k;
if
((k = e.key) == key ||
(e.hash == hash && key.equals(k))) {
if
(oldValue.equals(e.value)) {
e.value = newValue;
++modCount;
replaced =
true
;
}
break
;
}
}
}
finally
{
unlock();
}
return
replaced;
}
final
V replace(K key,
int
hash, V value) {
if
(!tryLock())
scanAndLock(key, hash);
V oldValue =
null
;
try
{
HashEntry<K,V> e;
for
(e = entryForHash(
this
, hash); e !=
null
; e = e.next) {
K k;
if
((k = e.key) == key ||
(e.hash == hash && key.equals(k))) {
oldValue = e.value;
e.value = value;
++modCount;
break
;
}
}
}
finally
{
unlock();
}
return
oldValue;
}
final
void
clear() {
lock();
try
{
HashEntry<K,V>[] tab = table;
for
(
int
i =
0
; i < tab.length ; i++)
setEntryAt(tab, i,
null
);
++modCount;
count =
0
;
}
finally
{
unlock();
}
}
}
|
3.put方法
流程：
|
1
2
3
4
5
6
7
8
9
10
11
12
|
public
V put(K key, V value) {
Segment<K,V> s;
if
(value ==
null
)
throw
new
NullPointerException();
int
hash = hash(key.hashCode());
int
j = (hash >>> segmentShift) & segmentMask;
//上面两行用于获取段号
if
((s = (Segment<K,V>)UNSAFE.getObject
// nonvolatile; recheck
(segments, (j << SSHIFT) + SBASE)) ==
null
)
// in ensureSegment
s = ensureSegment(j);
//得到段，将数据插入到段中
return
s.put(key, hash, value,
false
);
}
|
|
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
|
static
final
class
Segment<K,V>
extends
ReentrantLock
implements
Serializable {
final
V put(K key,
int
hash, V value,
boolean
onlyIfAbsent) {
HashEntry<K,V> node = tryLock() ?
null
:
//加锁
scanAndLockForPut(key, hash, value);
V oldValue;
try
{
HashEntry<K,V>[] tab = table;
int
index = (tab.length -
1
) & hash;
HashEntry<K,V> first = entryAt(tab, index);
for
(HashEntry<K,V> e = first;;) {
if
(e !=
null
) {
K k;
if
((k = e.key) == key ||
(e.hash == hash && key.equals(k))) {
oldValue = e.value;
if
(!onlyIfAbsent) {
e.value = value;
++modCount;
}
break
;
}
e = e.next;
}
else
{
if
(node !=
null
)
node.setNext(first);
else
node =
new
HashEntry<K,V>(hash, key, value, first);
int
c = count +
1
;
if
(c > threshold && tab.length < MAXIMUM_CAPACITY)
rehash(node);
else
setEntryAt(tab, index, node);
++modCount;
count = c;
oldValue =
null
;
break
;
}
}
}
finally
{
unlock();
//解锁
}
return
oldValue;
}
}
|
|
1
2
3
4
5
6
7
8
9
10
11
|
@SuppressWarnings
(
"unchecked"
)
static
final
<K,V> HashEntry<K,V> entryAt(HashEntry<K,V>[] tab,
int
i) {
return
(tab ==
null
) ?
null
:
(HashEntry<K,V>) UNSAFE.getObjectVolatile
(tab, ((
long
)i << TSHIFT) + TBASE);
}
static
final
<K,V>
void
setEntryAt(HashEntry<K,V>[] tab,
int
i,
HashEntry<K,V> e) {
UNSAFE.putOrderedObject(tab, ((
long
)i << TSHIFT) + TBASE, e);
}
|
04.当系统需要取得全局锁，消耗资源就会比较多。比如size()方法：事实上会先使用无锁的方式求和，如果失败，会先获得所有段的锁再去求和。
concurrenthashmap源码解析（Java1.8）
暂时先偷懒，参考别人的：http://blog.csdn.net/zly9923218/article/details/51420561
本文转自 叫我北北 51CTO博客，原文链接:http://blog.51cto.com/qinbin/2057787
