jdk源码解析三之ConcurrentHashMap

た入场券 2023-02-20 12:07 7阅读 0赞

### 文章目录 ###

*   *  ConcurrentHashMap
     *   *  put
         *  初始化
         *  扩容
         *  get
         *  addCount
         *  replace\#remove
         *  总结:
         *   *  什么时候扩容?
             *  JDK1.8放弃分段锁
             *  jdk1.8的map实现
             *  为什么不用ReentrantLock而用synchronized ?
             *  多个线程又是如何同步处理的呢？

## ConcurrentHashMap ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L051YW5fRmVuZw_size_16_color_FFFFFF_t_70]

//使用了unSafe方法，通过直接操作内存的方式来保证并发处理的安全性，使用的是硬件的安全机制。
        /*
         * 用来返回节点数组的指定位置的节点的原子操作
         */
        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原子操作，在指定位置设定值
         */
        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);
        }
        /*
         * 原子操作，在指定位置设定值
         */
        static final <K,V> void setTabAt(Node<K,V>[] tab, int i, Node<K,V> v) {
        
            U.putObjectVolatile(tab, ((long)i << ASHIFT) + ABASE, v);
        }

### put ###

public V put(K key, V value) {
        
    
            /*
             * onlyIfAbsent
             *  false:这个value一定会设置
             *  true:只有当这个key的value为空的时候才会设置
             */
            return putVal(key, value, false);
        }
    
        final V putVal(K key, V value, boolean onlyIfAbsent) {
        
            //不允许key/value为null,否则及时失败
            if (key == null || value == null) throw new NullPointerException();
            //获取key的hashCode
            int hash = spread(key.hashCode());
            //用来计算在这个节点总共有多少个元素，用来控制扩容或者转移为树
            int binCount = 0;
            for (Node<K,V>[] tab = table;;) {
        
                Node<K,V> f; int n, i, fh;
                //初始化tab
                if (tab == null || (n = tab.length) == 0)
                    tab = initTable();
                else if (
                    //通过哈希计算出一个表中的位置因为n是数组的长度，所以(n-1)&hash肯定不会出现数组越界
                        (f = tabAt(tab, i = (n - 1) & hash)) == null) {
        
                    //如果这个位置没有元素的话，则通过cas的方式尝试添加，注意这个时候是没有加锁的
                    if (casTabAt(tab, i, null,
                                 new Node<K,V>(hash, key, value, null)))
                        break;                   // no lock when adding to empty bin
                }
                /*
                 * 如果检测到某个节点的hash值是MOVED，则表示正在进行数组扩张的数据复制阶段，
                 * 则当前线程也会参与去复制，通过允许多线程复制的功能，一次来减少数组的复制所带来的性能损失
                 */
                else if ((fh = f.hash) == MOVED)
                    tab = helpTransfer(tab, f);
                else {
        
                    V oldVal = null;
                    synchronized (f) {
        
                        //再次取出要存储的位置的元素，跟前面取出来的比较
                        if (tabAt(tab, i) == f) {
        
                            //取出来的元素的hash值大于0，当转换为树之后，hash值为-2
                            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;
                                }
                            }
                        }
                    }
                    if (binCount != 0) {
        
                        //链表节点其中个数达到8,则扩张数组或转成树
                        if (binCount >= TREEIFY_THRESHOLD)
                            treeifyBin(tab, i);
                        if (oldVal != null)
                            return oldVal;
                        break;
                    }
                }
            }
            //计数
            addCount(1L, binCount);
            return null;
        }

### 初始化 ###

private final Node<K,V>[] initTable() {
        
            Node<K,V>[] tab; int sc;
            while ((tab = table) == null || tab.length == 0) {
        
                //sizeCtl初始值为0，当小于0的时候表示在别的线程在初始化表或扩展表
                //则暂停当前正在执行的线程对象，并执行其他线程。
                if ((sc = sizeCtl) < 0)
                    Thread.yield(); // lost initialization race; just spin
                else if (
                      /*
                       SIZECTL:当前内存偏移量,
                        sc:期望值
                        -1:表示要替换的值
                    */
                        U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
        
                    try {
        
                        if ((tab = table) == null || tab.length == 0) {
        
                            //指定了大小的时候就创建指定大小的Node数组，否则创建指定大小(16)的Node数组
                            int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
                            @SuppressWarnings("unchecked")
                            Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
                            table = tab = nt;
                            sc = n - (n >>> 2);
                        }
                    } finally {
        
                        //初始化后，sizeCtl长度为数组长度的3/4
                        sizeCtl = sc;
                    }
                    break;
                }
            }
            return tab;
        }

