ConcurrentHashMap源码设计分析之addCount

将数组中每个链表或红黑树称之为桶，将数组中的每个结点称之为槽
jdk1.7：1、segment分段锁设计，2、数组+链表
jdk1.8：1、取消分段锁，对每个桶进行加锁，2、数组+链表+红黑树（当链表长度大于8会变红黑树，当扩容后，红黑树节点小于8会转成链表）

初始化长度：DEFAULT_CAPACITY=16
扩容因子：0.75
sizeCtl大于n（数组长度）* 0.75时会进行扩容（例如当数组长度n为16时，如果有12个数组位都已经有数据时，再put第13个数组位时，会对数组进行扩容）
通过 (n - 1) & hash（数组长度与key的hash值做&运算）确定当前数据落在哪个槽点位置。

addCount源码分析：
addCount（元素个数++）多线程情况下是怎么实现的？（这里提供了一个多线程高并发场景下实现数字的高性能原子递增的处理方案）
addCount使用了一个分流的思想：先进行一次cas，cas成功则addCount成功，若cas失败就不去重试了，直接通过数组来处理，最终总数量是两者之和

    private final void addCount(long x, int check) {
        CounterCell[] as; long b, s;
        //分流
        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 ||
                //生成线程安全的随机数与数组长度做与运算，确定去哪个数组位置做value++操作
                (a = as[ThreadLocalRandom.getProbe() & m]) == null ||
                !(uncontended =
                  //数组处理，内部依然使用cas去++
                  U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x))) {
                fullAddCount(x, uncontended);
                return;
            }
            if (check <= 1)
                return;
            s = sumCount();
        }

为什么不都直接都用cas操作addCount：高并发场景下会导致大量无效的循环（例：1000个并发，只有一个cas成功，其他999个cas都是无效循环，会造成系统性能浪费）

CounterCell数组来记录个数（初始化数组长度为2，高并发情况可以扩容，每个数组节点分别记录落在当前数组的记录数，使用的是cas去操作value++，最后将所有节点的value求和，并加上baseCount的值，即为map元素个数。每次addCount，进入数组操作时会生成一个线程安全的随机数，通过随机数与数组长度做与运算，决定当前次++是去数组什么位置++）
CounterCell数组记录的好处：多个线程可以并发的去多个数组节点位置去做value++操作

扩容后数据是如何迁移的？
会通过&运算判断是否等于0，等于0的组成一个低位链ln，不等于0的组成一个高位链hn
然后低位链保存原有数组下标，不迁移，高位链所有数组下标加上n

                //链表的迁移代码段
                synchronized (f) {
                    if (tabAt(tab, i) == f) {
                        Node<K,V> ln, hn;
                        if (fh >= 0) {
                           //int n = tab.length, 判断是否等于0
                            int runBit = fh & n;
                            Node<K,V> lastRun = f;
                            for (Node<K,V> p = f.next; p != null; p = p.next) {
                                int b = p.hash & n;
                                if (b != runBit) {
                                    runBit = b;
                                    lastRun = p;
                                }
                            }
                           //等于0生成低位链
                            if (runBit == 0) {
                                ln = lastRun;
                                hn = null;
                            }
                            //不等于0生成高位链
                            else {
                                hn = lastRun;
                                ln = null;
                            }
                            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);
                            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;
                                }
                            }
                            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;
                            setTabAt(nextTab, i, ln);
                            setTabAt(nextTab, i + n, hn);
                            setTabAt(tab, i, fwd);
                            advance = true;
                        }
                    }
                }