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
|
public class ConcurrentHashMap<K,V> extends AbstractMap<K,V> implements ConcurrentMap<K,V>,
Serializable {
/* --------- 常量及成员变量的设计 几乎与HashMap相差无几 -------- */
/**
* 最大容量
*/
private static final int MAXIMUM_CAPACITY = 1 << 30;
/**
* 默认初始容量
*/
private static final int DEFAULT_CAPACITY = 16;
/**
* 单个数组最大容量
*/
static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
/**
* 默认并发等级，也就分成多少个单独上锁的区域
*/
private static final int DEFAULT_CONCURRENCY_LEVEL = 16;
/**
* 扩容因子
*/
private static final float LOAD_FACTOR = 0.75f;
/**
*
*/
transient volatile Node<K,V>[] table;
/**
*
*/
private transient volatile Node<K,V>[] nextTable;
/* --------- 系列构造方法，依然推荐在初始化时根据实际情况设置好初始容量 -------- */
public ConcurrentHashMap() {
}
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;
}
public ConcurrentHashMap(Map<? extends K, ? extends V> m) {
this.sizeCtl = DEFAULT_CAPACITY;
putAll(m);
}
public ConcurrentHashMap(int initialCapacity, float loadFactor) {
this(initialCapacity, loadFactor, 1);
}
public ConcurrentHashMap(int initialCapacity,
float loadFactor, int concurrencyLevel) {
if (!(loadFactor > 0.0f) || initialCapacity < 0 || concurrencyLevel <= 0)
throw new IllegalArgumentException();
if (initialCapacity < concurrencyLevel) // Use at least as many bins
initialCapacity = concurrencyLevel; // as estimated threads
long size = (long)(1.0 + (long)initialCapacity / loadFactor);
int cap = (size >= (long)MAXIMUM_CAPACITY) ?
MAXIMUM_CAPACITY : tableSizeFor((int)size);
this.sizeCtl = cap;
}
/**
* ConcurrentHashMap 的核心就在于其put元素时 利用synchronized局部锁 和
* CAS乐观锁机制 大大提升了本集合的并发能力，比JDK7的分段锁性能更强
*/
public V put(K key, V value) {
return putVal(key, value, false);
}
/**
* 当前指定数组位置无元素时，使用CAS操作 将 Node键值对 放入对应的数组下标。
* 出现hash冲突，则用synchronized局部锁锁住，若当前hash对应的节点是链表的头节点，遍历链表，
* 若找到对应的node节点，则修改node节点的val，否则在链表末尾添加node节点；倘若当前节点是
* 红黑树的根节点，在树结构上遍历元素，更新或增加节点
*/
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) {
// 注意！这是一个CAS的方法，将新节点放入指定位置，不用加锁阻塞线程
// 也能保证并发安全
if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value, null)))
break; // no lock when adding to empty bin
}
// 当前Map在扩容，先协助扩容，在更新值
else if ((fh = f.hash) == MOVED)
tab = helpTransfer(tab, f);
else { // hash冲突
V oldVal = null;
// 局部锁，有效减少锁竞争的发生
synchronized (f) { // 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;
}
}
}
}
// 链表节点超过了8，链表转为红黑树
if (binCount != 0) {
if (binCount >= TREEIFY_THRESHOLD)
treeifyBin(tab, i);
if (oldVal != null)
return oldVal;
break;
}
}
}
// 统计节点个数，检查是否需要resize
addCount(1L, binCount);
return null;
}
}
|
