【JUC源码】并发容器：ConcurrentHashMap（二）添加元素及树化源码分析

不念不忘少年蓝@ 2022-10-31 12:19 179阅读 0赞

> ConcurrentHashMap 系列：
> 
>  *  [【JUC源码】并发容器：ConcurrentHashMap（一）底层结构分析][JUC_ConcurrentHashMap]
>  *  [【JUC源码】并发容器：ConcurrentHashMap（二）添加元素及树化源码分析][JUC_ConcurrentHashMap 1]
>  *  [【JUC源码】并发容器：ConcurrentHashMap（三）扩容源码分析][JUC_ConcurrentHashMap 2]
>  *  [【JUC源码】并发容器：ConcurrentHashMap（四）获取 value 源码分析][JUC_ConcurrentHashMap_ value]
>  *  [【JUC源码】并发容器：关于 ConcurrentHashMap 的几个问题][JUC_ ConcurrentHashMap]

由于 concurrentHashMap 主要用于并发情况，为了线程安全要避免直接对数组读写。ConcurrentHashMap 定义了三个原子操作，用于对指定位置的节点进行操作。正是这些原子操作保证了 ConcurrentHashMap 的线程安全。

@SuppressWarnings("unchecked")
        // 获得在i位置上的Node节点
        static final <K,V> Node<K,V> tabAt(Node<K,V>[] tab, int i) {
        
            return (Node<K,V>)U.getObjectVolatile(tab, ((long)i << ASHIFT) + ABASE);
        }
    	// 利用CAS算法设置i位置上的Node节点。之所以能实现并发是因为他指定了原来这个节点的值是多少
    	// 在CAS算法中，会比较内存中的值与你指定的这个值是否相等，如果相等才接受你的修改，否则拒绝你的修改
    	// 因此当前线程中的值并不是最新的值，这种修改可能会覆盖掉其他线程的修改结果  有点类似于SVN
        static final <K,V> boolean casTabAt(Node<K,V>[] tab, int i,
                                            Node<K,V> c, Node<K,V> v) {
        
            return U.compareAndSwapObject(tab, ((long)i << ASHIFT) + ABASE, c, v);
        }
    
    	// 利用volatile方法设置节点位置的值
        static final <K,V> void setTabAt(Node<K,V>[] tab, int , Node<K,V> v) {
        
            U.putObjectVolatile(tab, ((long)i << ASHIFT) + ABASE, v);
        }

## 1.添加元素 ##

### **put()** ###

与Hashmap的区别在于无evict参数了，hashmap的evict是为Hashset服务

public V put(K key, V value) {
        
            return putVal(key, value, false);
    }

### **putVal()** ###

新增值操作是在自旋中进行的，目的是保证新增操作一定能成功。后面主要分为四种情况

*  情况一：table 是空的，调用 initTable() 初始化
 *  情况二：当前槽点 null，直接新增，并判断是否扩容（addCount方法在最后）
 *  情况三：当前槽点正在扩容，调用 helptransfer 去辅助扩容
 *  情况四：正常哈希碰撞，锁住当前槽点后，分成链表和红黑树两种情况进行处理，其中链表再新增完后还要判断是否需要转换为红黑树

