探究并发包中ConcurrentHashMap中的put方法底层实现原理
程序员文章站
2022-05-13 09:33:51
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(); int hash = spread(key.hashCode()...
put方法
public V put(K key, V value) {
//返回putVal
return putVal(key, value, false);
}
//进入putVal
final V putVal(K key, V value, boolean onlyIfAbsent) {
//如果key或者value 为空,抛出空指针异常
if (key == null || value == null) throw new NullPointerException();
//通过spread计算key的hash,重新计算hash值 计算过程 高位不变 低位异或 符号位改为0
//spread跟HashMap的hash算法类似,只是把位数控制在int最大整数之内
int hash = spread(key.hashCode());
//用于统计节点个数
int binCount = 0;
//开始死循环 定义一个节点数组tab
for (Node<K,V>[] tab = table;;) {
//定义头节点f的 容器长度n 碰撞位置i 头节点的hash值fh
Node<K,V> f; int n, i, fh;
//在tab为空 或 长度为空时进入initTable()
if (tab == null || (n = tab.length) == 0)
//用于初始化节点数组
tab = initTable();
//初始化结束 进入下次循环
//这个过程确定了头节点的散列hash值位置
//tabAt的作用是寻找tab在内存中i位置的数据
//i = (n - 1) & hash的意思是对hash % n ,采用二进制位操作相对于%能够提高运算效率
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
//如果此时头节点为null
//casTabAt 基于CAS尝试更新 tab 中下标为 i 的结点的值为 v
if (casTabAt(tab, i, null,
new Node<K,V>(hash, key, value, null)))//此时添值没加锁
//如果失败则说明期间有两个以上的线程同时操作,需要进入一轮新的循环
//如果成功则本次 put 操作完成 跳出循环
break;
}
//如果 Map 正在执行扩容操作(MOVED 哈希值表示正在扩容)
else if ((fh = f.hash) == MOVED)
//helpTransfer用于帮助扩容
tab = helpTransfer(tab, f);
//获取到 hash 值对应下标的头结点,且结点不为 null
else {
//声明一个临时变量
V oldVal = null;
//头节点加锁
synchronized (f) {
//再次判断头节点是否为f
if (tabAt(tab, i) == f) {
//头结点f的哈希值fh大于等于0,说明是链表,如果是树的话应该是 -2
if (fh >= 0) {
//必然最少一个值,因为f是一个值
binCount = 1;
//开始循环 创建节点e 每次binCount+1 ek为e的Key
for (Node<K,V> e = f;; ++binCount) {
K ek;
//判断e的hash值是否等于之前的hash值
if (e.hash == hash &&
//判断ek是否为空,是否重复
((ek = e.key) == key ||
(ek != null && key.equals(ek)))) {
//如果是已经存在的 key,则就把已有的值替换为新的值
oldVal = e.val;
//如果不重复则不进入这个if
if (!onlyIfAbsent)
e.val = value;
break;
}
//如果是不存在的 key,则直接在链表尾部插入一个新的结点
Node<K,V> pred = e;
//e向后移动 并判断e的next是不是为空
if ((e = e.next) == null) {
//如果是空则创建新节点并放在pred的next
pred.next = new Node<K,V>(hash, key,
value, null);
//进入下一轮for循环
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) {
//如果binCount大于等于8
if (binCount >= TREEIFY_THRESHOLD)
//对链表执行转换操作
//如果 table 长度小于 64,则执行扩容
//如果 table 长度大于等于 64,则转换成红黑树
treeifyBin(tab, i);
if (oldVal != null)
return oldVal;
break;
}
}
}
//size+1
addCount(1L, binCount);
return null;
}
initTable方法
初始化 table 的过程
private final Node<K,V>[] initTable() {
//声明节点数组 tab 临时变量sc
Node<K,V>[] tab; int sc;
//如果此时tab为空 或 数组长度为0 进入while循环
while ((tab = table) == null || tab.length == 0) {
//sizeCtl默认为0,用来控制table的初始化和扩容操作
if ((sc = sizeCtl) < 0)
//抢占线程失败 yiede()让出当前线程的执行权
Thread.yield();
//如果sc大于等于0 (U是一个非线程安全的工具类)
//执行 CAS 操作,期望将sizeCtl替换为-1,sizeCtl为-1表示正在初始化
else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
try {
//对 table 进行初始化,再次判断此时tab为空 或 数组长度为0
//因为无法保证在上面的时间中有其他线程往table里放值
if ((tab = table) == null || tab.length == 0) {
//sc大于0则 把sc给n 否则初始化长度为默认容量大小16
int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
@SuppressWarnings("unchecked")
//创建节点数组nt
Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
table = tab = nt;
//指定下次扩容的长度,相当于 0.75 × n
sc = n - (n >>> 2);
}
} finally {
//最终执行sc的值给sizeCtl
sizeCtl = sc;
}
break;
}
}
//返回tab 此时tab容量为16
return tab;
}
参考资料:
http://www.zhenchao.org/2019/01/31/java/cas-based-concurrent-hashmap/
本文地址:https://blog.csdn.net/qq_44457886/article/details/110492146