【JUC系列】并发容器之ConcurrentHashMap(JDK1.8版)

ConcurrentHashMap（JDK1.8）

文章目录

ConcurrentHashMap（JDK1.8）
- 组成
- - 内部类
  - - Node
    - ForwardingNode
    - TreeNode
    - TreeBin
  - 数据结构
  - 核心方法
  - - `int spread(int h)`计算hash值
  - 构造函数
  - PUT过程
  - - putVal(K key, V value, boolean onlyIfAbsent)
    - initTable()
    - helpTransfer(tab, f)
    - transfer(tab, nextTab)
    - treeifyBin(tab, index)
    - tryPresize(int size)
    - addCount(long x, int check)
    - fullAddCount(long x, boolean wasUncontended)
  - GET过程
  - - get(Object key)
  - Replace和Remove过程
  - - replaceNode(Object key, V value, Object cv)
  - 其他
  - - sizeCtl

在JDK1.5~1.7版本，Java使用了分段锁机制实现ConcurrentHashMap。在使用中发现最大并发度受Segment的个数限制。因此，在JDK1.8中，ConcurrentHashMap的实现原理摒弃了这种设计，而是选择了与HashMap类似的数组+链表+红黑树的方式实现，而加锁则采用CAS和synchronized实现。

组成内部类 Node

拥有键值对的链表的基础存储结构

    static class Node implements Map.Entry {
        // key的hash值
        final int hash;
        // 关键字
        final K key;
        // 存储值
        volatile V val;
        // 下一个结点
        volatile Node next;

        Node(int hash, K key, V val, Node next) {
            this.hash = hash;
            this.key = key;
            this.val = val;
            this.next = next;
        }

        public final K getKey()       { return key; }
        public final V getValue()     { return val; }
        public final int hashCode()   { return key.hashCode() ^ val.hashCode(); }
        public final String toString(){ return key + "=" + val; }
        public final V setValue(V value) {
            throw new UnsupportedOperationException();
        }

        public final boolean equals(Object o) {
            Object k, v, u; Map.Entry e;
            return ((o instanceof Map.Entry) &&
                    (k = (e = (Map.Entry)o).getKey()) != null &&
                    (v = e.getValue()) != null &&
                    (k == key || k.equals(key)) &&
                    (v == (u = val) || v.equals(u)));
        }

        
        Node find(int h, Object k) {
            Node e = this;
            if (k != null) {
                do {
                    K ek;
                    if (e.hash == h &&
                        ((ek = e.key) == k || (ek != null && k.equals(ek))))
                        return e;
                } while ((e = e.next) != null);
            }
            return null;
        }
    }

ForwardingNode

在transfer操作期间插入到 bin 头部的节点。

static final class ForwardingNode extends Node {
    // node数组，存放的什么？
    final Node[] nextTable;
    ForwardingNode(Node[] tab) {
        super(MOVED, null, null, null);
        this.nextTable = tab;
    }

    Node find(int h, Object k) {
        // loop to avoid arbitrarily deep recursion on forwarding nodes
        outer: for (Node[] tab = nextTable;;) {
            Node e; int n;
            if (k == null || tab == null || (n = tab.length) == 0 ||
                (e = tabAt(tab, (n - 1) & h)) == null)
                return null;
            for (;;) {
                int eh; K ek;
                if ((eh = e.hash) == h &&
                    ((ek = e.key) == k || (ek != null && k.equals(ek))))
                    return e;
                if (eh < 0) {
                    if (e instanceof ForwardingNode) {
                        tab = ((ForwardingNode)e).nextTable;
                        continue outer;
                    }
                    else
                        return e.find(h, k);
                }
                if ((e = e.next) == null)
                    return null;
            }
        }
    }
}

TreeNode

作为红黑树结构的存储结构，比一般红黑树存储结构出来的next和prev，可以将这些结点变成双向的链表结构，是为了方便从链表变为红黑树，在从红黑树变成链表。在ConcurrentHashMap中，链表与红黑树的转变是依据链表中的结点数量，默认变成红黑树的链表结点个数需要大于8。

hash	key	val	next	prev	parent	left	right	red
key的hash值	关键字	具体值	下一个结点	上一个结点	双亲结点	左子结点	右子结点	结点颜色

static final class TreeNode extends Node {
    TreeNode parent;  // red-black tree links
    TreeNode left;
    TreeNode right;
    TreeNode prev;    // needed to unlink next upon deletion
    boolean red;

    TreeNode(int hash, K key, V val, Node next,
             TreeNode parent) {
        super(hash, key, val, next);
        this.parent = parent;
    }

    Node find(int h, Object k) {
        return findTreeNode(h, k, null);
    }

    
    final TreeNode findTreeNode(int h, Object k, Class kc) {
        if (k != null) {
            TreeNode p = this;
            do  {
                int ph, dir; K pk; TreeNode q;
                TreeNode pl = p.left, pr = p.right;
                if ((ph = p.hash) > h)
                    p = pl;
                else if (ph < h)
                    p = pr;
                else if ((pk = p.key) == k || (pk != null && k.equals(pk)))
                    return p;
                else if (pl == null)
                    p = pr;
                else if (pr == null)
                    p = pl;
                else if ((kc != null ||
                          (kc = comparableClassFor(k)) != null) &&
                         (dir = compareComparables(kc, k, pk)) != 0)
                    p = (dir < 0) ? pl : pr;
                else if ((q = pr.findTreeNode(h, k, kc)) != null)
                    return q;
                else
                    p = pl;
            } while (p != null);
        }
        return null;
    }
}