### 扩容 ###

/**
         * Replaces all linked nodes in bin at given index unless table is
         * too small, in which case resizes instead.
         * 数组长度<64,则扩容一倍
         * 否则转成树
         */
        private final void treeifyBin(Node<K,V>[] tab, int index) {
        
            Node<K,V> b; int n, sc;
            if (tab != null) {
        
                if ((n = tab.length) < MIN_TREEIFY_CAPACITY)
                    //扩容
                    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;
                            for (Node<K,V> e = b; e != null; e = e.next) {
        
                                TreeNode<K,V> p =
                                    new TreeNode<K,V>(e.hash, e.key, e.val,
                                                      null, null);
                                //把Node组成的链表，转化为TreeNode的链表，头结点依然放在相同的位置
                                if ((p.prev = tl) == null)
                                    hd = p;
                                else
                                    tl.next = p;
                                tl = p;
                            }
                            //把TreeNode的链表放入容器TreeBin中,内部将单节点树转换成红黑树
                            setTabAt(tab, index, new TreeBin<K,V>(hd));
                        }
                    }
                }
            }
        }
    
     private final void tryPresize(int size) {
        
            //扩容大小>=最大的一半,直接设置成最大容量
            int c = (size >= (MAXIMUM_CAPACITY >>> 1)) ? MAXIMUM_CAPACITY :
                    //返回大于输入参数且最近的2的整数次幂的数
                tableSizeFor(size + (size >>> 1) + 1);
            int sc;
            while ((sc = sizeCtl) >= 0) {
        
                Node<K,V>[] tab = table; int n;
                //如果数组还没有初始化
                //putAll的时候,会执行这儿
                if (tab == null || (n = tab.length) == 0) {
        
                    n = (sc > c) ? sc : c;
                    //SIZECTL设置-1，表示正在初始化
                    if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
        
                        try {
        
                            //双重检查
                            if (table == tab) {
        
                                @SuppressWarnings("unchecked")
                                Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
                                table = nt;
                                //sc=3/4*n
                                sc = n - (n >>> 2);
                            }
                        } finally {
        
                            sizeCtl = sc;
                        }
                    }
                }
                //扩容后的大小<=sizeCtl或者当前数组长度>容量上限,则退出
                else if (c <= sc || n >= MAXIMUM_CAPACITY)
                    break;
                else if (tab == table) {
        
                    int rs = resizeStamp(n);
                    //表示正在扩容
                    if (sc < 0) {
        
                        Node<K,V>[] nt;
                        if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
                            sc == rs + MAX_RESIZERS || (nt = nextTable) == null ||
                            transferIndex <= 0)
                            break;
                        //transfer线程数+1,当前线程将加入对transfer的处理
                        //transfer的时候,sc表示在transfer工作的线程数
                        if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1))
                            transfer(tab, nt);
                    }
                    //没有在初始化或扩容,则开始扩容
                    else if (U.compareAndSwapInt(this, SIZECTL, sc,
                                                 (rs << RESIZE_STAMP_SHIFT) + 2))
                        transfer(tab, null);
                }
            }
        }
    
    
        private static final int tableSizeFor(int c) {
        
    
            /*
            　　让cap-1再赋值给n的目的是另找到的目标值大于或等于原值。例如二进制1000，十进制数值为8。
            如果不对它减1而直接操作，将得到答案10000，即16。显然不是结果。
            减1后二进制为111，再进行操作则会得到原来的数值1000，即8。
             */
            int n = c - 1;
            n |= n >>> 1;
            n |= n >>> 2;
            n |= n >>> 4;
            n |= n >>> 8;
            n |= n >>> 16;
            return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
        }
    
     private final void transfer(Node<K,V>[] tab, Node<K,V>[] nextTab) {
        
            int n = tab.length, stride;
            //MIN_TRANSFER_STRIDE=16.控制线程数
            //每个CPU最少处理16个长度的数组元素,可以看出核数越高步长越小,也就是说，如果一个数组的长度只有16，那只有一个线程会对其进行扩容的复制移动操作
            if ((stride = (NCPU > 1) ? (n >>> 3) / NCPU : n) < MIN_TRANSFER_STRIDE)
                stride = MIN_TRANSFER_STRIDE; // subdivide range
            //只有第一个线程进此方法的时候,才会初始化数组.
            if (nextTab == null) {
                    // initiating
                try {
        
                    @SuppressWarnings("unchecked")
                            //扩容一倍数组容量
                    Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n << 1];
                    nextTab = nt;
                } catch (Throwable ex) {
              // try to cope with OOME
                    sizeCtl = Integer.MAX_VALUE;
                    return;
                }
                //这里标记数组初始化完成,
                nextTable = nextTab;
                transferIndex = n;
            }
            int nextn = nextTab.length;
            /*
             * 创建一个fwd节点，这个是用来控制并发的，当一个节点为空或已经被转移之后，就设置为fwd节点
             * 这是一个空的标志节点
             */
            ForwardingNode<K,V> fwd = new ForwardingNode<K,V>(nextTab);
            //是否继续向前查找的标志位
            boolean advance = true;
            //在完成之前重新在扫描一遍数组，看看有没完成的没
            boolean finishing = false; // to ensure sweep before committing nextTab
            for (int i = 0, bound = 0;;) {
        
                Node<K,V> f; int fh;
                while (advance) {
        
                    int nextIndex, nextBound;
                    //i每次自减,小于范围  或者 当前线程执行完成  则标记不需要再向前查找
                    if (--i >= bound || finishing)
                        advance = false;
                    //说明每个桶位置都有线程进行处理,则跳出循环
                    else if ((nextIndex = transferIndex) <= 0) {
        
                        i = -1;
                        advance = false;
                    }
                    //每次修改transferIndex=transferIndex-stride,每个线程处理stride步长的桶
                    else if (U.compareAndSwapInt
                             (this, TRANSFERINDEX, nextIndex,
                              nextBound = (nextIndex > stride ?
                                           nextIndex - stride : 0))) {
        
                        //假设当前数组长度为32,stride=16
                        //则nextIndex=32
                        //transferIndex=nextBound= nextIndex - stride=16
                        //bound=16
                        bound = nextBound;
                        //i=31
                        i = nextIndex - 1;
                        //设置不用向前推进
                        advance = false;
                    }
                }
                if (i < 0 || i >= n || i + n >= nextn) {
        
                    int sc;
                    //已经完成转移
                    if (finishing) {
        
                        nextTable = null;
                        //这里完成nextTab=>table转换
                        table = nextTab;
                        //为扩容后的0.75
                        sizeCtl = (n << 1) - (n >>> 1);
                        return;
                    }
                    //正在工作的线程数-1,并返回
                    if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, sc - 1)) {
        
                        //说明执行到了最后一个线程,则直接返回
                        if ((sc - 2) != resizeStamp(n) << RESIZE_STAMP_SHIFT)
                            return;
                        finishing = advance = true;
                        i = n; // recheck before commit
                    }
                }
                else if ((f = tabAt(tab, i)) == null)
                    //数组中把null的元素设置为ForwardingNode节点(hash值为MOVED)
                    advance = casTabAt(tab, i, null, fwd);
                else if ((fh = f.hash) == MOVED)
                    //表示已有线程正在处理
                    advance = true; // already processed
                else {
        
                    synchronized (f) {
        
                        //双重检查加锁
                        if (tabAt(tab, i) == f) {
        
                            Node<K,V> ln, hn;
                            //>=0说明是node节点
                            if (fh >= 0) {
        
                                //为0则表示放在扩容后数组当前索引下,否则放在n+之前位置索引下
                                int runBit = fh & n;
                                Node<K,V> lastRun = f;
                                /*
                                循环结束之后,runBit就是最后不变的hash&n的值
                                也就是说由lastRun节点后的hash&n的值一样,这样就可以直接保存,而不需要处理后面的节点
                                 */
                                for (Node<K,V> p = f.next; p != null; p = p.next) {
        
                                    int b = p.hash & n;
                                    if (b != runBit) {
        
                                        runBit = b;
                                        lastRun = p;
                                    }
                                }
                                //说明之后的节点都是低位
                                if (runBit == 0) {
        
                                    ln = lastRun;
                                    hn = null;
                                }
                                else {
        
                                    //说明之后的节点都是高位
                                    hn = lastRun;
                                    ln = null;
                                }
                                //前面的节点不确定高低位,所以遍历f~lastRun范围的所有节点
                                //分别逆序存入ln或hn链表中
                                for (Node<K,V> p = f; p != lastRun; p = p.next) {
        
                                    int ph = p.hash; K pk = p.key; V pv = p.val;
                                    if ((ph & n) == 0)
                                        ln = new Node<K,V>(ph, pk, pv, ln);
                                    else
                                        hn = new Node<K,V>(ph, pk, pv, hn);
                                }
                                //存入之前的位置
                                setTabAt(nextTab, i, ln);
                                //存入改变后的位置
                                setTabAt(nextTab, i + n, hn);
                                //设置fwd,这样其他线程执行的时候,会跳过去.
                                setTabAt(tab, i, fwd);
                                advance = true;
                            }
                            else if (f instanceof TreeBin) {
        
                                //红黑树处理
                                TreeBin<K,V> t = (TreeBin<K,V>)f;
                                TreeNode<K,V> lo = null, loTail = null;
                                TreeNode<K,V> hi = null, hiTail = null;
                                int lc = 0, hc = 0;
                                for (Node<K,V> e = t.first; e != null; e = e.next) {
        
                                    int h = e.hash;
                                    TreeNode<K,V> p = new TreeNode<K,V>
                                        (h, e.key, e.val, null, null);
                                    if ((h & n) == 0) {
        
                                        if ((p.prev = loTail) == null)
                                            lo = p;
                                        else
                                            loTail.next = p;
                                        loTail = p;
                                        ++lc;
                                    }
                                    else {
        
                                        if ((p.prev = hiTail) == null)
                                            hi = p;
                                        else
                                            hiTail.next = p;
                                        hiTail = p;
                                        ++hc;
                                    }
                                }
                                /*
                                 * 在复制完树节点之后，判断该节点处构成的树还有几个节点，
                                 * 如果≤6个的话，就转为一个链表
                                 */
                                ln = (lc <= UNTREEIFY_THRESHOLD) ? untreeify(lo) :
                                    (hc != 0) ? new TreeBin<K,V>(lo) : t;
                                hn = (hc <= UNTREEIFY_THRESHOLD) ? untreeify(hi) :
                                    (lc != 0) ? new TreeBin<K,V>(hi) : t;
                                //低位链表存储i处
                                setTabAt(nextTab, i, ln);
                                //高位存储i+n处
                                setTabAt(nextTab, i + n, hn);
                                //原来tab中存储fwd,标识该桶扩容完成
                                setTabAt(tab, i, fwd);
                                advance = true;
                            }
                        }
                    }
                }
            }
        }
    
    
       final Node<K,V>[] helpTransfer(Node<K,V>[] tab, Node<K,V> f) {
        
            Node<K,V>[] nextTab; int sc;
            if (tab != null && (f instanceof ForwardingNode) &&
                (nextTab = ((ForwardingNode<K,V>)f).nextTable) != null) {
        
                int rs = resizeStamp(tab.length);
                while (nextTab == nextTable && table == tab &&
                       (sc = sizeCtl) < 0) {
        
                    //如果 sc 的高 16 位也就是当前n扩容标识,不等于标识符,这说明扩容的容量变化了,不是当前原容量扩容
                    if ((sc >>> RESIZE_STAMP_SHIFT) != rs
                            // 如果 sc == 标识符 + 1
                            //      （扩容结束了，不再有线程进行扩容）（默认第一个线程设置 sc ==rs 左移 16 位 + 2，
                            //       当第一个线程结束扩容了，就会将 sc 减一。这个时候，sc 就等于 rs + 1）
                            || sc == rs + 1 ||
                            // 如果 sc == 标识符 + 65535（帮助线程数已经达到最大）
                        sc == rs + MAX_RESIZERS || 
                            //说明已经扩容完成又或者有足够的线程扩容
                            transferIndex <= 0)
                        break;
                    //线程数+1,帮助一起转换
                    if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1)) {
        
                        transfer(tab, nextTab);
                        break;7
                    }
                }
                return nextTab;
            }
            return table;
        }

