这么回答面试官之--ConcurrentHashMap如何put?
程序员文章站
2022-05-12 11:30:07
...
ConCurrentHashMap的put操作主要由putVal()方法实现,该方法中对value的插入,采用了CAS操作和synchronized的操作,从而保证了并发环境下的安全性。
put步骤大致如下:
- 通过key计算得到hashcode
- 判断是否需要进行初始化(采用了延迟初始化的策略Lazy table initialization minimizes footprint until first use)
- 利用hash值定位Node,如果当前位置没有Node,则依据CAS机制尝试插入。如果插入失败,则通过自旋保证插入成功
- 判断是否需要进行扩容,如果需要进行扩容,则执行helpTransfer方法
- 如果是在无需进行初始化,hash值计算得到的位置存在Node,并且无需扩容的情况下,则利用synchronized锁来写入数据
- 上述操作后,如果当前数量超过了TREEIFY_THRESHOLD(8,跟HashMap中的值大小相同),则转化为红黑树结构。(注意,上述标蓝的4步,只会执行其中一步)
ConCurrentHashMap的put操作的源码如下(含注释):
final V putVal(K key, V value, boolean onlyIfAbsent) {
if (key == null || value == null) throw new NullPointerException();
// 根据key计算出hash code
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) {
// 根据计算得出的hash定位Node的位置,如果为空,则依据CAS机制尝试插入,如果失败,则通过自旋保证成功
if (casTabAt(tab, i, null,
new Node<K,V>(hash, key, value, null)))
break; // no lock when adding to empty bin
}
// 判断是否需要扩容
else if ((fh = f.hash) == MOVED)
tab = helpTransfer(tab, f);
else {
// 利用synchronized锁进行写入数据
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;
}
}
}
}
// 如果数量大于TREEIFY_THRESHOLD,则转化为红黑树
if (binCount != 0) {
if (binCount >= TREEIFY_THRESHOLD)
treeifyBin(tab, i);
if (oldVal != null)
return oldVal;
break;
}
}
}
addCount(1L, binCount);
return null;
}