TreeBin

继承Node，树标记结构，表明该结点背后有一棵红黑树。在新增结点和删除结点的时候，为了并发的安全都需要会进行锁的竞争。root和first不应该是同一个结点。

        TreeNode root;
        volatile TreeNode first;
        volatile Thread waiter;
        volatile int lockState;

为了减少本篇篇幅长度，将红黑树的实现部分拆分出去：ConcurrentHashMap(JDK1.8)中红黑树的实现

数据结构

核心方法

方法名	描述
V putVal(K key, V value, boolean onlyIfAbsent)	将指定键映射到此表中的指定值。键和值都不能为空。可以通过使用与原始键相同的键调用 get 方法来检索该值。 onlyIfAbsent:true 代表不更新旧值，false更新旧值
Node[] initTable()	使用 sizeCtl 中记录的大小初始化表。第一级结点存储的数组结构
void transfer(Node[] tab, Node[] nextTab)	将每个 bin 中的节点移动和/或复制到新表。
void treeifyBin(Node[] tab, int index)	在给定的索引中替换所有链接节点将简单的链表改为红黑树，除非表太小（数组长度小于64），在这种情况下对Node数组进行扩容，扩2倍
void tryPresize(int size)	尝试预先调整表格大小以容纳给定数量的元素。即将Node数组扩容到指定的size大小。
void addCount(long x, int check)	添加到计数中，如果Node数组太小并且尚未调整大小，则启动transfer。如果已经调整大小，则在工作可用时帮助执行扩容（多线程扩容，在线程数量允许的情况下，一起进行扩容操作，扩容线程已满的话，自旋重新检查）。转移后重新检查占用情况，以查看是否已经需要再次调整大小，因为调整大小滞后于添加。
V get(Object key)	返回指定键映射到的值，如果此映射不包含该键的映射，则返回 null。更正式地说，如果此映射包含从键 k 到值 v 的映射，使得 key.equals( k)，则此方法返回 v；否则返回null。（最多可以有一个这样的映射。）
V replaceNode(Object key, V value, Object cv)	四种公共删除/替换方法的实现：用 v 替换节点值，如果非空，则以 cv 匹配为条件。如果value为空，则删除。

int spread(int h)计算hash值

static final int HASH_BITS = 0x7fffffff; // 正常节点哈希的可用位,十六进制表示法，一个十六进制数占4个bit。int一个32位（bit），那需要8个十六进制数，故可以理解为0x7 f f f f f f f，F的二进制为1111，7的二进制0111.

static final int spread(int h) {
    return (h ^ (h >>> 16)) & HASH_BITS;
}

构造函数

ConcurrentHashMap(int initialCapacity)

创建一个新的空映射，其初始表大小可容纳指定数量的元素，无需动态调整大小。

参数

initialCapacity：初始容量。

public ConcurrentHashMap(int initialCapacity) {
    if (initialCapacity < 0)
        throw new IllegalArgumentException();
    int cap = ((initialCapacity >= (MAXIMUM_CAPACITY >>> 1)) ?
               MAXIMUM_CAPACITY :
               tableSizeFor(initialCapacity + (initialCapacity >>> 1) + 1));
    this.sizeCtl = cap;
}

ConcurrentHashMap(int initialCapacity, float loadFactor, int concurrencyLevel)

根据给定的元素数 (initialCapacity)、表密度 (loadFactor) 和并发更新线程数 (concurrencyLevel) 创建一个新的空映射，其初始表大小。

参数

initialCapacity：初始容量。给定指定的负载因子，实现执行内部大小调整以适应这么多元素。
loadFactor：用于建立初始表大小的负载因子（表密度）。
concurrencyLevel：估计的并发更新线程数。实现可以使用这个值作为大小提示。

    public ConcurrentHashMap(int initialCapacity, float loadFactor, int concurrencyLevel) {
        if (!(loadFactor > 0.0f) || initialCapacity < 0 || concurrencyLevel <= 0)
            throw new IllegalArgumentException();
        // 若出现初始容量小于并发数，则以并发数的值作为初始容量
        if (initialCapacity < concurrencyLevel)   // Use at least as many bins
            initialCapacity = concurrencyLevel;   // as estimated threads
        long size = (long)(1.0 + (long)initialCapacity / loadFactor);
        int cap = (size >= (long)MAXIMUM_CAPACITY) ?
            MAXIMUM_CAPACITY : tableSizeFor((int)size);
        this.sizeCtl = cap;
    }

int tableSizeFor(int c)计算数组的大小，通过初始值*1.5+1，然后向上取2的n次方。

    private static final int tableSizeFor(int c) {
        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;
    }

