欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

探究并发包中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

相关标签: java