并发编程源码解析（五）ConcurrentHashMap源码解析之二读与写源码分析

黄小墨(￣∇￣)

于 2023-11-24 23:50:17 发布

阅读量611

点赞数 13

分类专栏：并发编程源码解析文章标签： java 开发语言

本文链接：https://blog.csdn.net/qq_33781946/article/details/134607838

版权

并发编程源码解析专栏收录该内容

11 篇文章

订阅专栏

一、前瞻

并发编程源码解析（四）ConcurrentHashMap源码解析之一基础概念介绍以及散列算法讲解-CSDN博客

二、ConcurrentHashMap 的读与写源码解析

2.1 写

ConcurrentHashMap 的写方法主要有两个：put 和 putIfAbsent 他们共同调用的方法都是putVal；所以我们这边主要讲解写的流程；因为源码的长度过长我会先贴出源码进行一个大致的讲解，详细的部分可以再接下来的小点中仔细说明。

final V putVal(K key, V value, boolean onlyIfAbsent) {
        // 注意！HashMap 允许 Key 为空； 但是 ConcurrentHashMap 不允许
        if (key == null || value == null) throw new NullPointerException();
        // 计算Hash值，具体流程见上篇
        int hash = spread(key.hashCode());
        int binCount = 0;
        //其实就是拿到值之后死循环了
        for (Node<K,V>[] tab = table;;) {
            Node<K,V> f; int n, i, fh;
            //初始化
            if (tab == null || (n = tab.length) == 0)
                tab = initTable();
            //插入数组
            else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
                if (casTabAt(tab, i, null,
                        new Node<K,V>(hash, key, value, null)))
                    break;                   // no lock when adding to empty bin
            }
            //帮助迁移
            else if ((fh = f.hash) == MOVED)
                tab = helpTransfer(tab, f);
            //添加数据的流程
            else {
                V oldVal = null;
                //锁住对应的Node对象
                synchronized (f) {
                    //check 这个期间数据是否发生改变
                    if (tabAt(tab, i) == f) {
                        //链表 在这里进行添加
                        if (fh >= 0) {
                            binCount = 1;
                            for (Node<K,V> e = f;; ++binCount) {
                                K ek;
                                if (e.hash == hash &&
                                        ((ek = e.key) == key ||
                                                (ek != null && key.equals(ek)))) {
                                    oldVal = e.val;
                                    if (!onlyIfAbsent)
                                        e.val = value;
                                    break;
                                }
                                Node<K,V> pred = e;
                                if ((e = e.next) == null) {
                                    pred.next = new Node<K,V>(hash, key,
                                            value, null);
                                    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;
                            }
                        }
                    }
                }
                //如果大于8转红黑树
                if (binCount != 0) {
                    if (binCount >= TREEIFY_THRESHOLD)
                        treeifyBin(tab, i);
                    if (oldVal != null)
                        return oldVal;
                    break;
                }
            }
        }
        addCount(1L, binCount);
        return null;
    }

2.1.1 数组的数组的初始化

ConcurrentHashMap 采用的是来加载的方式，所以实在put过程中加载的详见如下：

在此之前说明sizeCtl的值

-1 正常初始化

< -1 是正在扩容

0 没有初始化

>0 数组扩容阈值/ 没有初始化是代表初始化长度

     //初始化
     if (tab == null || (n = tab.length) == 0)
          tab = initTable();

     private final Node<K,V>[] initTable() {
        Node<K,V>[] tab; int sc;
        // 再一次检查数组是否为0 或者 空
        while ((tab = table) == null || tab.length == 0) {
            // sizeCtl 小于 1 说明数据已经在迁移了；让出线程
            if ((sc = sizeCtl) < 0)
                Thread.yield(); // lost initialization race; just spin
            // 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;
                        @SuppressWarnings("unchecked")
                        //创建数组
                        Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
                        table = tab = nt;
                        //扩展系数是0.75 所以是 n - n >>> 2; 如 16 右移2位是 4。
                        sc = n - (n >>> 2);
                    }
                } finally {
                    // sc 未初始化之前储存的是初始值，未初始化储存的是拓展系数
                    sizeCtl = sc;
                }
                break;
            }
        }
        return tab;
    }