PUT过程 putVal(K key, V value, boolean onlyIfAbsent)

    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();
        // 计算hash值
        int hash = spread(key.hashCode());
        // 对应链表长度？？？
        int binCount = 0;
        // 存放数据的Node数组
        for (Node[] tab = table;;) {
            Node f; int n, i, fh;
            // 若Node[]还是null或没有元素，则需要进行初始化
            if (tab == null || (n = tab.length) == 0)
                // 初始化数组
                tab = initTable();
            // 至此代表容器中的数组已经成功初始化，找该 hash 值对应的数组下标，得到第一个节点 f；
            // 若f为null，使用CAS操作直接将新节点放到数组下标i的位置，执行成功直接退出for，执行失败代表存在竞争，继续执行
            else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
                if (casTabAt(tab, i, null,
                             new Node(hash, key, value, null)))
                    break;                   // no lock when adding to empty bin
            }
            // MOVED代表在扩容
            else if ((fh = f.hash) == MOVED)
                // 帮助数据迁移
                tab = helpTransfer(tab, f);
            else {
                // 此时数组当前下标的元素的头结点f，不为空
                V oldVal = null;
                // 对这个位置的头结点上锁
                synchronized (f) {
                    if (tabAt(tab, i) == f) {
                        // 对此头结点的hash进行判断，若值>=0则说明是数组此下标的元素是个链表
                        if (fh >= 0) {
                            // 链表节点计数，由头结点从1开始
                            binCount = 1;
                            // 遍历链表
                            for (Node e = f;; ++binCount) {
                                K ek;
                                // 如果发现了"相等"的 key，判断是否要进行值覆盖，然后也就可以 break 了
                                if (e.hash == hash &&
                                    ((ek = e.key) == key ||
                                     (ek != null && key.equals(ek)))) {
                                    oldVal = e.val;
                                    if (!onlyIfAbsent)
                                        e.val = value;
                                    break;
                                }
                                // 到了链表的最末端，将这个新值放到链表的最后面
                                Node pred = e;
                                if ((e = e.next) == null) {
                                    pred.next = new Node(hash, key, value, null);
                                    break;
                                }
                            }
                        }
                        // 此时头结点的hash小于0，检查数组此下标的元素是不是红黑树
                        else if (f instanceof TreeBin) {
                            Node p;
                            //为啥这个计数从2开始？
                            binCount = 2;
                            // 调用红黑树的插值方法插入新节点
                            if ((p = ((TreeBin)f).putTreeVal(hash, key, value)) != null) {
                                oldVal = p.val;
                                if (!onlyIfAbsent)
                                    p.val = value;
                            }
                        }
                    }
                }
                if (binCount != 0) {
                    // 判断是否尝试要将链表转换为红黑树，TREEIFY_THRESHOLD=8
                    if (binCount >= TREEIFY_THRESHOLD)
                        treeifyBin(tab, i);
                    if (oldVal != null)
                        return oldVal;
                    break;
                }
            }
        }
        // 总元素个数+1
        addCount(1L, binCount);
        return null;
    }

initTable()

使用 sizeCtl 中记录的大小初始化表。

假设sizeCtl=16

sizeCtl:  16  -1   12
sc     :  0   16   12
n      :  -   16

    private final Node[] initTable() {
        Node[] tab; int sc;
        // 判断Node数组是否被初始化了
        while ((tab = table) == null || tab.length == 0) {
            // sizeCtl<0,应该是-1，代表有其他线程进行数组的初始化
            if ((sc = sizeCtl) < 0)
                Thread.yield(); // lost initialization race; just spin
            // CAS 一下，将 sizeCtl 设置为 -1，代表抢到了锁
            else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
                try {
                    // 再次检查数组是否为空？通过CAS操作成功不能代表当前线程获取初始化数组的，DEFAULT_CAPACITY默认16
                    if ((tab = table) == null || tab.length == 0) {
                        int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
                        @SuppressWarnings("unchecked")
                        Node[] nt = (Node[])new Node[n];
                        // 将这个数组赋值给 table，table 是 volatile 的
                        table = tab = nt;
                        // 其实就是 0.75 * n
                        sc = n - (n >>> 2);
                    }
                } finally {
                    sizeCtl = sc;
                }
                break;
            }
        }
        return tab;
    }

最终数组的长度为16，此时sizeCtl为12。

helpTransfer(tab, f)

//扩容状态下其他线程对集合进行插入、修改、删除、合并、compute等操作时遇到 ForwardingNode 节点会调用该帮助扩容方法
final Node[] helpTransfer(Node[] tab, Node f) {
    Node[] nextTab; int sc;
    if (tab != null && (f instanceof ForwardingNode) &&
        (nextTab = ((ForwardingNode)f).nextTable) != null) {
        int rs = resizeStamp(tab.length);
        while (nextTab == nextTable && table == tab && (sc = sizeCtl) < 0) {
            if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
                sc == rs + MAX_RESIZERS || transferIndex <= 0)
                break;
            if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1)) {
                transfer(tab, nextTab);
                break;
            }
        }
        return nextTab;
    }
    return table;
}

transfer(tab, nextTab)

addCount 向集合中插入新数据后更新容量计数时发现到达扩容阈值而触发的扩容
helpTransfer 扩容状态下其他线程对集合进行插入、修改、删除、合并、compute 等操作时遇到
tryPresize putAll批量插入或者插入后发现链表长度达到8个或以上，但数组长度为64以下时触发的扩容

