CourrentHashMap的构造方法以及put函数和红黑树

总共有五种构造器，总结： 两个重要参数 initalCapacity 初始化容量；loadFactor 扩容的负载因子（用于计算扩容阈值）;默认初始化容量为16；默认负载因子为0.75。
一个BUG：一个参数构造器和三参构造器构造的集合对象长度不一致；一个参数的构造器即使在构造时，给定初始化容量是2的n次幂，结果也会被改变；在JDK12中得以修正。

public ConcurrentHashMap(int initialCapacity, float loadFactor, int concurrencyLevel) {
        
        if (!(loadFactor > 0.0f) || initialCapacity < 0 || concurrencyLevel <= 0)
                throw new IllegalArgumentException();
        // 如果初始化容量小于预计更新线程数，初始化容量就时更新线程数
        if (initialCapacity < concurrencyLevel)
                initialCapacity = concurrencyLevel;
        // 预计初始化集合的大小；1.0 保证不会等于0（因为初始化容量可以为0）
        long size = (long)(1.0 + (long)initialCapacity / loadFactor);
        
        int cap = (size >= (long)MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : tableSizeFor((int)size);
        // 将数组真正的初始化容量赋值给成员变量 sizeCtl
        this.sizeCtl = cap;
}

// 本质调用三参构造器
public ConcurrentHashMap(int initialCapacity, float loadFactor) {
        this(initialCapacity, loadFactor, 1);
}


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;
}


// 参数为Map对象，采用默认初始化容量，不足时再扩容
public ConcurrentHashMap(Map m) {
        // 默认初始化容量 16
        this.sizeCtl = DEFAULT_CAPACITY;
        // 容量不足时，会在putAll 中执行 tryPreSize 尝试扩容
        putAll(m);
}

// 无参构造器 什么都没做
public ConcurrentHashMap() {
}

put方法的执行过程
1、判断key，value值是否为空，为空抛出空指针异常；
2、判断集合数组是否初始化，未初始化进行初始化；
3、用key的hash值与数组长度做 & 运算得出索引位置：hash & (n -1),并判断索引位置的节点是否为空，为空采用CAS放入数据
4、索引位置不为空分为三种情况
4.1 数组正在扩容，数据在迁移中，索引位置的节点为forward节点，forward的节点特点hash值为-1，当前线程进行协助扩容

----- 4.2和4.3前置：所以位置不管是链表还是红黑树，都先加同步锁synchronized
4.2 索引位置为链表，遍历链表，查看链表是否有相同的key存在，
– 有相同的key根据onlyIfAbsent的值进行覆盖或者保持不变；
– 没有相同的key，找到链表尾部插入数据。
4.3 索引位置为红黑树，调用TreeBin.putTreeNode插入红黑树。
4.5 如果链表长度超过8，尝试树化。（不一定会转为红黑树，转为红黑树还有一个条件，数组长度 > 64)

注意：在ConcurrentHashMap中，hash值负数有特殊含义，与HashMap不同的地方在于计算hash值时，hash & HASH_BITS,保证正常的hash值是一个正数；
HASH_BITS = 0x7fffffff；
HASH_BITS = 011111111 11111111 11111111 11111；最高位为0，保证与hash值做 & 运算后，得到一个最高位为0的值。
当Hash值负数的三种情况：

当前位置正在进行扩容
static final int MOVED = -1;

当前位置下是一棵红黑树
static final int TREEBIN = -2;

预留当前位置 ====> computIfAbsent ====> new ReservationNode();
static final int RESERVED = -3;

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

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



