探究并发包中ConcurrentHashMap中的put方法底层实现原理

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