private final void transfer(Node[] tab, Node[] nextTab) {
    int n = tab.length, stride;
    // 计算每条线程处理的桶个数，每条线程处理的桶数量一样，如果CPU为单核，则使用一条线程处理所有桶
    // 每条线程至少处理16个桶，如果计算出来的结果少于16，则一条线程处理16个桶
    if ((stride = (NCPU > 1) ? (n >>> 3) / NCPU : n) < MIN_TRANSFER_STRIDE)
        stride = MIN_TRANSFER_STRIDE; // subdivide range
    // 如果原数组为空，则初始化新数组(原数组长度的2倍)
    if (nextTab == null) {            // initiating
        try {
            @SuppressWarnings("unchecked")
            Node[] nt = (Node[])new Node[n << 1];
            nextTab = nt;
        } catch (Throwable ex) {      // try to cope with OOME
            sizeCtl = Integer.MAX_VALUE;
            return;
        }
        nextTable = nextTab;
        // 将 transferIndex 指向最右边的桶，也就是数组索引下标最大的位置
        transferIndex = n;
    }
    // 新node数组长度
    int nextn = nextTab.length;
    // 新建一个占位对象ForwardingNode，该占位对象的 hash 值为 -1 该占位对象存在时表示集合正在扩容状态，key、value、next 属性均为 null ，nextTable 属性指向扩容后的数组
    // 该占位对象主要有两个用途：
    // 1、占位作用，用于标识数组该位置的桶已经迁移完毕，处于扩容中的状态。
    // 2、作为一个转发的作用，扩容期间如果遇到查询操作，遇到转发节点，会把该查询操作转发到新的数组上去，不会阻塞查询操作。
    ForwardingNode fwd = new ForwardingNode(nextTab);
    //该标识用于控制是否继续处理下一个桶，为 true 则表示已经处理完当前桶，可以继续迁移下一个桶的数据
    boolean advance = true;
    //该标识用于控制扩容何时结束，该标识还有一个用途是最后一个扩容线程会负责重新检查一遍数组查看是否有遗漏的桶
    boolean finishing = false; // to ensure sweep before committing nextTab
    //这个循环用于处理一个 stride 长度的任务，i 后面会被赋值为该 stride 内最大的下标，而 bound 后面会被赋值为该 stride 内最小的下标
    //通过循环不断减小 i 的值，从右往左依次迁移桶上面的数据，直到 i 小于 bound 时结束该次长度为 stride 的迁移任务
    //结束这次的任务后会通过外层 addCount、helpTransfer、tryPresize 方法的 while 循环达到继续领取其他任务的效果
    for (int i = 0, bound = 0;;) {
        Node f; int fh;
        while (advance) {
            int nextIndex, nextBound;
            // 每处理完一个hash桶就将 bound 进行减 1 操作
            if (--i >= bound || finishing)
                advance = false;
            else if ((nextIndex = transferIndex) <= 0) {
                //transferIndex <= 0 说明数组的hash桶已被线程分配完毕，没有了待分配的hash桶，将 i 设置为 -1 ，后面的代码根据这个数值退出当前线的扩容操作
                i = -1;
                advance = false;
            }
            //只有首次进入for循环才会进入这个判断里面去，设置 bound 和 i 的值，也就是领取到的迁移任务的数组区间
            else if (U.compareAndSwapInt
                     (this, TRANSFERINDEX, nextIndex,
                      nextBound = (nextIndex > stride ?
                                   nextIndex - stride : 0))) {
                bound = nextBound;
                i = nextIndex - 1;
                advance = false;
            }
        }
        if (i < 0 || i >= n || i + n >= nextn) {
            int sc;
            //扩容结束后做后续工作，将 nextTable 设置为 null，表示扩容已结束，将 table 指向新数组，sizeCtl 设置为扩容阈值
            if (finishing) {
                nextTable = null;
                table = nextTab;
                sizeCtl = (n << 1) - (n >>> 1);
                return;
            }
            //每当一条线程扩容结束就会更新一次 sizeCtl 的值，进行减 1 操作
            if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, sc - 1)) {
                //若成立，说明该线程不是扩容大军里面的最后一条线程，直接return回到上层while循环
                if ((sc - 2) != resizeStamp(n) << RESIZE_STAMP_SHIFT)
                    return;
                //(sc - 2) == resizeStamp(n) << RESIZE_STAMP_SHIFT 说明这条线程是最后一条扩容线程
                //之所以能用这个来判断是否是最后一条线程，因为第一条扩容线程进行了如下操作：
                //    U.compareAndSwapInt(this, SIZECTL, sc, (rs << RESIZE_STAMP_SHIFT) + 2)
                //除了修改结束标识之外，还得设置 i = n; 以便重新检查一遍数组，防止有遗漏未成功迁移的桶
                finishing = advance = true;
                i = n; // recheck before commit
            }
        }
        else if ((f = tabAt(tab, i)) == null)
            //遇到数组上空的位置直接放置一个占位对象，以便查询操作的转发和标识当前处于扩容状态
            advance = casTabAt(tab, i, null, fwd);
        else if ((fh = f.hash) == MOVED)
            //数组上遇到hash值为MOVED，也就是 -1 的位置，说明该位置已经被其他线程迁移过了，将 advance 设置为 true ，以便继续往下一个桶检查并进行迁移操作
            advance = true; // already processed
        else {
            synchronized (f) {
                if (tabAt(tab, i) == f) {
                    Node ln, hn;
                    //该节点为链表结构
                    if (fh >= 0) {
                        int runBit = fh & n;
                        Node lastRun = f;
                        //遍历整条链表，找出 lastRun 节点
                        for (Node p = f.next; p != null; p = p.next) {
                            int b = p.hash & n;
                            if (b != runBit) {
                                runBit = b;
                                lastRun = p;
                            }
                        }
                        //根据 lastRun 节点的高位标识(0 或 1)，首先将 lastRun设置为 ln 或者 hn 链的末尾部分节点，后续的节点使用头插法拼接
                        if (runBit == 0) {
                            ln = lastRun;
                            hn = null;
                        }
                        else {
                            hn = lastRun;
                            ln = null;
                        }
                        //使用高位和低位两条链表进行迁移，使用头插法拼接链表
                        for (Node 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(ph, pk, pv, ln);
                            else
                                hn = new Node(ph, pk, pv, hn);
                        }
                        //setTabAt方法调用的是 Unsafe 类的 putObjectVolatile 方法
                        //使用 volatile 方式的 putObjectVolatile 方法，能够将数据直接更新回主内存，并使得其他线程工作内存的对应变量失效，达到各线程数据及时同步的效果
                        //使用 volatile 的方式将 ln 链设置到新数组下标为 i 的位置上
                        setTabAt(nextTab, i, ln);
                        //使用 volatile 的方式将 hn 链设置到新数组下标为 i + n(n为原数组长度) 的位置上
                        setTabAt(nextTab, i + n, hn);
                        //迁移完成后使用 volatile 的方式将占位对象设置到该 hash 桶上，该占位对象的用途是标识该hash桶已被处理过，以及查询请求的转发作用
                        setTabAt(tab, i, fwd);
                        //advance 设置为 true 表示当前 hash 桶已处理完，可以继续处理下一个 hash 桶
                        advance = true;
                    }
                    //该节点为红黑树结构
                    else if (f instanceof TreeBin) {
                        TreeBin t = (TreeBin)f;
                        //lo 为低位链表头结点，loTail 为低位链表尾结点，hi 和 hiTail 为高位链表头尾结点
                        TreeNode lo = null, loTail = null;
                        TreeNode hi = null, hiTail = null;
                        int lc = 0, hc = 0;
                        //同样也是使用高位和低位两条链表进行迁移
                        //使用for循环以链表方式遍历整棵红黑树，使用尾插法拼接 ln 和 hn 链表
                        for (Node e = t.first; e != null; e = e.next) {
                            int h = e.hash;
                            //这里面形成的是以 TreeNode 为节点的链表
                            TreeNode p = new TreeNode
                                (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;
                            }
                        }
                        //形成中间链表后会先判断是否需要转换为红黑树：
                        //1、如果符合条件则直接将 TreeNode 链表转为红黑树，再设置到新数组中去
                        //2、如果不符合条件则将 TreeNode 转换为普通的 Node 节点，再将该普通链表设置到新数组中去
                        //(hc != 0) ? new TreeBin(lo) : t 这行代码的用意在于，如果原来的红黑树没有被拆分成两份，那么迁移后它依旧是红黑树，可以直接使用原来的 TreeBin 对象
                        ln = (lc <= UNTREEIFY_THRESHOLD) ? untreeify(lo) :
                            (hc != 0) ? new TreeBin(lo) : t;
                        hn = (hc <= UNTREEIFY_THRESHOLD) ? untreeify(hi) :
                            (lc != 0) ? new TreeBin(hi) : t;
                        //setTabAt方法调用的是 Unsafe 类的 putObjectVolatile 方法
                        //使用 volatile 方式的 putObjectVolatile 方法，能够将数据直接更新回主内存，并使得其他线程工作内存的对应变量失效，达到各线程数据及时同步的效果
                        //使用 volatile 的方式将 ln 链设置到新数组下标为 i 的位置上
                        setTabAt(nextTab, i, ln);
                        //使用 volatile 的方式将 hn 链设置到新数组下标为 i + n(n为原数组长度) 的位置上
                        setTabAt(nextTab, i + n, hn);
                        //迁移完成后使用 volatile 的方式将占位对象设置到该 hash 桶上，该占位对象的用途是标识该hash桶已被处理过，以及查询请求的转发作用
                        setTabAt(tab, i, fwd);
                        //advance 设置为 true 表示当前 hash 桶已处理完，可以继续处理下一个 hash 桶
                        advance = true;
                    }
                }
            }
        }
    }
}

