Java并发编程（五）ConcurrentHashMap
站长
· 阅读数 32
1. 结构介绍
-
ConcurrentHashMap和HashMap的存储结构是一致的。
-
ConcurrentHashMap是线程安全的。
存储结构
关于put和putIfAbsent的区别
// put和putIfAbsent都是想ConcurrentHashMap中存储值。
// 如果出现key一致的，将新数据覆盖老数据，并且返回老数据
public V put(K key, V value) {
return putVal(key, value, false);
}
// 如果出现key一致的，什么都不做，返回老数据。 最只有key不存在时，才会正常的添加数据
public V putIfAbsent(K key, V value) {
return putVal(key, value, true);
}
2. 散列算法
由于putVal方法代码较复杂，文中分析源码时会将各个部分单独分析，不涉及的部分为了方便阅读会省略，完整方法代码可在JDK8中自行查看
散列算法是为了让hashCode的高16位参与到索引位置的计算中，从而尽可能的打散数据存放到数组上。从而减少Hash冲突 ConcurrentHashMap中，还会将hash值对HASH_BITS进行&运算，让hash值一定是一个正数。
// ConcurrentHashMap存储数据的核心方法
final V putVal(K key, V value, boolean onlyIfAbsent) {
// key和value不能为null。 HashMap中是允许为null的。
if (key == null || value == null) throw new NullPointerException();
// 散列算法就是基于key进行hash运算，并且根据散列算法的结果，确定当前key-value存储到数组的哪个索引位置。
int hash = spread(key.hashCode());
// ===============省略===============
}
// 散列算法
// 散列算法是为了让hashCode的高16位参与到索引位置的计算中，从而尽可能的打散数据存放到数组上。从而减少Hash冲突
// ConcurrentHashMap中，还会将hash值对HASH_BITS进行&运算，让hash值一定是一个正数。
// 因为ConcurrentHashMap中数组上的数据的hash值，如果为负数，有特殊含义
// static final int MOVED = -1; // 代表当前位置数据在扩容，并且数据已经迁移到了新数组
// static final int TREEBIN = -2; // 代表当前索引位置下，是一个红黑树。 转红黑树，TreeBin有参构造
// static final int RESERVED = -3; // 代表当前索引位置已经被占了，但是值还没放进去呢。 compute方法
static final int spread(int h) {
return (h ^ (h >>> 16)) & HASH_BITS;;
}
00011000 00000110 00111000 00001100 h
^
00000000 00000000 00011000 00000110 h >>> 16
00011000 00000110 00111000 00001100
&
00000000 00000000 00000111 11111111 2048 - 1
ConcurrentHashMap是如何根据hash值，计算存储的位置？
(数组长度 - 1) & (h ^ (h >>> 16))
00011000 00000110 00110000 00001100 key1-hash
00011000 00000110 00111000 00001100 key2-hash
&
00000000 00000000 00000111 11111111 2048 - 1
3.初始化数组
final V putVal(K key, V value, boolean onlyIfAbsent) {
// ===============省略===============
// tab是ConcurrentHashMap的数组
for (Node<K,V>[] tab = table;;) {
// 一堆变量
Node<K,V> f; int n, i, fh;
// 代表当前数组没有初始化。
if (tab == null || (n = tab.length) == 0)
// 初始化数组 （ConcurrentHashMap在new时，不会创建数组，在使用时，才会创建）
tab = initTable();
}
// ===============省略===============
return null;
}
/*
sizeCtl是标识数组初始化和扩容的标识信息。
= -1：代表正在初始化！
< -1：代表正在扩容！
= 0：代表没有初始化！
> 0：①当前数组没有初始化，这个值，就代表初始化的长度！ ②如果已经初始化了，就代表下次扩容的阈值！
*/
private transient volatile int sizeCtl;
// 初始化数组操作
private final Node<K,V>[] initTable() {
// 声明tab：临时存数组。 sc：临时存sizeCtl
Node<K,V>[] tab; int sc;
// 判断数组还没初始化呢吧？
while ((tab = table) == null || tab.length == 0) {
// sc赋值，并判断是否小于0
if ((sc = sizeCtl) < 0)
// 线程先让出CPU的执行权。
Thread.yield();
// 如果sc大于等于0，没人在执行初始化操作。
// 以CAS的方式，将sizeCtl，改为-1，代表当前线程正在执行初始化逻辑
else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
try {
// 判断数组还没初始化呢吧？ DCL
if ((tab = table) == null || tab.length == 0) {
// 拿到数组的初始化长度
int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
// 创建数组
Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
// 依次给局部变量和成员变量赋值。
table = tab = nt;
// 计算下次扩容的阈值
sc = n - (n >>> 2);
}
} finally {
// 将扩容阈值赋值给sizeCtl
sizeCtl = sc;
}
break;
}
}
return tab;
}
4. 添加数据-数组
数据添加到数组上（没有发生hash冲突）
final V putVal(K key, V value, boolean onlyIfAbsent) {
// ===============省略===============
int binCount = 0;
for (Node<K,V>[] tab = table;;) {
// n： 数组长度。 i：索引位置。 f：i位置的数据。 fh：是f的hash值
Node<K,V> f; int n, i, fh;
// tabAt(数组，索引位置) = 拿到数组指定索引位置的数据
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
// 当前索引位置数据为null。
// 以CAS的方式，将数据放到tab的i位置上，将hash，key，value封装成了一个Node对象
if (casTabAt(tab, i, null,new Node<K,V>(hash, key, value, null)))
break;
}
// 说明当前位置数据已经被迁移到了新数组。
else if ((fh = f.hash) == MOVED)
// 帮你扩容，快点扩容完，我好把数据放到新数组~~~
tab = helpTransfer(tab, f);
// ===============省略===============
}
return null;
}
5. 添加数据-链表
final V putVal(K key, V value, boolean onlyIfAbsent) {
// ===============省略===============
// 拿到binCount
int binCount = 0;
for (Node<K,V>[] tab = table;;) {
// n： 数组长度。 i：索引位置。 f：i位置的数据。 fh：是f的hash值
Node<K,V> f; int n, i, fh;
// ===============省略===============
// 到这，说明出现了hash冲突，i位置有数据，尝试往i位置下挂数据
else {
// 声明oldVal，返回结果
V oldVal = null;
// 以桶位置数据作为锁，锁住当前桶，锁粒度更细。
synchronized (f) {
// 再判断一次，数据没有变化，正常挂链表。
if (tabAt(tab, i) == f) {
// 链表添加操作
if (fh >= 0) {
// binCount赋值1，记录链表中Node的长度
binCount = 1;
// e：暂时指向数组位置数据
for (Node<K,V> e = f;; ++binCount) {
K ek;
// 拿到当前数据的hash值，和数组位置数据的hash值比较，
if (e.hash == hash &&
// 如果相等 , 判断 == 或者 equals 返回true
((ek = e.key) == key || (ek != null && key.equals(ek)))) {
// 尝试覆盖原数据，先获取老数据
oldVal = e.val;
// 如果是put方法，进去覆盖值
// 如果是putIfAbsent，进去不if逻辑
if (!onlyIfAbsent)
// 覆盖值
e.val = value;
break;
}
// pred暂存e
Node<K,V> pred = e;
// e指向下一个节点，并且如果e == null，说明下面没节点了
if ((e = e.next) == null) {
// 将当前的值封装为Node对象，并挂在最后一个节点的后面
pred.next = new Node<K,V>(hash, key, value, null);
break;
}
}
}
// 红黑树添加操作
else if (f instanceof TreeBin) {
// ===============省略===============
}
}
}
// 如果binCount != 0
if (binCount != 0) {
// 如果binCount >= 8
if (binCount >= TREEIFY_THRESHOLD)
// 判断是扩容还是转红黑树
treeifyBin(tab, i);
// 判断是否需要返回
if (oldVal != null)
return oldVal;
break;
}
}
}
// ===============省略===============
return null;
}
6. 添加数据-红黑树
- 红黑树添加与链表添加基本相同，仅仅是在判断当前桶节点类型为TreeBin时调用TreeBin的putTreeVal
// ===============省略===============
// 红黑树添加操作
else if (f instanceof TreeBin) {
// 判断当前桶节点类型为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;
}
}
// ===============省略===============
- 由于红黑树操作较复杂，这里不做详细描述，有兴趣的小伙伴可以查看ConcurrentHashMap.TreeBin以及ConcurrentHashMap.TreeNode相关源码
判断是否需要转红黑树或者是扩容
在添加节点时，会判断是否需要转红黑树或者是扩容，当bincount(链表长度) > TREEIFY_THRESHOLD(8)时
- 数组tab长度 < 64时，会触发扩容
- 数组tab长度 >= 64时，会将当前位置的链表转为红黑树
// tab：数组！ index：索引位置！
private final void treeifyBin(Node<K,V>[] tab, int index) {
// n：数组长度， sc：sizeCtl
Node<K,V> b; int n, sc;
// 判断tab不为null
if (tab != null) {
// 如果数组长度 小于 64，不转红黑树，先扩容（更希望数据存放在数组上，O1）
// 只有数组长度大于等于64并且链表长度达到8，才转为红黑树
if ((n = tab.length) < MIN_TREEIFY_CAPACITY)
// 扩容前的一些准备和业务判断
tryPresize(n << 1);
// 转红黑树操作
else if ((b = tabAt(tab, index)) != null && b.hash >= 0) {
synchronized (b) {
if (tabAt(tab, index) == b) {
TreeNode<K,V> hd = null, tl = null;
// 将单向链表转换为TreeNode对象（双向链表），
for (Node<K,V> e = b; e != null; e = e.next) {
TreeNode<K,V> p =
new TreeNode<K,V>(e.hash, e.key, e.val,
null, null);
// 设置双向链表的上下节点关系，若上一个节点为空，当前节点设置为链表初始节点
if ((p.prev = tl) == null)
hd = p;
else
tl.next = p;
// 存储TreeNode引用
tl = p;
}
// 通过TreeBin将TreeNode链表转为红黑树，放入tab中。
// TreeBin中保留着双向链表以及红黑树
setTabAt(tab, index, new TreeBin<K,V>(hd));
}
}
}
}
}
7. 扩容
转载自:https://juejin.cn/post/7232224552218984485