### get ###

public V get(Object key) {
        
            Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
            int h = spread(key.hashCode());
            if ((tab = table) != null && (n = tab.length) > 0 &&
                (e = tabAt(tab, (n - 1) & h)) != null) {
        
                //如果first匹配key-value,则直接返回
                if ((eh = e.hash) == h) {
        
                    if ((ek = e.key) == key || (ek != null && key.equals(ek)))
                        return e.val;
                }
                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;
        }

### addCount ###

private final void addCount(long x, int check) {
        
            CounterCell[] as; long b, s;
            /*
            as不为空,说明counterCells数组已创建了,进入条件体继续执行
            若为空,则说明数组还没创建,预测竞争线程少,直接cas操作baseCount
            如果成功,则执行下一步,若失败,则进入条件体继续执行
             */
            if ((as = counterCells) != null ||
                !U.compareAndSwapLong(this, BASECOUNT, b = baseCount, s = b + x)) {
        
                CounterCell a; long v; int m;
                //标记未发生竞争
                boolean uncontended = true;
                //数组为空
                if (as == null || (m = as.length - 1) < 0 ||
                        //给当前线程随机生成一个数,获取counterCells对应值,若为null,则进入条件体
                    (a = as[ThreadLocalRandom.getProbe() & m]) == null ||
                        //条件语句执行到这里,说明counterCells不为空,且有值.则尝试修改个数
                        //修改失败,则标记竞争
                    !(uncontended =
                      U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x))) {
        
                    //继续累加次数
                    fullAddCount(x, uncontended);
                    return;
                }
                if (check <= 1)
                    return;
                //计算CounterCell总个数
                s = sumCount();
            }
            //扩容
            if (check >= 0) {
        
                Node<K,V>[] tab, nt; int n, sc;
                //元素个数达到扩容的阀值,且table不为空,且数组长度小于最大容量
                while (s >= (long)(sc = sizeCtl) && (tab = table) != null &&
                       (n = tab.length) < MAXIMUM_CAPACITY) {
        
                    //根据length获取一个标识符
                    //高16位置0
                    //第16位为1
                    //低15位存当前n扩容标识
                    int rs = resizeStamp(n);
                    //sc<0说明正在扩容
                    if (sc < 0) {
        
                        // 如果 sc 的高 16 位也就是当前n扩容标识,不等于标识符,这说明扩容的容量变化了,不是当前原容量扩容
                        // 如果 sc == 标识符 + 1
                        //      （扩容结束了，不再有线程进行扩容）（默认第一个线程设置 sc ==rs 左移 16 位 + 2，
                        //       当第一个线程结束扩容了，就会将 sc 减一。这个时候，sc 就等于 rs + 1）
                        // 如果 sc == 标识符 + 65535（帮助线程数已经达到最大）
                        // 如果 nextTable == null（结束扩容了）
                        // 如果 transferIndex <= 0 (转移状态变化了)
                        // 结束循环
                        if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
                            sc == rs + MAX_RESIZERS || (nt = nextTable) == null ||
                            transferIndex <= 0)
                            break;
                        //sc+1,帮助扩容
                        if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1))
                            transfer(tab, nt);
                    }
                    //初始化扩容,
                    else if (U.compareAndSwapInt(this, SIZECTL, sc,
                                                 //高第16位为1,显示负数
                                                 //高15位容量n扩容标志
                                                //低16位,并行扩容线程数+1
                                                 (rs << RESIZE_STAMP_SHIFT) + 2))
                        //扩容,第二个参数代表新表,传入null,表示第一次初始化新表
                        transfer(tab, null);
                    s = sumCount();
                }
            }
        }
    
     private final void fullAddCount(long x, boolean wasUncontended) {
        
            int h;
            //如果当前线程随机数为0,则强制初始一个值
            if ((h = ThreadLocalRandom.getProbe()) == 0) {
        
                ThreadLocalRandom.localInit();      // force initialization
                h = ThreadLocalRandom.getProbe();
                //设置无竞争
                wasUncontended = true;
            }
            //标记是否发生碰撞
            boolean collide = false;                // True if last slot nonempty
            for (;;) {
        
                CounterCell[] as; CounterCell a; int n; long v;
                //counterCells不为null
                if ((as = counterCells) != null && (n = as.length) > 0) {
        
                    //当前线程所在格子为空
                    if ((a = as[(n - 1) & h]) == null) {
        
                        //锁未占用
                        if (cellsBusy == 0) {
                    // Try to attach new Cell
                            //新建CounterCell
                            CounterCell r = new CounterCell(x); // Optimistic create
                            //再次检查锁未占用,尝试加锁
                            if (cellsBusy == 0 &&
                                U.compareAndSwapInt(this, CELLSBUSY, 0, 1)) {
        
                                //表示创建CounterCell是否成功状态
                                boolean created = false;
                                try {
                       // Recheck under lock
                                    CounterCell[] rs; int m, j;
                                    //再次检查counterCells不为空,且格子为占用
                                    if ((rs = counterCells) != null &&
                                        (m = rs.length) > 0 &&
                                        rs[j = (m - 1) & h] == null) {
        
                                        //设置格子
                                        rs[j] = r;
                                        //设置创建状态
                                        created = true;
                                    }
                                } finally {
        
                                    //释放锁
                                    cellsBusy = 0;
                                }
                                //正确创建则退出循环
                                if (created)
                                    break;
                                continue;           // Slot is now non-empty
                            }
                        }
                        //表明cellsBusy=1锁上发生竞争,则重新生成随机数,进行下次循环
                        collide = false;
                    }
                    //CAS 失败,重新继续
                    else if (!wasUncontended)       // CAS already known to fail
                        wasUncontended = true;      // Continue after rehash
                    //执行到这里说明wasUncontended=true,认为无竞争
                    //且所在槽有值
    
                    //2:尝试直接累加
                    else if (U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x))
                        break;
                    //3:数组发生变化,说明发生了扩容或者数组长度>=cpu核心数,
                    //则认为无碰撞
                    //当扩容超过限制后,则会不停的执行3和4,直到2成功
                    else if (counterCells != as || n >= NCPU)
                        collide = false;            // At max size or stale
                    //4:数组没变化且数组长度<CPU核心数,且collide认为无碰撞,则设置有碰撞
                    else if (!collide)
                        collide = true;
                    //执行到这里,说明数组没变化,且有碰撞,则需要扩容
                    else if (
                            //无锁
                            cellsBusy == 0 &&
                                    //尝试加锁
                             U.compareAndSwapInt(this, CELLSBUSY, 0, 1)) {
        
                        try {
        
                            //counterCells没发生变化
                            if (counterCells == as) {
        // Expand table unless stale
                                //扩容counterCells一倍容量
                                CounterCell[] rs = new CounterCell[n << 1];
                                for (int i = 0; i < n; ++i)
                                    rs[i] = as[i];
                                counterCells = rs;
                            }
                        } finally {
        
                            //释放锁
                            cellsBusy = 0;
                        }
                        collide = false;
                        continue;                   // Retry with expanded table
                    }
                    //重新生成随机数,进行下次循环
                    h = ThreadLocalRandom.advanceProbe(h);
                }
                //执行到这里说明counterCells为空,判断锁是否未被占用,尝试加锁
                else if (cellsBusy == 0 && counterCells == as &&
                         U.compareAndSwapInt(this, CELLSBUSY, 0, 1)) {
        
                    boolean init = false;
                    try {
                                   // Initialize table
                        //再次判断counterCells是否有变化
                        if (counterCells == as) {
        
                            //新建长度2的数组
                            CounterCell[] rs = new CounterCell[2];
                            rs[h & 1] = new CounterCell(x);
                            counterCells = rs;
                            //标记初始化完成
                            init = true;
                        }
                    } finally {
        
                        //释放锁
                        cellsBusy = 0;
                    }
                    //跳出循环
                    if (init)
                        break;
                }
                //数组为空,抢锁失败,则尝试直接累加baseCount值
                else if (U.compareAndSwapLong(this, BASECOUNT, v = baseCount, v + x))
                    break;                          // Fall back on using base
            }
        }