treeifyBin(tab, index)

当table长度小于64时，将数组长度按2倍进行扩容。若数组长度大于64且数组下标inde中的链表长度大于8时，会将插槽中的Node链表变为TreeNode，转换为红黑树。

    private final void treeifyBin(Node[] tab, int index) {
        Node b; int n, sc;
        if (tab != null) {
            // MIN_TREEIFY_CAPACITY 为 64
            // 所以，如果数组长度小于 64 的时候，其实也就是 32 或者 16 或者更小的时候，会进行数组扩容
            if ((n = tab.length) < MIN_TREEIFY_CAPACITY)
                tryPresize(n << 1);//如果数组整体容量太小则去扩容，放弃转红黑树结构
            // b 是头节点
            else if ((b = tabAt(tab, index)) != null && b.hash >= 0) {
                synchronized (b) {
                    if (tabAt(tab, index) == b) {
                        // 下面就是遍历链表，将Node链表变为TreeNode链表
                        TreeNode hd = null, tl = null;
                        for (Node e = b; e != null; e = e.next) {
                            TreeNode p =
                                new TreeNode(e.hash, e.key, e.val,
                                                  null, null);
                            if ((p.prev = tl) == null)
                                hd = p;
                            else
                                tl.next = p;
                            tl = p;
                        }
                        //hd 为链表的首结点，将TreeNode链表转为红黑树TreeBin
                        setTabAt(tab, index, new TreeBin(hd));
                    }
                }
            }
        }
    }