final V putVal(K key, V value, boolean onlyIfAbsent) {
        // key和value都不允许为空，跟HashMap的区别
        if (key == null || value == null) throw new NullPointerException();
        
        int hash = spread(key.hashCode());
        int binCount = 0;

        for (Node[] tab = table;;) {
                
                Node f; int n, i, fh;
                // 判断数组是否初始化
                if (tab == null || (n = tab.length) == 0)
                        // 没有初始化，初始化数组
                        tab = initTable();
                
                else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
                        // 索引位置为空，则通过CAS插入数据
                        if (casTabAt(tab, i, null, new Node(hash, key, value, null)))
                                // 插入成功，跳出当前循环
                                break;
                }
                // 当前位置是否正在扩容
                else if ((fh = f.hash) == MOVED)
                        // 当前插入数据的线程协助扩容
                        tab = helpTransfer(tab, f);
                // 当前索引位置下有数据，分为两种情况，当前索引位置下是链表或者一颗红黑树
                else {
                        // 链表中当前节点的value
                        V oldVal = null;
                        // 基于当前索引位置的节点数据进行加锁，也就是常说的桶锁。
                        synchronized (f) {
                                // 再次判断当前位置引用是否变更，引用变更说明发生了并发冲突
                                if (tabAt(tab, i) == f) {
                                        //当前位置中是一个链表
                                        if (fh >= 0) {
                                                // 在链表中位置的索引，1表示链表第二个位置
                                                //（数组索引为i的节点为链表首节点 ==> 0）
                                                binCount = 1;
                                                for (Node e = f;; ++binCount) {
                                                        // 当前位置i下的链表位置为binCount位置的节点的key值。
                                                        K ek;
                                                        
                                                        if (e.hash == hash &&
                                                                        ((ek = e.key) == key ||
                                                                         (ek != null && key.equals(ek)))) {
                                                                // 将链表当前节点的value赋值给oldValue
                                                                oldVal = e.val;
                                                                
                                                                if (!onlyIfAbsent)
                                                                        e.val = value;
                                                                break;
                                                        }

                                                        Node pred = e;
                                                        // 找到链表尾部（链表尾部的next为空）
                                                        if ((e = e.next) == null) {
                                                                
                                                                pred.next = new Node(hash, key, value, null);
                                                                break;
                                                        }
                                                }
                                        }
                                        // 当前 i = hash & n -1 位置下是一颗红黑树
                                        else if (f instanceof TreeBin) {
                                                // 临时节点：用于接收插入红黑树后的返回值
                                                Node p;
                                                binCount = 2; 
                                                // 插入到当前节点下红黑树中（因为当前节点是红黑树节点，所以可以强转）
                                                // p 不为空，说明红黑树中有相同的key存在
                                                if ((p = ((TreeBin)f).putTreeVal(hash, key, value)) != null) {
                                                        // 获取要覆盖节点的原来的value
                                                        oldVal = p.val;
                                                        // 是否允许覆盖旧值
                                                        if (!onlyIfAbsent)
                                                                // 覆盖旧值
                                                                p.val = value;
                                                }
                                        }
                                }
                        }
                        if (binCount != 0) {
                                if (binCount >= TREEIFY_THRESHOLD)
                                        // 树化
                                        treeifyBin(tab, i);
                                if (oldVal != null)
                                        return oldVal;
                                break;
                        }
                }
        }
        addCount(1L, binCount);
        return null;
}

初始化数组的执行过程
1、while循环判断数组是否初始化，为空或者数组长度为空0，表示数组没有初始化
1.1、已经初始化直接返回当前数组
1.2、没有初始化，分为以下两种情况：
----- sizeCtl < 0，当前线程让步，进入就绪状态。
----- 否则，尝试设置 sizeCtl 为 -1，设置不成功继续while循环，设置成功，再次判断是数组引用是否变更，是否初始化。没有初始化进行初始化，并将sizeCtl设置为下次扩容的阈值。

sizeCtl > 0 表示数组的初始化长度或者扩容的阈值
sizeCtl = 0 表示是数组没有初始化
sizeCtl = -1 表示数组正在初始化
sizeCtl < -1 表示数组正在扩容的线程数，-2代表有一个线程扩容，以此类推

private final Node[] initTable() {
    // tab 当前数组，sc 当前sizeCtl的值
    Node[] tab; int sc;
    // 再次判断数组是否初始化
    while ((tab = table) == null || tab.length == 0) {
        
        // 判断数组是否正在初始化或者扩容
        if ((sc = sizeCtl) < 0)
            // 当前线程让步（让出CPU执行），进入就绪状态
            Thread.yield(); // lost initialization race; just spin
        // 线程以CAS的方式，设置sc的值为-1，只有一个线程能设置成功
        else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
            try {
                // 再次判断数组是否初始化
                if ((tab = table) == null || tab.length == 0) {
                    // 如果sc > 0 ,那么sc是数组初始化长度，否则数组长度为默认数组初始化长度==》16。
                    int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
                    // 真正开始初始化数组
                    Node[] nt = (Node[])new Node[n];
                    // 将初始化后的数组赋值给局部变量tab和全局变量table
                    table = tab = nt;
                    // 下次数组扩容的阈值 3/4 = 0.75
                    sc = n - (n >>> 2);
                }
            } finally {
                // 将sc （扩容阈值）赋值给全局变量sizeCtl
                sizeCtl = sc;
            }
            break;
        }
    }
    return tab;
}