### replace\#remove ###

public V remove(Object key) {
        
            return replaceNode(key, null, null);
        }
     
        /**
         * {@inheritDoc}
         *
         * @throws NullPointerException if any of the arguments are null
         * key映射有值,值为oldValue,则更新
         */
        public boolean replace(K key, V oldValue, V newValue) {
        
            if (key == null || oldValue == null || newValue == null)
                throw new NullPointerException();
            return replaceNode(key, newValue, oldValue) != null;
        }
    
    
        final V replaceNode(Object key, V value, Object cv) {
        
            int hash = spread(key.hashCode());
            for (Node<K,V>[] tab = table;;) {
        
                Node<K,V> f; int n, i, fh;
                //空判断
                if (tab == null || (n = tab.length) == 0 ||
                    (f = tabAt(tab, i = (n - 1) & hash)) == null)
                    break;
                //正在扩容,则加入扩容队伍
                else if ((fh = f.hash) == MOVED)
                    tab = helpTransfer(tab, f);
                else {
        
                    V oldVal = null;
                    boolean validated = false;
                    synchronized (f) {
        
                        //双重检查加锁,DCL
                        if (tabAt(tab, i) == f) {
        
                            //对链表的处理
                            if (fh >= 0) {
        
                                validated = true;
                                for (Node<K,V> e = f, pred = null;;) {
        
                                    K ek;
                                    //匹配key
                                    if (e.hash == hash &&
                                        ((ek = e.key) == key ||
                                         (ek != null && key.equals(ek)))) {
        
                                        V ev = e.val;
                                        //匹配value
                                        if (cv == null || cv == ev ||
                                            (ev != null && cv.equals(ev))) {
        
                                            oldVal = ev;
                                            //修改
                                            if (value != null)
                                                e.val = value;
                                            //value=null,说明执行删除操作
                                            else if (pred != null)
                                                pred.next = e.next;
                                            //当匹配的值是first节点的处理
                                            else
                                                setTabAt(tab, i, e.next);
                                        }
                                        break;
                                    }
                                    //临时保存上一个节点,便于执行删除节点操作
                                    pred = e;
                                    //执行最后一个节点,则退出
                                    if ((e = e.next) == null)
                                        break;
                                }
                            }
                            //红黑树的处理
                            else if (f instanceof TreeBin) {
        
                                validated = true;
                                TreeBin<K,V> t = (TreeBin<K,V>)f;
                                TreeNode<K,V> r, p;
                                if ((r = t.root) != null &&
                                    (p = r.findTreeNode(hash, key, null)) != null) {
        
                                    V pv = p.val;
                                    if (cv == null || cv == pv ||
                                        (pv != null && cv.equals(pv))) {
        
                                        oldVal = pv;
                                        if (value != null)
                                            p.val = value;
                                        else if (t.removeTreeNode(p))
                                            setTabAt(tab, i, untreeify(t.first));
                                    }
                                }
                            }
                        }
                    }
                    if (validated) {
        
                        if (oldVal != null) {
        
                            if (value == null)
                                //记数-1
                                addCount(-1L, -1);
                            return oldVal;
                        }
                        break;
                    }
                }
            }
            return null;
        }