tryPresize(int size)

putAll批量插入或者插入节点后发现链表长度达到8个或以上，但数组长度为64以下时触发的扩容会调用到这个方法

    // 首先要说明的是，方法参数 size 传进来的时候就已经翻了倍了
	private final void tryPresize(int size) {
        // c: size 的 1.5 倍，再加 1，再往上取最近的 2 的 n 次方。
        int c = (size >= (MAXIMUM_CAPACITY >>> 1)) ? MAXIMUM_CAPACITY : tableSizeFor(size + (size >>> 1) + 1);
        int sc;
        //如果不满足条件，也就是 sizeCtl < 0 ，说明有其他线程正在扩容当中，这里也就不需要自己去扩容了，结束该方法
        while ((sc = sizeCtl) >= 0) {
            Node[] tab = table; int n;
            //如果数组初始化则进行初始化，这个选项主要是为批量插入操作方法 putAll 提供的
            if (tab == null || (n = tab.length) == 0) {
                n = (sc > c) ? sc : c;
                if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
                    try {
                        if (table == tab) {
                            @SuppressWarnings("unchecked")
                            Node[] nt = (Node[])new Node[n];
                            table = nt;
                            sc = n - (n >>> 2);// 0.75 * n
                        }
                    } finally {
                        //初始化完成后 sizeCtl 用于记录当前集合的负载容量值，也就是触发集合扩容的阈值
                        sizeCtl = sc;
                    }
                }
            }
            else if (c <= sc || n >= MAXIMUM_CAPACITY)
                break;
            //插入节点后发现链表长度达到8个或以上，但数组长度为64以下时触发的扩容会进入到下面这个 else if 分支
            else if (tab == table) {
                int rs = resizeStamp(n);
                // 说明此时有线程在执行扩容
                if (sc < 0) {
                    Node[] nt;
                    // 判断扩容是否结束或者并发扩容线程数是否已达最大值，如果是的话直接结束while循环
                    if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
                        sc == rs + MAX_RESIZERS || (nt = nextTable) == null ||
                        transferIndex <= 0)
                        break;
                    // 扩容未结束吗，用 CAS 将 sizeCtl 加 1，然后执行 transfer 方法，一起执行扩容
                    if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1))
                        transfer(tab, nt);
                }
                 // 如果集合还未处于扩容状态中，则进入扩容方法，并首先初始化 nextTab 数组，也就是新数组
                 //  调用 transfer 方法，此时 nextTab 参数为 null
                else if (U.compareAndSwapInt(this, SIZECTL, sc,
                                             (rs << RESIZE_STAMP_SHIFT) + 2))
                    transfer(tab, null);
            }
        }
    }

addCount(long x, int check)

添加到计数中，如果表太小并且尚未调整大小，则启动转移调整。如果已经调整大小，则在工作可用时帮助执行传输。转移后重新检查占用情况，以查看是否已经需要再次调整大小，因为调整大小滞后于添加。

baseCount基本计数器值，主要在没有争用时使用，但也可作为表初始化竞赛期间的后备。通过 CAS 更新。

counterCells计数单元表。当非空时，大小是 2 的幂。

private final void addCount(long x, int check) {
    CounterCell[] as; long b, s;
    // 首先if判断counterCells为空并且对当前map对象cas操作baseCount + x成功，就跳过if里的操作，
    // 因为都cas操作baseCount + x成功了，就不需要通过counterCells辅助了，简单明了
    if ((as = counterCells) != null || !U.compareAndSwapLong(this, BASECOUNT, b = baseCount, s = b + x)) {
        CounterCell a; long v; int m;
        boolean uncontended = true;
        //如果上面判断失败了，counterCells不为空 或者counterCells为空但cas失败了。
        //如果counterCells为空，直接执行fullAddCount。
        //如果不为空,判断当前线程在counterCells中的槽位是否为空，如果不为空，
        //对槽位中的CounterCell对象cas操作value加1，成功return,失败执行fullAddCount，如果槽位为空，直接执行fullAddCount
        if (as == null || (m = as.length - 1) < 0 ||
            (a = as[ThreadLocalRandom.getProbe() & m]) == null ||
            !(uncontended = U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x))) {
            fullAddCount(x, uncontended);
            return;
        }
        if (check <= 1)
            return;
        s = sumCount();
    }
    // check就是结点数量，有新元素加入成功才检查是否要扩容。
    if (check >= 0) {
        Node[] tab, nt; int n, sc;
        //s表示加入新元素后容量大小，计算已省略。
        //新容量大于当前扩容阈值并且小于最大扩容值才扩容，如果tab=null说明正在初始化，死循环等待初始化完成。
        while (s >= (long)(sc = sizeCtl) && (tab = table) != null && (n = tab.length) < MAXIMUM_CAPACITY) {
            int rs = resizeStamp(n);
            //sc<0表示已经有线程在进行扩容工作
            if (sc < 0) {
                //条件1：检查是对容量n的扩容，保证sizeCtl与n是一块修改好的
                //条件2与条件3：应该是进行sc的最小值或最大值判断。
                //条件4与条件5: 确保tranfer()中的nextTable相关初始化逻辑已走完。
                if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
                    sc == rs + MAX_RESIZERS || (nt = nextTable) == null ||
                    transferIndex <= 0)
                    break;
                //有新线程参与扩容则sizeCtl加1
                if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1))
                    transfer(tab, nt);
            }
            //没有线程在进行扩容，将sizeCtl的值改为(rs << RESIZE_STAMP_SHIFT) + 2).
            else if (U.compareAndSwapInt(this, SIZECTL, sc, (rs << RESIZE_STAMP_SHIFT) + 2))
                transfer(tab, null);
            s = sumCount();
        }
    }
}