final V putVal(K key, V value, boolean onlyIfAbsent) {
        
        if (key == null || value == null) throw new NullPointerException();
        // 计算hash值：(h ^ (h >>> 16)) & HASH_BITS
        int hash = spread(key.hashCode());
        int binCount = 0; // binCount主要作用是记录链表节点数量
        // 自旋
        for (Node<K,V>[] tab = table;;) {
        
            Node<K,V> f; int n, i, fh;
            
            // 情况一：table是空的，进行初始化
            // 初始化完后，再走下一轮循环，继续判断
            if (tab == null || (n = tab.length) == 0)
                tab = initTable();
            // 情况二：如果当前索引位置没有值，直接创建
            else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
        
                // cas 在 i 位置创建新的元素，当 i 位置是空时，即能创建成功，结束for自旋，否则继续自旋
                if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value, null)))
                    break;                   // no lock when adding to empty bin
            }
            
            // 情况三：如果当前槽点是转移节点，表示该槽点正在扩容，就会一直等待扩容完成，之后再for进行新增
            // 转移节点的 hash 值是固定的，都是 MOVED
            else if ((fh = f.hash) == MOVED)
                tab = helpTransfer(tab, f);
            
            // 情况四：槽点上有值的，即出现Hash碰撞。下面要分成链表和红黑树两种情况
            else {
        
                V oldVal = null;
                // 锁定当前槽点，其余线程不能操作，保证了安全
                synchronized (f) {
        
                    // 这里再次判断 i 索引位置的数据没有被修改
                    if (tabAt(tab, i) == f) {
        
                        // 当前槽点上是链表
                        if (fh >= 0) {
        
                            binCount = 1; // binCount 被赋值的话，说明走到了修改表的过程里面
                            // 遍历链表
                            for (Node<K,V> e = f;; ++binCount) {
        
                                K ek;
                                // 判断链表中是否已经有要新增的key
                                if (e.hash == hash &&
                                    ((ek = e.key) == key || (ek != null && key.equals(ek)))) {
        
                                    // 获取oldValue
                                    oldVal = e.val;
                                    // 根据参数onlyIfAbsent判断是否覆盖
                                    if (!onlyIfAbsent)
                                        e.val = value;
                                    break; // 退出链表遍历
                                }
                                // 链表中不存在要新增key，则将该node插入到链表最后
                                Node<K,V> pred = e;
                                if ((e = e.next) == null) {
        
                                    pred.next = new Node<K,V>(hash, key, value, null);
                                    break; // 退出链表遍历
                                }
                            }
                        }
                        // 红黑树，这里没有使用 TreeNode,使用的是 TreeBin，TreeNode 只是红黑树的一个节点
                        // TreeBin 持有红黑树的引用，并且会对其加锁，保证其操作的线程安全
                        else if (f instanceof TreeBin) {
        
                            Node<K,V> p;
                            binCount = 2;
                            // 满足if的话，把老的值给oldVal
                            // 在putTreeVal方法里面，在给红黑树重新着色旋转的时候会锁住红黑树的根节点
                            if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key, value)) != null) {
        
                                oldVal = p.val;
                                if (!onlyIfAbsent)
                                    p.val = value;
                            }
                        }
                    }
                }
                
                // binCount不为0说明已经新增成功了
                if (binCount != 0) {
        
                    // 判断链表是否需要转化成红黑树，链表节点数已经大于8
                    if (binCount >= TREEIFY_THRESHOLD)
                        treeifyBin(tab, i);
                    if (oldVal != null)
                        return oldVal;
                    // 这一步几乎走不到
                    // 槽点已经上锁，只有在红黑树或者链表新增失败的时候才会走到这里，这两者新增都是自旋的，几乎不会失败
                    break;
                }
            }
        }
        
        // check 容器是否需要扩容，如果需要去扩容，调用 transfer 方法去扩容
        // 如果已经在扩容中了，check有无完成
        // 注：情况四（在链表或者红黑树中添加元素）不会走到这里
        addCount(1L, binCount);
        return null;
    }

putVal() 保证线程安全的手段：**自旋 + CAS + 锁**

*  通过自旋死循环保证一定可以新增成功
    
    在新增之前，通过 `for (Node<K,V>[] tab = table;;)` 这样的死循环来保证新增一定可以成功，一旦新增成功，就可以退出当前死循环，新增失败的话，会重复新增的步骤，直到新增成功为止。
 *  若当前槽点为空通过CAS新增
    
    Java 这里的写法非常严谨，没有在判断槽点为空的情况下直接赋值，因为在判断槽点为空和赋值的瞬间，很有可能槽点已经被其他线程赋值了，所以我们采用 CAS 算法，能够保证槽点为空的情况下赋值成功。
    
    如果恰好槽点已经被其他线程赋值，当前 CAS 操作失败，会再次执行 for 自旋，再走槽点有值的 put 流程，这里就是自旋 + CAS 的结合。
 *  哈希碰撞时，锁住当前槽点后再进行操作
    
    put 时，如果当前槽点有值，就是 key 的 hash 冲突的情况，此时槽点上可能是链表或红黑树，我们通过锁住槽点，来保证同一时刻只会有一个线程能对槽点进行修改，截图如下：  
    ![图片描述][2020092616032967.png_pic_center]