final TreeNode putTreeVal(int h, K k, V v) {
    // key 的类对象
    Class kc = null;
    // 是否已经搜索过子节点
    boolean searched = false;
    // p 父节点的临时变量（for循环的起点是根节点）
    for (TreeNode p = root;;) {
        
        int dir, ph; K pk;
        // 如果父节点为空，说明树不存在
        if (p == null) {
            
            first = root = new TreeNode(h, k, v, null, null);
            break;
            // 如果父节点不为空，判断父节点hash 是否大于 当前插入节点的hash值
        } else if ((ph = p.hash) > h)
            // 如果父hash > hash,当前要插入的节点应该插入左子树
            dir = -1;
        else if (ph < h)
            // 如果父hash < hash,当前要插入的节点应该插入右子树
            dir = 1;
        // 如果当前插入key 与 父节点key引用地址相同 或者 key equals相等
        else if ((pk = p.key) == k || (pk != null && k.equals(pk)))
            // 说父节点的key与当前插入key相同，直接返回当前节点
            return p;
        
        else if ((kc == null && (kc = comparableClassFor(k)) == null) ||
                 (dir = compareComparables(kc, k, pk)) == 0) {
            // 只会搜索一次，搜索一次后 searched被赋值为true，表示搜索过了
            if (!searched) {
                TreeNode q, ch;
                searched = true;
                

                if (((ch = p.left) != null && (q = ch.findTreeNode(h, k, kc)) != null) ||
                        ((ch = p.right) != null && (q = ch.findTreeNode(h, k, kc)) != null))
                    return q;
            }
            // k hash值 <= pk的hash值 ? -1 : 1
            dir = tieBreakOrder(k, pk);
        }
        // 根据dir，判断放入左或右子树，并维护链表
        TreeNode xp = p;
        if ((p = (dir <= 0) ? p.left : p.right) == null) {
            // 将根节点赋值给临时变量f；x 当前节点的临时变量
            TreeNode x, f = first;
            // 将当前节点赋值给链表头节点
            first = x = new TreeNode(h, k, v, f, xp);
            // 如果根节点不为空，将当前节点赋值给根节点的prev（链表的上一个节点）
            if (f != null)
                f.prev = x;
            // 将当前节点放入父节点的左子树
            if (dir <= 0)
                xp.left = x;
            // 将当前节点放入父节点的左子树
            else
                xp.right = x;
            // 如果父节点不是红色，则当前节点为红色
            if (!xp.red)
                x.red = true;
            // 如果父节点是红色，则加锁，进行自平衡
            else {
                lockRoot();
                try {
                    root = balanceInsertion(root, x);
                } finally {
                    unlockRoot();
                }
            }
            break;
        }
    }
    // 检查红黑树
    assert checkInvariants(root);
    return null;
}

  
    static  TreeNode balanceInsertion(TreeNode root,
            TreeNode x) {
        // 默认插入节点时红色的
        x.red = true;
        
        for (TreeNode xp, xpp, xppl, xppr;;) {
            
            if ((xp = x.parent) == null) {
                x.red = false;
                return x;

                // 如果父节点是黑色的，或者爷爷节点是空，则说明不需要做自平衡，直接结束方法
            } else if (!xp.red || (xpp = xp.parent) == null)
                return root;

            // 左子树操作，当前节点的父节点位于左子树
            if (xp == (xppl = xpp.left)) {

                // 如果叔叔节点不为空，且是红色
                if ((xppr = xpp.right) != null && xppr.red) {
                    // 将叔叔节点，父节点都变为黑色；爷爷节点变为红色
                    xppr.red = false;
                    xp.red = false;
                    xpp.red = true;
                    // 将当前节点指向爷爷节点，再走一次循环（验证爷爷节点是否满足特性）
                    x = xpp;

                    // 叔叔节点为空或者是黑色的
                } else {
                    // 当前节点是位于父节点右边的节点
                    if (x == xp.right) {
                        // 父节点进行左旋操作
                        root = rotateLeft(root, x = xp);
                        // 判断父节点是否为空，为空，则爷爷节点为空；不为空，则爷爷节点是父节点的父节点
                        xpp = (xp = x.parent) == null ? null : xp.parent;
                    }
                    // 父节点不为空
                    if (xp != null) {
                        // 将父节点变为黑色
                        xp.red = false;
                        // 如果爷爷节点不为空，将爷爷节点变为红色，并将爷爷节点右旋
                        if (xpp != null) {
                            xpp.red = true;
                            root = rotateRight(root, xpp);
                        }
                    }
                }
                // 右子树操作，当前节点的父节点位于右子树（与左子树类似）
            } else {
                if (xppl != null && xppl.red) {
                    xppl.red = false;
                    xp.red = false;
                    xpp.red = true;
                    x = xpp;
                } else {
                    if (x == xp.left) {
                        root = rotateRight(root, x = xp);
                        xpp = (xp = x.parent) == null ? null : xp.parent;
                    }
                    if (xp != null) {
                        xp.red = false;
                        if (xpp != null) {
                            xpp.red = true;
                            root = rotateLeft(root, xpp);
                        }
                    }
                }
            }
        }
    }

