ConcurrentHashMap
在JDK 8中ConcurrentHashMap存储结构如下，它由数组、单向链表、红黑树组成。
它在HashMap的基础上，提供了并发安全的实现，通过对指定Node加锁来保证更新的安全性。
构造函数
1
2
3
4
5
6
7
8
| public ConcurrentHashMap(int initialCapacity) {
if (initialCapacity < 0)
throw new IllegalArgumentException();
int cap = ((initialCapacity >= (MAXIMUM_CAPACITY >>> 1)) ?
MAXIMUM_CAPACITY :
tableSizeFor(initialCapacity + (initialCapacity >>> 1) + 1));
this.sizeCtl = cap;
}
|
- 如果指定初始容量，则创建为初始容量两倍的大小的数组
- 未指定容量，则默认大小为16
JDK 7中的实现
在JDK 7中的ConcurrentHashMap基本沿用了HashMap的设计，即数组加链表。但是，他的数组设计不太一样，有拆分成了一个大数组Segment和Segment内部的小数组HashEntry
每个Segment都继承自ReentranLock，锁之间彼此独立，多线程操作多个Segment相互独立。Segment默认大小是16，扩容的时候Segment的内部可以扩容，不是整个ConcurrentHashMap扩容，而是每个Segment独立扩容
JDK 8中的实现
1
| private transient volatile int sizeCtl;
|
在JDK 1.8以及后版本，取消了分段锁，所有数据都在一个大的HashMap中。总体结构上和HashMap非常相似。使用红黑树，提升读写效率，解决Hash冲突。对每个头节点分别加锁，即并发度Node数组的长度。这个可以体现锁粒度的细化特征
新插入一个元素的流程如下：通过使用CAS和Synchronized来保证线程安全：
CAS：
- 多线程初始化的时候通过
CAS设置sizeCtl=-1，来获取初始化的权力。其他线程自旋等待
- 插入的时候如果在该哈希桶第一次插入使用
CAS来实现
Synchronized
- 将新的
Node节点按链表或红黑树的方式插入到合适的位置，使用Synchronized来对头节点加锁
关键参数sizeCtl，它用于管理表的初始化、扩容和并发操作的状态
- 其值为负值（-1或更小），表示哈希表正在进行初始化操作。当一个线程成功将
sizeCtl的值设置为负值时，它获取了初始化的控制权，并负责初始化哈希表的操作。其他线程需要等待该线程完成初始化
- 其值为正值，表示哈希表的下一个扩容阈值。当哈希表的元素数量达到了
sizeCtl的值时，就会触发扩容操作
- sizeCtl为0，代表数组未初始化，且数组的初始容量为16
initialTable
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| private final Node<K,V>[] initTable() {
Node<K,V>[] tab; int sc;
while ((tab = table) == null || tab.length == 0) {
if ((sc = sizeCtl) < 0)
Thread.yield();
else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
try {
if ((tab = table) == null || tab.length == 0) {
int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
@SuppressWarnings("unchecked")
Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
table = tab = nt;
sc = n - (n >>> 2);
}
} finally {
sizeCtl = sc;
}
break;
}
}
return tab;
}
|
- 如果sizeCtl<0，表明有其他线程在初始化，让出CPU使用权
- 否则，自旋设置sizeCtrl的值为-1
- 并再次检查table是否为null
Put方法
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
| final V putVal(K key, V value, boolean onlyIfAbsent) {
if (key == null || value == null) throw new NullPointerException();
int hash = spread(key.hashCode());
int binCount = 0;
for (Node<K,V>[] tab = table;;) {
Node<K,V> f; int n, i, fh;
if (tab == null || (n = tab.length) == 0)
tab = initTable();
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
if (casTabAt(tab, i, null,
new Node<K,V>(hash, key, value, null)))
break;
}
else if ((fh = f.hash) == MOVED)
tab = helpTransfer(tab, f);
else {
V oldVal = null;
synchronized (f) {
if (tabAt(tab, i) == f) {
if (fh >= 0) {
binCount = 1;
for (Node<K,V> e = f;; ++binCount) {
K ek;
if (e.hash == hash &&
((ek = e.key) == key ||
(ek != null && key.equals(ek)))) {
oldVal = e.val;
if (!onlyIfAbsent)
e.val = value;
break;
}
Node<K,V> pred = e;
if ((e = e.next) == null) {
pred.next = new Node<K,V>(hash, key,
value, null);
break;
}
}
}
else if (f instanceof TreeBin) {
Node<K,V> p;
binCount = 2;
if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
value)) != null) {
oldVal = p.val;
if (!onlyIfAbsent)
p.val = value;
}
}
}
}
if (binCount != 0) {
if (binCount >= TREEIFY_THRESHOLD)
treeifyBin(tab, i);
if (oldVal != null)
return oldVal;
break;
}
}
}
addCount(1L, binCount);
return null;
}
|