fullAddCount(long x, boolean wasUncontended)

    // See LongAdder version for explanation
    private final void fullAddCount(long x, boolean wasUncontended) {
        int h;
        // 如果当前线程hash值==0，则重新生成一个hash值。当前线程生成的hash值不会改变
        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已经被初始化了
            if ((as = counterCells) != null && (n = as.length) > 0) {
                // 如果当前线程对应于counterCell数组中的槽位为空
                if ((a = as[(n - 1) & h]) == null) {
                    //如果没有其他线程操作对应counterCell数组中的槽位
                    if (cellsBusy == 0) {            // Try to attach new Cell
                        //counterCell数组中为空的槽位中创建一个CounterCell对象
                        CounterCell r = new CounterCell(x); // Optimistic create
                        //如果将cellsBusy成功修改成1,抢锁成功
                        if (cellsBusy == 0 &&
                            U.compareAndSwapInt(this, CELLSBUSY, 0, 1)) {
                            boolean created = false;
                            try {               // Recheck under lock
                                //再次校验有没有其他线程操作该数组槽位
                                CounterCell[] rs; int m, j;
                                if ((rs = counterCells) != null &&
                                    (m = rs.length) > 0 &&
                                    rs[j = (m - 1) & h] == null) {
                                    rs[j] = r;
                                    // 标记创建成功
                                    created = true;
                                }
                            } finally {
                                // 恢复标志位
                                cellsBusy = 0;
                            }
                            // 创建成功，则跳出for循环
                            if (created)
                                break;
                            continue;           // Slot is now non-empty
                        }
                    }
                    collide = false;
                }
                else if (!wasUncontended)       // CAS already known to fail
                    wasUncontended = true;      // Continue after rehash
                //如果当前线程对应槽位已经存在CounterCell元素了，就对value+x
                else if (U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x))
                    break;
                //不扩容条件
                else if (counterCells != as || n >= NCPU)
                    collide = false;            // At max size or stale
                // 准备扩容条件
                else if (!collide)
                    collide = true;
                // 一个线程循环两次，都没有加1成功的情况下，数组扩容 
                // 在collide = true的情况下，数组扩容
                else if (cellsBusy == 0 && U.compareAndSwapInt(this, CELLSBUSY, 0, 1)) {
                    try {
                        if (counterCells == as) {// Expand table unless stale
                            //扩展数组，长度变为两倍
                            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
                }
                // 当前线程重新生成的hash值
                h = ThreadLocalRandom.advanceProbe(h);
            }
            // 如果counterCells 没有被初始化，
            // cellsBusy==0表示没有其他线程在使用counterCells数组。
            else if (cellsBusy == 0 && counterCells == as &&
                     U.compareAndSwapInt(this, CELLSBUSY, 0, 1)) {
                boolean init = false;
                try {                           // Initialize table
                    // 初始化数组
                    if (counterCells == as) {
                        // 初始长度为2
                        CounterCell[] rs = new CounterCell[2];
                        rs[h & 1] = new CounterCell(x);
                        counterCells = rs;
                        init = true;
                    }
                } finally {
                    //表示当前线程已经操作完成该数组 恢复标记
                    cellsBusy = 0;
                }
                // 初始化成功 跳出for循环
                if (init)
                    break;
            }
            // 如果都不满足，则线程自旋去竞争baseCount和CounterCell
            else if (U.compareAndSwapLong(this, BASECOUNT, v = baseCount, v + x))
                break;                          // Fall back on using base
        }
    }

GET过程 get(Object key)

    public V get(Object key) {
        Node[] tab; Node e, p; int n, eh; K ek;
        // 计算key的hash
        int h = spread(key.hashCode());
        // 1.空数组或key对应的数组下标为null，直接返回null
        
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (e = tabAt(tab, (n - 1) & h)) != null) {
            // 在node数组非空的场景下,检查对应下标的Node的hash值是否一直
            if ((eh = e.hash) == h) {
                // 只要==和equals任一种判断方式相等，就返回value
                if ((ek = e.key) == key || (ek != null && key.equals(ek)))
                    return e.val;
            }
            // Node数组对应下标的Node的hash值小于0，采用有Node子类的查询具体实现，可以树，或者数据迁移中选择。
            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;
    }