左旋操作：

右旋操作：

TreeBin的锁操作，没有基于AQS，仅仅是对一个变量的CAS操作和一些业务判断实现的。

每次读线程操作，对lockState+4。

写线程操作，对lockState 设置为 1，如果读操作占用着线程，就先设置 lockState为 2，表示当前有写线程在等待写锁

// TreeBin的锁操作
// 如果说有读线程在读取红黑树的数据，这时，写线程要阻塞（做平衡前）
// 如果有写线程正在操作红黑树（做平衡），读线程不会阻塞，会读取双向链表
// 读读不会阻塞！
static final class TreeBin extends Node {
  
    // waiter：等待获取写锁的线程
    volatile Thread waiter;
    // lockState：当前TreeBin的锁状态
    volatile int lockState;
  
    // 对锁状态进行运算的值
    // 有线程拿着写锁
    static final int WRITER = 1; 
    // 有写线程，再等待获取写锁
    static final int WAITER = 2; 
    // 读线程，在红黑树中检索时，需要先对lockState + READER
    // 这个只会在读操作中遇到
    static final int READER = 4; 

    // 加锁-写锁
    private final void lockRoot() {
        // 将lockState从0设置为1，代表拿到写锁成功
        if (!U.compareAndSwapInt(this, LOCKSTATE, 0, WRITER))
            // 如果写锁没拿到，执行contendedLock
            contendedLock(); 
    }

    // 释放写锁
    private final void unlockRoot() {
        lockState = 0;
    }

  
    // 写线程没有拿到写锁，执行当前方法
    private final void contendedLock() {
        // 是否有线程正在等待
        boolean waiting = false;
        // 死循环，s是lockState的临时变量
        for (int s;;) {
            // 
            // lockState & 11111101 ,只要结果为0，说明当前写锁，和读锁都没线程获取
            if (((s = lockState) & ~WAITER) == 0) {
                // CAS一波，尝试将lockState再次修改为1，
                if (U.compareAndSwapInt(this, LOCKSTATE, s, WRITER)) {
                    // 成功拿到锁资源，并判断是否在waiting
                    if (waiting)
                        // 如果当前线程挂起过，直接将之前等待的线程资源设置为null
                        waiter = null;
                    return;
                }
            }
            // 有读操作在占用资源
            // lockState &  00000010,代表当前没有写操作挂起等待。
            else if ((s & WAITER) == 0) {
                // 基于CAS，将LOCKSTATE的第二位设置为1
                if (U.compareAndSwapInt(this, LOCKSTATE, s, s | WAITER)) {
                    // 如果成功，代表当前线程可以waiting等待了
                    waiting = true;
                    waiter = Thread.currentThread();
                }
            }
            else if (waiting)
                // 挂起当前线程！会由写操作唤醒
                LockSupport.park(this);
        }
    }
}