2.1.2 添加数据的流程

2.1.2.1 添加数据到数组

数组是用CAS方式写入的。

        //插入数组，当发现当前数据的数组计算出来的位置为null
        else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
            //就是用CAS的方式直接写入
            if (casTabAt(tab, i, null,
                new Node<K,V>(hash, key, value, null)))
                    break;                   
            }

2.1.2.2 添加数据到链表

    //check 这个期间数据是否发生改变
    if (tabAt(tab, i) == f) {
    //链表 在这里进行添加； fh的值详情请参照上一篇node hash值小于1的情况
    if (fh >= 0) {
        //记录链表的长度
        binCount = 1;
        //++链表
        for (Node<K,V> e = f;; ++binCount) {
            K ek;
            //如果Hash值相同则覆盖
            if (e.hash == hash &&
              ((ek = e.key) == key ||
               (ek != null && key.equals(ek)))) {
                // 返回OldVal
                oldVal = e.val;
                if (!onlyIfAbsent)
                    //put 和 putIfAbsent 的差别
                    e.val = value;
                    break;
                 }
                // 不同的话就不断地向下迭代，直到找到或者插入队尾
                Node<K,V> pred = e;
                if ((e = e.next) == null) {
                    pred.next = new Node<K,V>(hash, key, value, null);
                    break;
                }
            }
    }

2.1.3.3 添加数据进入红黑树

红黑树的逻辑没有特别复杂，转换的逻辑涉及到红黑树的；可以看看相关文章这里就不细讲了。

    //红黑树的添加
    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;
            }
    }

2.1.3 帮助迁移

当 Hash 值被赋值为 MOVED，意味着数组正在发生迁移，所以让当前线程帮助迁移；具体逻辑之后 ConcurrentHashMap 的扩容流程会详细讲解。

    //帮助迁移
   else if ((fh = f.hash) == MOVED)
        tab = helpTransfer(tab, f);

2.1.4 转红黑树

当链表大于的8的时候会转成红黑树，使用的就是链表那块的binCount参数；转红黑树的逻辑不详细介绍了。但是有三个点可以了解一下：

1、转成红黑树之后会保留原先的双向链表

2、红黑树到减到6才会退化到双向链表；目的是为了防止一直频繁转换。

3、这里可能会发生扩容，详情请见扩容篇。

    //如果大于8转红黑树
    if (binCount != 0) {
       if (binCount >= TREEIFY_THRESHOLD)
           //转成红黑树，这里可能会发生扩容
          treeifyBin(tab, i);
       if (oldVal != null)
           return oldVal;
           break;
    }

2.2 读

get 方法的全流程介绍，读的过程全程都不会阻塞哦~

     public V get(Object key) {
        Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
        // 计算Hash值
        int h = spread(key.hashCode());
        // 判断数组长度
        if ((tab = table) != null && (n = tab.length) > 0 &&
                (e = tabAt(tab, (n - 1) & h)) != null) {
            // 如果hash相等
            if ((eh = e.hash) == h) {
                // 如果key值相等，则返回结果
                if ((ek = e.key) == key || (ek != null && key.equals(ek)))
                    return e.val;
            }
            // 如果eh值小于0 说明hash已经迁移或者是红黑树； 具体的是看各个实现类的find代码
            // 如果是已经被迁移走的会去新的数组当中获取参数
            else if (eh < 0)
                return (p = e.find(h, key)) != null ? p.val : null;
            // 去链表中查找
            while ((e = e.next) != null) {
                if (e.hash == h &&
                        ((ek = e.key) == key || (ek != null && key.equals(ek))))
                    return e.val;
            }
        }
        return null;
    }