Replace和Remove过程 replaceNode(Object key, V value, Object cv)

	// value 新值，cv 旧值
	final V replaceNode(Object key, V value, Object cv) {
        // 计算key的hash
        int hash = spread(key.hashCode());
        // 无限循环-遍历Node数组
        for (Node[] tab = table;;) {
            Node f; int n, i, fh;
            // Node数组为空，或Node数组对应下标Node为空 退出循环
            if (tab == null || (n = tab.length) == 0 ||
                (f = tabAt(tab, i = (n - 1) & hash)) == null)
                break;
            // Node数组对应的Node在进行迁移，尝试进行帮助迁移
            else if ((fh = f.hash) == MOVED)
                tab = helpTransfer(tab, f);
            else {
                V oldVal = null;
                boolean validated = false;
                // 对相应位置的Node上锁
                synchronized (f) {
                    if (tabAt(tab, i) == f) {
                        // hash>=0说明 按链表式查询
                        if (fh >= 0) {
                            validated = true;
                            for (Node e = f, pred = null;;) {
                                K ek;
                                if (e.hash == hash &&
                                    ((ek = e.key) == key ||
                                     (ek != null && key.equals(ek)))) {
                                    V ev = e.val;
                                    if (cv == null || cv == ev ||
                                        (ev != null && cv.equals(ev))) {
                                        oldVal = ev;
                                        if (value != null)
                                            e.val = value;
                                        else if (pred != null)
                                            pred.next = e.next;
                                        else
                                            setTabAt(tab, i, e.next);
                                    }
                                    break;
                                }
                                pred = e;
                                if ((e = e.next) == null)
                                    break;
                            }
                        }
                        // 是否为树结点，树的方式查询
                        else if (f instanceof TreeBin) {
                            validated = true;
                            TreeBin t = (TreeBin)f;
                            TreeNode 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)
                            addCount(-1L, -1);
                        return oldVal;
                    }
                    break;
                }
            }
        }
        return null;
    }

remove是特殊的replace

replaceNode(key, null, value)

其他 sizeCtl

在table也就是Node数组未初始化时：

==0：代表未指定集合大小
>0：代表经过计算之后，Node数组初始化的大小

初始化过程中：

-1：代表数组初始化进行中

初始化完成后：

=table.length * 0.75 ：代表扩容的阈值，容器元素个数到达此数值，触发扩容

扩容时：

MAX_RESIZERS = (1 << (32 - RESIZE_STAMP_BITS)) - 1;//1<<16 -1 最大的并发扩容线程数65535

正在扩容是用于记录当前扩容的并发线程数情况

高15位	低16位
容量n扩容标识	并行扩容线程数+1

结合resizeStamp(int n)方法，n代表集合的长度（Node数组的长度）。

static final int resizeStamp(int n) {
    	// Integer.numberOfLeadingZeros(n)用来计算n的二进制下，前面有几个0
        return Integer.numberOfLeadingZeros(n) | (1 << (RESIZE_STAMP_BITS - 1));
}

RESIZE_STAMP_BITS=16，假设n=16,

0000 0000 0000 0000 0000 0000 0001 0000  // 16的二进制
0000 0000 0000 0000 0000 0000 0001 1011  // Integer.numberOfLeadingZeros(16)=27
0000 0000 0000 0000 1000 0000 0000 0000  // (1 << (RESIZE_STAMP_BITS - 1)) 即 1<<15
0000 0000 0000 0000 1000 0000 0001 1011  // resizeStamp(16)即rs

// sc>0 代表尚未进入扩容状态
//第一个线程要扩容时，sc = (rs << RESIZE_STAMP_SHIFT) + 2)即 rs << 16 + 2。
1000 0000 0001 1011 0000 0000 0000 0010 
// 由于首位变成了1，即成为一个负数，开始扩容状态后 sc<0。 
// 1.sc >>> RESIZE_STAMP_SHIFT) != rs代表检查是对容量n的扩容，保证sizeCtl与n是一块修改好的
// 2.sc == rs + 1  不理解,sc 此时应该是负数 rs 是正数，按道理，应该永远不会相等 sc>>>16==rs+1
// 3.sc == rs + MAX_RESIZERS 不理解sc 此时应该是负数 rs 是正数，按道理，应该永远不会相等
// 4.(nt = nextTable) == null 需要扩容的数组已经为空
// 5.transferIndex <= 0 确保tranfer()中的nextTable相关初始化逻辑已走完。
//第二个线程要扩容时，sc = sc+1
1000 0000 0001 1011 0000 0000 0000 0011 
//一个线程要结束扩容时，sc = sc-1

对扩容线程个数线程的判断为啥要用

sc==rs+1

sc==rs+MAX_RESIZERS

不应该是

sc==(rs<<15)+1

sc==(rs<<15)+MAX_RESIZERS

1000 0000 0001 1011 0000 0000 0000 0001 这应该是说明最后一个扩容线程已经在执行了，其他线程无需加入了

1000 0000 0001 1011 0111 1111 1111 1111 扩容线程个数超过最大值了

【JUC系列】并发容器之ConcurrentHashMap(JDK1.8版)

Java相关栏目本月热门文章