### 总结: ###

#### 什么时候扩容? ####

1.  单节点容量>=8且容量<64,则扩容一倍
2.  当数组中元素达到了sizeCtl的数量的时候，则会调用transfer方法来进行扩容

没有实现对map进行加锁来执行独占访问,因为采用了分段锁,所以无法使用客户端加锁来创建新的原子操作,如若没有则添加之内操作.

#### JDK1.8放弃分段锁 ####

段Segment继承了重入锁ReentrantLock，有了锁的功能，每个锁控制的是一段，当每个Segment越来越大时，锁的粒度就变得有些大了。  
分段锁的优势在于保证在操作不同段 map 的时候可以并发执行，操作同段 map 的时候，进行锁的竞争和等待。这相对于直接对整个map同步synchronized是有优势的。  
缺点在于分成很多段时会比较浪费内存空间(不连续，碎片化); 操作map时竞争同一个分段锁的概率非常小时，分段锁反而会造成更新等操作的长时间等待; 当某个段很大时，分段锁的性能会下降。

#### jdk1.8的map实现 ####

和hashmap一样,jdk 1.8中ConcurrentHashmap采用的底层数据结构为数组+链表+红黑树的形式。数组可以扩容，链表可以转化为红黑树。

#### 为什么不用ReentrantLock而用synchronized ? ####

减少内存开销:如果使用ReentrantLock则需要节点继承AQS来获得同步支持，增加内存开销，而1.8中只有头节点需要进行同步。  
内部优化:synchronized则是JVM直接支持的，JVM能够在运行时作出相应的优化措施：锁粗化、锁消除、锁自旋等等。

#### 多个线程又是如何同步处理的呢？ ####

1.  同步处理主要是通过Synchronized和unsafe两种方式来完成的。
2.  在取得sizeCtl、某个位置的Node的时候，使用的都是unsafe的方法，来达到并发安全的目的  
    当需要在某个位置设置节点的时候，则会通过Synchronized的同步机制来锁定该位置的节点。
3.  在数组扩容的时候，则通过处理的步长和fwd节点来达到并发安全的目的，通过设置hash值为MOVED
4.  当把某个位置的节点复制到扩张后的table的时候，也通过Synchronized的同步机制来保证现程安全

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L051YW5fRmVuZw_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200525225014811.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L051YW5fRmVuZw==,size_16,color_FFFFFF,t_70