## 2.数组初始化 ##

### initTable() ###

进行数组的初始化，通过**自旋+CAS+双重检查**保证了线程安全

*  自旋：保证一定可以初始化成功
 *  CAS：保证只有一个线程进行初始化
 *  双重check：保证数组只初始化一次，避免刚好一个线程初始化完的情况

// 初始化 table，通过对 sizeCtl 的变量赋值来保证数组只能被初始化一次
    private final Node<K,V>[] initTable() {
        
        Node<K,V>[] tab; int sc;
        // 通过自旋保证一定能初始化成功
        while ((tab = table) == null || tab.length == 0) {
        
            // sizeCtl 小于 0 代表有线程正在初始化，释放当前 CPU 的调度权，重新发起锁的竞争
            if ((sc = sizeCtl) < 0) 
                Thread.yield(); 
            // 运行到这一行表示没有现成正在初始化或者扩容，所以当前线程CAS修改 sizeCtl 为 -1
            // 保证了数组的初始化的安全性
            else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
        
                try {
        
                    // 这里是第二次 check，很有可能执行到这里的时候，table 已经不为空了
                    if ((tab = table) == null || tab.length == 0) {
        
                        // 进行初始化,若sizeCtl=0则用16进行初始化
                        int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
                        @SuppressWarnings("unchecked")
                        // 创建大小为n的数组
                        Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
                        table = tab = nt;
                        // 将 sizeCtl 设置为 n*0.75，表示扩容阈值
                        // 注：这里的逻辑是 1 - 1/2/2 = 1 - 0.25 = 0.75
                        sc = n - (n >>> 2);
                    }
                } finally {
        
                    // 若初始化数组失败，则将sizeCtl重置
                    sizeCtl = sc;
                }
                break;
            }
        }
        return tab;
    }

## 3.链表转红黑树 ##

### treeifyBin() ###

这个方法用于将过长的链表转换为 TreeBin 对象。但是他并不是直接转换，而是进行一次容量判断

*  如果容量没有达到转换的要求，直接进行扩容操作并返回
 *  如果满足条件才链表的结构转换为 TreeBin ，这与 HashMap 不同的是，它并没有把 TreeNode 直接放入红黑树，而是利用了TreeBin 这个小容器来封装所有的 TreeNode

private final void treeifyBin(Node<K,V>[] tab, int index) {
        
            Node<K,V> b; int n, sc;
            if (tab != null) {
        
                // 数组长度小于 64，先尝试扩容解决
                if ((n = tab.length) < MIN_TREEIFY_CAPACITY)
                    // tryPresize中调用了transfer
                    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;
                            // 根据 Node 的 key，value 构造 TreeNode
                            for (Node<K,V> e = b; e != null; e = e.next) {
        
                            	// 构造 TreeNode
                                // 注：这里只是利用了TreeNode封装 而没有利用TreeNode的next域和parent域
                                TreeNode<K,V> p =
                                    new TreeNode<K,V>(e.hash, e.key, e.val, null, null);
                                // 通过 prev 以链表的形式组织所有 TreeNode
                                // 如果是第一个节点，则它就是 head
                                if ((p.prev = tl) == null)
                                    hd = p;
                                else
                                    tl.next = p;
                                // 更新 tl 为 p
                                tl = p;
                            }
                            // 通过 head 构造 TreeBin 对象，并替换原来的 node
                            // 注：TreeBin 在构造时会按红黑树构造组装这些 TreeNode
                            setTabAt(tab, index, new TreeBin<K,V>(hd));
                        }
                    }
                }
            }
        }

[JUC_ConcurrentHashMap]: https://blog.csdn.net/weixin_43935927/article/details/108810815
[JUC_ConcurrentHashMap 1]: https://blog.csdn.net/weixin_43935927/article/details/113943932
[JUC_ConcurrentHashMap 2]: https://blog.csdn.net/weixin_43935927/article/details/113945436
[JUC_ConcurrentHashMap_ value]: https://blog.csdn.net/weixin_43935927/article/details/113950339
[JUC_ ConcurrentHashMap]: https://blog.csdn.net/weixin_43935927/article/details/108819013
[2020092616032967.png_pic_center]: /images/20221024/9978baeac93f478283e6a637bb903c5c.png