// 默认为 0 // 当初始化时, 为 -1 // 当扩容时, 为 -(1 + 扩容线程数) // 当初始化或扩容完成后,为 下一次的扩容的阈值大小 private transient volatile int sizeCtl; // 整个 ConcurrentHashMap 就是一个 Node[] static class Nodeimplements Map.Entry {} // hash 表 transient volatile Node [] table;//Node包括键,值,哈希码和Next // 扩容时的 新 hash 表 private transient volatile Node [] nextTable; // 扩容时如果某个 bin 迁移完毕, 用 ForwardingNode 作为旧 table bin 的头结点 static final class ForwardingNode extends Node {} // 用在 compute 以及 computeIfAbsent 时, 用来占位, 计算完成后替换为普通 Node static final class ReservationNode extends Node {} // 作为 treebin 的头节点, 存储 root 和 first static final class TreeBin extends Node {} // 作为 treebin 的节点, 存储 parent, left, right static final class TreeNode extends Node {}
ForwardingNode
// 获取 Node[] 中第 i 个 Node static final构造器分析Node tabAt(Node [] tab, int i) // cas 修改 Node[] 中第 i 个 Node 的值, c 为旧值, v 为新值 static final boolean casTabAt(Node [] tab, int i, Node c, Node v) // 直接修改 Node[] 中第 i 个 Node 的值, v 为新值 static final void setTabAt(Node [] tab, int i, Node v)
构造器三个参数分别是:初始容量,负载因子0.75,并发度。
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);
// tableSizeFor 仍然是保证计算的大小是 2^n, 即 16,32,64 ...
int cap = (size >= (long)MAXIMUM_CAPACITY) ?
MAXIMUM_CAPACITY : tableSizeFor((int)size);
this.sizeCtl = cap;
}
- 如果初始容量小于并发度,那么会将初始容量改为并发度
- 实现了懒惰初始化,在构造方法中仅仅计算了 table 的大小,以后在第一次使用时才会真正创建
public V get(Object key) {
Node[] tab; Node e, p; int n, eh; K ek;
// spread 方法能确保返回结果是正数
int h = spread(key.hashCode());
if ((tab = table) != null && (n = tab.length) > 0 &&
(e = tabAt(tab, (n - 1) & h)) != null) {
// 如果头结点已经是要查找的 key
if ((eh = e.hash) == h) {
if ((ek = e.key) == key || (ek != null && key.equals(ek)))
return e.val;
}
// hash 为负数表示该 bin 在扩容中或是 treebin, 这时调用 find 方法来查找
else if (eh < 0)
return (p = e.find(h, key)) != null ? p.val : null;
// 正常遍历链表, 用 equals 比较
while ((e = e.next) != null) {
if (e.hash == h &&
((ek = e.key) == key || (ek != null && key.equals(ek))))
return e.val;
}
}
return null;
全程未加锁,并发度高
put流程 public V put(K key, V value) {
return putVal(key, value, false);
}
final V putVal(K key, V value, boolean onlyIfAbsent) {
if (key == null || value == null) throw new NullPointerException();
// 其中 spread 方法会综合高位低位, 具有更好的 hash 性
int hash = spread(key.hashCode());
int binCount = 0;
for (Node[] tab = table;;) {
// f 是链表头节点
// fh 是链表头结点的 hash
// i 是链表在 table 中的下标
Node f; int n, i, fh; K fk; V fv;
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(hash, key, value)))
break; // no lock when adding to empty bin
}
else if ((fh = f.hash) == MOVED)
tab = helpTransfer(tab, f);
else if (onlyIfAbsent && fh == hash && // check first node
((fk = f.key) == key || fk != null && key.equals(fk)) &&
(fv = f.val) != null)
return fv;
else {
V oldVal = null;
synchronized (f) {
if (tabAt(tab, i) == f) {
if (fh >= 0) {
binCount = 1;
for (Node 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 pred = e;
if ((e = e.next) == null) {
pred.next = new Node(hash, key, value);
break;
}
}
}
else if (f instanceof TreeBin) {
Node p;
binCount = 2;
if ((p = ((TreeBin)f).putTreeVal(hash, key,
value)) != null) {
oldVal = p.val;
if (!onlyIfAbsent)
p.val = value;
}
}
else if (f instanceof ReservationNode)
throw new IllegalStateException("Recursive update");
}
}
if (binCount != 0) {
if (binCount >= TREEIFY_THRESHOLD)
treeifyBin(tab, i);
if (oldVal != null)
return oldVal;
break;
}
}
}
addCount(1L, binCount);
return null;
}
- 调用putVal方法,除了键值对以外还有个布尔值,取值为真表示,只有第一次put才会将这个键值对放入map,后面put相同的key不做操作,这里false说明每次都会用新值覆盖掉旧值
- 如果key或者value为null,抛出空指针异常(hashmap允许空key和空value)
- 遍历table,判断是否需要初始化,如果tab为null或长度为0,调用initTable()创建(cas)
- f 即为当前 key 定位出的 Node,如果为空表示当前位置可以写入数据,利用 CAS 尝试写入,失败则自旋保证成功。
- 帮忙扩容,如果当前位置的 hashcode == MOVED == -1,则说明有线程正在进行扩容,这个时候该线程也不会闲着,而是帮忙扩容
- 进入最后一个else,此时发生了桶下标冲突,此时就要进行加锁,锁住链表头节点。遍历该 链表,如果不为空则判断传入的 key 和当前遍历的 key 是否相等,相等则覆盖旧的 value。遍历到最后时,就新建一个节点添加到链表尾部。
- 如果数量大于 TREEIFY_THRESHOLD 则要转换为红黑树。
JDK1.8版本的ConcurrentHashMap的数据结构已经接近HashMap,相对而言, ConcurrentHashMap只是增加了同步的操作来控制并发,从JDK1.7版本的 ReentrantLock+Segment+HashEntry,到JDK1.8版本中synchronized+CAS+HashEntry+红黑 树。
- 1.数据结构:取消了Segment分段锁的数据结构,取而代之的是数组+链表+红黑树的结构。
- 2.保证线程安全机制:JDK1.7采用segment的分段锁机制实现线程安全,其中segment继承自 ReentrantLock。JDK1.8采用CAS+Synchronized保证线程安全。
- 3.锁的粒度:原来是对需要进行数据操作的Segment加锁,现调整为对每个数组元素加锁 (Node)。
- 4.链表转化为红黑树:定位结点的hash算法简化会带来弊端,Hash冲突加剧,因此在链表节点数 量大于8时,会将链表转化为红黑树进行存储。
- 5.查询时间复杂度:从原来的遍历链表O(n),变成遍历红黑树O(logN)。
来自:全面深入学习java并发编程_哔哩哔哩_bilibili



