1.JDK1.7

数据结构：

• 分为两级数组，外面有一个Segment数组，大小与并发级别有关
• 每个Segment管理一个HashEntry数组

Segment锁机制：

• 比如put，在Segment里面put时，先要加锁tryLock()
• Segment继承了ReentrantLock
• tryLock()失败后，进入while(!tryLock)循环，创建HashEntry，自旋达到阈值后（64/1），直接lock()阻塞

哈希寻址：

• 第一步用来定位Segment位置，这里取的是高位
• 第二步用来定位Segment里面小数组的位置

扩容rehash()：

• 是Segment里面的数组进行扩容
• lastRun机制
  末尾放到同一个位置的连续链表；
  直接插入到新数组位置；
  移动：只用移动链表头到lastRun的元素。

get()：

• 首先定位Segment
• 其次定位HashEntry
• 最后遍历链表

size()：

• 第一次不加锁
• 第二次也不加锁，如果与第一次相等，则返回统计数值
• 第三次加锁统计（对所有segment都加锁）

2.JDK1.8

2.1 数据结构

基本数据结构是数组，发送哈希冲突时采用链表解决，如果数组大小达到64并且链表长度达到8，则转换为红黑树。

通过节点的hash值区分不同节点：

• ForwardingNode，扩容时被转移的节点，hash值是-1
• TreeBin，红黑树，hash值是-2
• 正常链表Node节点，会通过spread()后的，会跟0x7fffffff相与，是个大于0的数

2.1.1 数组大小

数组的大小为2的幂次方：返回>=c的最小的2的次方数

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

2.1.2 sizeCtl

• sizeCtl < 0
  1） -1 表示当前table正在初始化（有线程在创建table数组），当前线程需要自旋等待..
  2）表示当前table数组正在进行扩容 ,高16位表示：扩容的标识戳 低16位表示：（1 + nThread） 当前参与并发扩容的线程数量
• sizeCtl = 0，表示创建table数组时 使用DEFAULT_CAPACITY为大小
• sizeCtl > 0
  1）如果table未初始化，表示初始化大小
  2）如果table已经初始化，表示下次扩容时的 触发条件（阈值）

 /**
     * sizeCtl < 0
     * 1. -1 表示当前table正在初始化（有线程在创建table数组），当前线程需要自旋等待..
     * 2.表示当前table数组正在进行扩容 ,高16位表示：扩容的标识戳   低16位表示：（1 + nThread） 当前参与并发扩容的线程数量
     *
     * sizeCtl = 0，表示创建table数组时 使用DEFAULT_CAPACITY为大小
     *
     * sizeCtl > 0
     *
     * 1. 如果table未初始化，表示初始化大小
     * 2. 如果table已经初始化，表示下次扩容时的 触发条件（阈值）
     */
    private transient volatile int sizeCtl;

2.1.3 数组初始化

在put()中进行延迟初始化

    /**
     * Initializes table, using the size recorded in sizeCtl.
     *      * sizeCtl < 0
     *      * 1. -1 表示当前table正在初始化（有线程在创建table数组），当前线程需要自旋等待..
     *      * 2.表示当前table数组正在进行扩容 ,高16位表示：扩容的标识戳   低16位表示：（1 + nThread） 当前参与并发扩容的线程数量
     *      *
     *      * sizeCtl = 0，表示创建table数组时 使用DEFAULT_CAPACITY为大小
     *      *
     *      * sizeCtl > 0
     *      *
     *      * 1. 如果table未初始化，表示初始化大小
     *      * 2. 如果table已经初始化，表示下次扩容时的 触发条件（阈值）
     */
    private final Node<K,V>[] initTable() {
        //tab 引用map.table
        //sc sizeCtl的临时值
        Node<K,V>[] tab; int sc;
        //自旋 条件：map.table 尚未初始化
        while ((tab = table) == null || tab.length == 0) {

            if ((sc = sizeCtl) < 0)
                //大概率就是-1，表示其它线程正在进行创建table的过程，当前线程没有竞争到初始化table的锁。
                Thread.yield(); // lost initialization race; just spin

            //1.sizeCtl = 0，表示创建table数组时 使用DEFAULT_CAPACITY为大小
            //2.如果table未初始化，表示初始化大小
            //3.如果table已经初始化，表示下次扩容时的 触发条件（阈值）
            else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
                try {
                    //这里为什么又要判断呢？ 防止其它线程已经初始化完毕了，然后当前线程再次初始化..导致丢失数据。
                    //条件成立，说明其它线程都没有进入过这个if块，当前线程就是具备初始化table权利了。
                    if ((tab = table) == null || tab.length == 0) {

                        //sc大于0 创建table时 使用 sc为指定大小，否则使用 16 默认值.
                        int n = (sc > 0) ? sc : DEFAULT_CAPACITY;

                        @SuppressWarnings("unchecked")
                        Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
                        //最终赋值给 map.table
                        table = tab = nt;
                        //n >>> 2  => 等于 1/4 n     n - (1/4)n = 3/4 n => 0.75 * n
                        //sc 0.75 n 表示下一次扩容时的触发条件。
                        sc = n - (n >>> 2);
                    }
                } finally {
                    //1.如果当前线程是第一次创建map.table的线程话，sc表示的是 下一次扩容的阈值
                    //2.表示当前线程 并不是第一次创建map.table的线程，当前线程进入到else if 块 时，将
                    //sizeCtl 设置为了-1 ，那么这时需要将其修改为 进入时的值。
                    sizeCtl = sc;
                }
                break;
            }
        }
        return tab;
    }

2.1.4 TreeBin锁状态

1.写锁状态 写是独占状态，以散列表来看，真正进入到TreeBin中的写线程 同一时刻 只有一个线程。 1
2.读锁状态 读锁是共享，同一时刻可以有多个线程 同时进入到 TreeBin对象中获取数据。 每一个线程 都会给 lockStat + 4
3.等待者状态（写线程在等待），当TreeBin中有读线程目前正在读取数据时，写线程无法修改数据，那么就将lockState的最低2位 设置为 0b 10

        /**
         * 1.写锁状态 写是独占状态，以散列表来看，真正进入到TreeBin中的写线程 同一时刻 只有一个线程。 1
         * 2.读锁状态 读锁是共享，同一时刻可以有多个线程 同时进入到 TreeBin对象中获取数据。 每一个线程 都会给 lockStat + 4
         * 3.等待者状态（写线程在等待），当TreeBin中有读线程目前正在读取数据时，写线程无法修改数据，那么就将lockState的最低2位 设置为 0b 10
         */
        volatile int lockState;

2.2 get()

    public V get(Object key) {
        //tab 引用map.table
        //e 当前元素
        //p 目标节点
        //n table数组长度
        //eh 当前元素hash
        //ek 当前元素key
        Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
        //扰动运算后得到 更散列的hash值
        int h = spread(key.hashCode());

        //条件一：(tab = table) != null
        //true->表示已经put过数据，并且map内部的table也已经初始化完毕
        //false->表示创建完map后，并没有put过数据，map内部的table是延迟初始化的，只有第一次写数据时会触发创建逻辑。
        //条件二：(n = tab.length) > 0 true->表示table已经初始化
        //条件三：(e = tabAt(tab, (n - 1) & h)) != null
        //true->当前key寻址的桶位 有值
        //false->当前key寻址的桶位中是null，是null直接返回null
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (e = tabAt(tab, (n - 1) & h)) != null) {
            //前置条件：当前桶位有数据

            //对比头结点hash与查询key的hash是否一致
            //条件成立：说明头结点与查询Key的hash值 完全一致
            if ((eh = e.hash) == h) {
                //完全比对 查询key 和 头结点的key
                //条件成立：说明头结点就是查询数据
                if ((ek = e.key) == key || (ek != null && key.equals(ek)))
                    return e.val;
            }

            //条件成立：
            //1.-1  fwd 说明当前table正在扩容，且当前查询的这个桶位的数据 已经被迁移走了
            //2.-2  TreeBin节点，需要使用TreeBin 提供的find 方法查询。
            else if (eh < 0)
                return (p = e.find(h, key)) != null ? p.val : null;




            //当前桶位已经形成链表的这种情况
            while ((e = e.next) != null) {
                if (e.hash == h &&
                    ((ek = e.key) == key || (ek != null && key.equals(ek))))
                    return e.val;
            }

        }
        return null;
    }

这里对hash值进行了处理，使高位向低位融合，是为了得到更散列的hash值。

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

上面eh < 0，有两种情况：

• ForwardingNode，此时回去nextTable里面查找
• TreeBin，此时获取红黑树查找（这里尝试加读锁进行树查找，如果没加成功，则进行链表查找）

ForwardingNode#find

        Node<K,V> find(int h, Object k) {
            // loop to avoid arbitrarily deep recursion on forwarding nodes
            //tab 一定不为空
            Node<K,V>[] tab = nextTable;
            outer: for (;;) {
                //n 表示为扩容而创建的 新表的长度
                //e 表示在扩容而创建新表使用 寻址算法 得到的 桶位头结点
                Node<K,V> e; int n;

                //条件一：永远不成立
                //条件二：永远不成立
                //条件三：永远不成立
                //条件四：在新扩容表中 重新定位 hash 对应的头结点
                //true -> 1.在oldTable中 对应的桶位在迁移之前就是null
                //        2.扩容完成后，有其它写线程，将此桶位设置为了null
                if (k == null || tab == null || (n = tab.length) == 0 ||
                    (e = tabAt(tab, (n - 1) & h)) == null)
                    return null;

                //前置条件：扩容后的表 对应hash的桶位一定不是null，e为此桶位的头结点
                //e可能为哪些node类型？
                //1.node 类型
                //2.TreeBin 类型
                //3.FWD 类型

                for (;;) {
                    //eh 新扩容后表指定桶位的当前节点的hash
                    //ek 新扩容后表指定桶位的当前节点的key
                    int eh; K ek;
                    //条件成立：说明新扩容 后的表，当前命中桶位中的数据，即为 查询想要数据。
                    if ((eh = e.hash) == h &&
                        ((ek = e.key) == k || (ek != null && k.equals(ek))))
                        return e;

                    //eh<0
                    //1.TreeBin 类型    2.FWD类型（新扩容的表，在并发很大的情况下，可能在此方法 再次拿到FWD类型..）
                    if (eh < 0) {
                        if (e instanceof ForwardingNode) {
                            tab = ((ForwardingNode<K,V>)e).nextTable;
                            continue outer;
                        }
                        else
                            //说明此桶位 为 TreeBin 节点，使用TreeBin.find 查找红黑树中相应节点。
                            return e.find(h, k);
                    }

                    //前置条件：当前桶位头结点 并没有命中查询，说明此桶位是 链表
                    //1.将当前元素 指向链表的下一个元素
                    //2.判断当前元素的下一个位置 是否为空
                    //   true->说明迭代到链表末尾，未找到对应的数据，返回Null
                    if ((e = e.next) == null)
                        return null;
                }
            }
        }
    }

        /**
         * Returns matching node or null if none. Tries to search
         * using tree comparisons from root, but continues linear
         * search when lock not available.
         */
        final Node<K,V> find(int h, Object k) {
            if (k != null) {

                //e 表示循环迭代的当前节点   迭代的是first引用的链表
                for (Node<K,V> e = first; e != null; ) {
                    //s 保存的是lock临时状态
                    //ek 链表当前节点 的key
                    int s; K ek;


                    //(WAITER|WRITER) => 0010 | 0001 => 0011
                    //lockState & 0011 != 0 条件成立：说明当前TreeBin 有等待者线程 或者 目前有写操作线程正在加锁
                    if (((s = lockState) & (WAITER|WRITER)) != 0) {
                        if (e.hash == h &&
                            ((ek = e.key) == k || (ek != null && k.equals(ek))))
                            return e;
                        e = e.next;
                    }

                    //前置条件：当前TreeBin中 等待者线程 或者 写线程 都没有
                    //条件成立：说明添加读锁成功
                    else if (U.compareAndSwapInt(this, LOCKSTATE, s,
                                                 s + READER)) {
                        TreeNode<K,V> r, p;
                        try {
                            //查询操作
                            p = ((r = root) == null ? null :
                                 r.findTreeNode(h, k, null));
                        } finally {
                            //w 表示等待者线程
                            Thread w;
                            //U.getAndAddInt(this, LOCKSTATE, -READER) == (READER|WAITER)
                            //1.当前线程查询红黑树结束，释放当前线程的读锁 就是让 lockstate 值 - 4
                            //(READER|WAITER) = 0110 => 表示当前只有一个线程在读，且“有一个线程在等待”
                            //当前读线程为 TreeBin中的最后一个读线程。

                            //2.(w = waiter) != null 说明有一个写线程在等待读操作全部结束。
                            if (U.getAndAddInt(this, LOCKSTATE, -READER) ==
                                (READER|WAITER) && (w = waiter) != null)
                                //使用unpark 让 写线程 恢复运行状态。
                                LockSupport.unpark(w);
                        }
                        return p;
                    }
                }
            }
            return null;
        }

2.3 put()

binCount的含义：

• binCount表示当前k-v 封装成node后插入到指定桶位后，在桶位中的所属链表的下标位置（两种情况：1.当前插入key与链表当中所有元素的key都不一致时，当前的插入操作是追加到链表的末尾，binCount表示链表长度；2.当前插入key与链表当中的某个元素的key一致时，当前插入操作可能就是替换了。binCount表示冲突位置（binCount - 1））
• 0表示当前桶位为null，node可以直接放着
• 2表示当前桶位已经可能是红黑树

总体来说分为几种情况：

• CASE1：当前map中的table尚未初始化
• CASE2：定位的桶位（槽位）为null。i 表示key使用路由寻址算法得到 key对应 table数组的下标位置，tabAt 获取指定桶位的头结点 f
• CASE3：前置条件，桶位的头结点一定不是null。当前桶位的头结点 为 FWD结点，表示目前map正处于扩容过程中..
• CASE4：当前桶位 可能是 链表 也可能是 红黑树代理结点TreeBin

    final V putVal(K key, V value, boolean onlyIfAbsent) {
        //控制k 和 v 不能为null
        if (key == null || value == null) throw new NullPointerException();

        //通过spread方法，可以让高位也能参与进寻址运算。
        int hash = spread(key.hashCode());
        //binCount表示当前k-v 封装成node后插入到指定桶位后，在桶位中的所属链表的下标位置
        //0 表示当前桶位为null，node可以直接放着
        //2 表示当前桶位已经可能是红黑树
        int binCount = 0;

        //tab 引用map对象的table
        //自旋
        for (Node<K,V>[] tab = table;;) {
            //f 表示桶位的头结点
            //n 表示散列表数组的长度
            //i 表示key通过寻址计算后，得到的桶位下标
            //fh 表示桶位头结点的hash值
            Node<K,V> f; int n, i, fh;

            //CASE1：成立，表示当前map中的table尚未初始化..
            if (tab == null || (n = tab.length) == 0)
                //最终当前线程都会获取到最新的map.table引用。
                tab = initTable();
            //CASE2：i 表示key使用路由寻址算法得到 key对应 table数组的下标位置，tabAt 获取指定桶位的头结点 f
            else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
                //进入到CASE2代码块 前置条件 当前table数组i桶位是Null时。
                //使用CAS方式 设置 指定数组i桶位 为 new Node<K,V>(hash, key, value, null),并且期望值是null
                //cas操作成功 表示ok，直接break for循环即可
                //cas操作失败，表示在当前线程之前，有其它线程先你一步向指定i桶位设置值了。
                //当前线程只能再次自旋，去走其它逻辑。
                if (casTabAt(tab, i, null,
                             new Node<K,V>(hash, key, value, null)))
                    break;                   // no lock when adding to empty bin
            }

            //CASE3：前置条件，桶位的头结点一定不是null。
            //条件成立表示当前桶位的头结点 为 FWD结点，表示目前map正处于扩容过程中..
            else if ((fh = f.hash) == MOVED)
                //看到fwd节点后，当前节点有义务帮助当前map对象完成迁移数据的工作
                //学完扩容后再来看。
                tab = helpTransfer(tab, f);

            //CASE4：当前桶位 可能是 链表 也可能是 红黑树代理结点TreeBin
            else {
                //当插入key存在时，会将旧值赋值给oldVal，返回给put方法调用处..
                V oldVal = null;

                //使用sync 加锁“头节点”，理论上是“头结点”
                synchronized (f) {
                    //为什么又要对比一下，看看当前桶位的头节点 是否为 之前获取的头结点？
                    //为了避免其它线程将该桶位的头结点修改掉，导致当前线程从sync 加锁 就有问题了。之后所有操作都不用在做了。
                    if (tabAt(tab, i) == f) {//条件成立，说明咱们 加锁 的对象没有问题，可以进来造了！

                        //条件成立，说明当前桶位就是普通链表桶位。
                        if (fh >= 0) {
                            //1.当前插入key与链表当中所有元素的key都不一致时，当前的插入操作是追加到链表的末尾，binCount表示链表长度
                            //2.当前插入key与链表当中的某个元素的key一致时，当前插入操作可能就是替换了。binCount表示冲突位置（binCount - 1）
                            binCount = 1;

                            //迭代循环当前桶位的链表，e是每次循环处理节点。
                            for (Node<K,V> e = f;; ++binCount) {
                                //当前循环节点 key
                                K ek;
                                //条件一：e.hash == hash 成立 表示循环的当前元素的hash值与插入节点的hash值一致，需要进一步判断
                                //条件二：((ek = e.key) == key ||(ek != null && key.equals(ek)))
                                //       成立：说明循环的当前节点与插入节点的key一致，发生冲突了
                                if (e.hash == hash &&
                                    ((ek = e.key) == key ||
                                     (ek != null && key.equals(ek)))) {
                                    //将当前循环的元素的 值 赋值给oldVal
                                    oldVal = e.val;

                                    if (!onlyIfAbsent)
                                        e.val = value;
                                    break;
                                }
                                //当前元素 与 插入元素的key不一致 时，会走下面程序。
                                //1.更新循环处理节点为 当前节点的下一个节点
                                //2.判断下一个节点是否为null，如果是null，说明当前节点已经是队尾了，插入数据需要追加到队尾节点的后面。

                                Node<K,V> pred = e;
                                if ((e = e.next) == null) {
                                    pred.next = new Node<K,V>(hash, key,
                                                              value, null);
                                    break;
                                }
                            }
                        }
                        //前置条件，该桶位一定不是链表
                        //条件成立，表示当前桶位是 红黑树代理结点TreeBin
                        else if (f instanceof TreeBin) {
                            //p 表示红黑树中如果与你插入节点的key 有冲突节点的话 ，则putTreeVal 方法 会返回冲突节点的引用。
                            Node<K,V> p;
                            //强制设置binCount为2，因为binCount <= 1 时有其它含义，所以这里设置为了2 回头讲 addCount。
                            binCount = 2;

                            //条件一：成立，说明当前插入节点的key与红黑树中的某个节点的key一致，冲突了
                            if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
                                                           value)) != null) {
                                //将冲突节点的值 赋值给 oldVal
                                oldVal = p.val;
                                if (!onlyIfAbsent)
                                    p.val = value;
                            }
                        }
                    }
                }

                //说明当前桶位不为null，可能是红黑树 也可能是链表
                if (binCount != 0) {
                    //如果binCount>=8 表示处理的桶位一定是链表
                    if (binCount >= TREEIFY_THRESHOLD)
                        //调用转化链表为红黑树的方法
                        treeifyBin(tab, i);
                    //说明当前线程插入的数据key，与原有k-v发生冲突，需要将原数据v返回给调用者。
                    if (oldVal != null)
                        return oldVal;
                    break;
                }
            }
        }

        //1.统计当前table一共有多少数据
        //2.判断是否达到扩容阈值标准，触发扩容。
        addCount(1L, binCount);

        return null;
    }

2.4 addCount()

这里的核心是sizeCtl：表示当前table数组正在进行扩容 ,高16位表示：扩容的标识戳 低16位表示：（1 + nThread） 当前参与并发扩容的线程数量

                    if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
                        sc == rs + MAX_RESIZERS || (nt = nextTable) == null ||
                        transferIndex <= 0)
                        break;

上面这个条件代码有一个bug：

• 条件二： JDK1.8 中有bug jira已经提出来了 其实想表达的是 = sc == (rs << 16 ) + 1
  true-> 表示扩容完毕，当前线程不需要再参与进来了
  false->扩容还在进行中，当前线程可以参与
• 条件三：JDK1.8 中有bug jira已经提出来了 其实想表达的是 = sc == (rs<<16) + MAX_RESIZERS
  true-> 表示当前参与并发扩容的线程达到了最大值 65535 - 1
  false->表示当前线程可以参与进来

    private final void addCount(long x, int check) {
        //as 表示 LongAdder.cells
        //b 表示LongAdder.base
        //s 表示当前map.table中元素的数量
        CounterCell[] as; long b, s;
        //条件一：true->表示cells已经初始化了，当前线程应该去使用hash寻址找到合适的cell 去累加数据
        //       false->表示当前线程应该将数据累加到 base
        //条件二：false->表示写base成功，数据累加到base中了，当前竞争不激烈，不需要创建cells
        //       true->表示写base失败，与其他线程在base上发生了竞争，当前线程应该去尝试创建cells。
        if ((as = counterCells) != null ||
            !U.compareAndSwapLong(this, BASECOUNT, b = baseCount, s = b + x)) {
            //有几种情况进入到if块中？
            //1.true->表示cells已经初始化了，当前线程应该去使用hash寻址找到合适的cell 去累加数据
            //2.true->表示写base失败，与其他线程在base上发生了竞争，当前线程应该去尝试创建cells。

            //a 表示当前线程hash寻址命中的cell
            CounterCell a;
            //v 表示当前线程写cell时的期望值
            long v;
            //m 表示当前cells数组的长度
            int m;
            //true -> 未竞争  false->发生竞争
            boolean uncontended = true;


            //条件一：as == null || (m = as.length - 1) < 0
            //true-> 表示当前线程是通过 写base竞争失败 然后进入的if块，就需要调用fullAddCount方法去扩容 或者 重试.. LongAdder.longAccumulate
            //条件二：a = as[ThreadLocalRandom.getProbe() & m]) == null   前置条件：cells已经初始化了
            //true->表示当前线程命中的cell表格是个空，需要当前线程进入fullAddCount方法去初始化 cell，放入当前位置.
            //条件三：!(uncontended = U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x)
            //      false->取反得到false，表示当前线程使用cas方式更新当前命中的cell成功
            //      true->取反得到true,表示当前线程使用cas方式更新当前命中的cell失败，需要进入fullAddCount进行重试 或者 扩容 cells。
            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);
                //考虑到fullAddCount里面的事情比较累，就让当前线程 不参与到 扩容相关的逻辑了，直接返回到调用点。
                return;
            }

            if (check <= 1)
                return;

            //获取当前散列表元素个数，这是一个期望值
            s = sumCount();
        }

        //表示一定是一个put操作调用的addCount
        if (check >= 0) {
            //tab 表示map.table
            //nt 表示map.nextTable
            //n 表示map.table数组的长度
            //sc 表示sizeCtl的临时值
            Node<K,V>[] tab, nt; int n, sc;


            /**
             * sizeCtl < 0
             * 1. -1 表示当前table正在初始化（有线程在创建table数组），当前线程需要自旋等待..
             * 2.表示当前table数组正在进行扩容 ,高16位表示：扩容的标识戳   低16位表示：（1 + nThread） 当前参与并发扩容的线程数量
             *
             * sizeCtl = 0，表示创建table数组时 使用DEFAULT_CAPACITY为大小
             *
             * sizeCtl > 0
             *
             * 1. 如果table未初始化，表示初始化大小
             * 2. 如果table已经初始化，表示下次扩容时的 触发条件（阈值）
             */

            //自旋
            //条件一：s >= (long)(sc = sizeCtl)
            //       true-> 1.当前sizeCtl为一个负数 表示正在扩容中..
            //              2.当前sizeCtl是一个正数，表示扩容阈值
            //       false-> 表示当前table尚未达到扩容条件
            //条件二：(tab = table) != null
            //       恒成立 true
            //条件三：(n = tab.length) < MAXIMUM_CAPACITY
            //       true->当前table长度小于最大值限制，则可以进行扩容。
            while (s >= (long)(sc = sizeCtl) && (tab = table) != null &&
                   (n = tab.length) < MAXIMUM_CAPACITY) {

                //扩容批次唯一标识戳
                //16 -> 32 扩容 标识为：1000 0000 0001 1011
                int rs = resizeStamp(n);

                //条件成立：表示当前table正在扩容
                //         当前线程理论上应该协助table完成扩容
                if (sc < 0) {
                    //条件一：(sc >>> RESIZE_STAMP_SHIFT) != rs
                    //      true->说明当前线程获取到的扩容唯一标识戳 非 本批次扩容
                    //      false->说明当前线程获取到的扩容唯一标识戳 是 本批次扩容
                    //条件二： JDK1.8 中有bug jira已经提出来了 其实想表达的是 =  sc == (rs << 16 ) + 1
                    //        true-> 表示扩容完毕，当前线程不需要再参与进来了
                    //        false->扩容还在进行中，当前线程可以参与
                    //条件三：JDK1.8 中有bug jira已经提出来了 其实想表达的是 = sc == (rs<<16) + MAX_RESIZERS
                    //        true-> 表示当前参与并发扩容的线程达到了最大值 65535 - 1
                    //        false->表示当前线程可以参与进来
                    //条件四：(nt = nextTable) == null
                    //        true->表示本次扩容结束
                    //        false->扩容正在进行中
                    if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
                        sc == rs + MAX_RESIZERS || (nt = nextTable) == null ||
                        transferIndex <= 0)
                        break;

                    //前置条件：当前table正在执行扩容中.. 当前线程有机会参与进扩容。
                    //条件成立：说明当前线程成功参与到扩容任务中，并且将sc低16位值加1，表示多了一个线程参与工作
                    //条件失败：1.当前有很多线程都在此处尝试修改sizeCtl，有其它一个线程修改成功了，导致你的sc期望值与内存中的值不一致 修改失败
                    //        2.transfer 任务内部的线程也修改了sizeCtl。
                    if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1))
                        //协助扩容线程，持有nextTable参数
                        transfer(tab, nt);
                }
                //1000 0000 0001 1011 0000 0000 0000 0000 +2 => 1000 0000 0001 1011 0000 0000 0000 0010
                //条件成立，说明当前线程是触发扩容的第一个线程，在transfer方法需要做一些扩容准备工作
                else if (U.compareAndSwapInt(this, SIZECTL, sc,
                                             (rs << RESIZE_STAMP_SHIFT) + 2))
                    //触发扩容条件的线程 不持有nextTable
                    transfer(tab, null);
                s = sumCount();
            }
        }
    }

2.5 扩容

    final Node<K,V>[] helpTransfer(Node<K,V>[] tab, Node<K,V> f) {
        //nextTab 引用的是 fwd.nextTable == map.nextTable 理论上是这样。
        //sc 保存map.sizeCtl
        Node<K,V>[] nextTab; int sc;

        //条件一：tab != null 恒成立 true
        //条件二：(f instanceof ForwardingNode) 恒成立 true
        //条件三：((ForwardingNode<K,V>)f).nextTable) != null 恒成立 true
        if (tab != null && (f instanceof ForwardingNode) &&
            (nextTab = ((ForwardingNode<K,V>)f).nextTable) != null) {

            //拿当前标的长度 获取 扩容标识戳   假设 16 -> 32 扩容：1000 0000 0001 1011
            int rs = resizeStamp(tab.length);

            //条件一：nextTab == nextTable
            //成立：表示当前扩容正在进行中
            //不成立：1.nextTable被设置为Null 了，扩容完毕后，会被设为Null
            //       2.再次出发扩容了...咱们拿到的nextTab 也已经过期了...
            //条件二：table == tab
            //成立：说明 扩容正在进行中，还未完成
            //不成立：说明扩容已经结束了，扩容结束之后，最后退出的线程 会设置 nextTable 为 table

            //条件三：(sc = sizeCtl) < 0
            //成立：说明扩容正在进行中
            //不成立：说明sizeCtl当前是一个大于0的数，此时代表下次扩容的阈值，当前扩容已经结束。
            while (nextTab == nextTable && table == tab &&
                   (sc = sizeCtl) < 0) {


                //条件一：(sc >>> RESIZE_STAMP_SHIFT) != rs
                //      true->说明当前线程获取到的扩容唯一标识戳 非 本批次扩容
                //      false->说明当前线程获取到的扩容唯一标识戳 是 本批次扩容
                //条件二： JDK1.8 中有bug jira已经提出来了 其实想表达的是 =  sc == (rs << 16 ) + 1
                //        true-> 表示扩容完毕，当前线程不需要再参与进来了
                //        false->扩容还在进行中，当前线程可以参与
                //条件三：JDK1.8 中有bug jira已经提出来了 其实想表达的是 = sc == (rs<<16) + MAX_RESIZERS
                //        true-> 表示当前参与并发扩容的线程达到了最大值 65535 - 1
                //        false->表示当前线程可以参与进来
                //条件四：transferIndex <= 0
                //      true->说明map对象全局范围内的任务已经分配完了，当前线程进去也没活干..
                //      false->还有任务可以分配。
                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;
    }

核心扩容方法，核心分为两大步骤：

• 1）给当前线程分配任务区间；维护当前线程任务进度（i 表示当前处理的桶位）；维护map对象全局范围内的进度transferIndex
• 2）迁移自己负责的任务区间：链表和红黑树

    private final void transfer(Node<K,V>[] tab, Node<K,V>[] nextTab) {
        //n 表示扩容之前table数组的长度
        //stride 表示分配给线程任务的步长
        int n = tab.length, stride;
        //方便讲解源码  stride 固定为 16
        if ((stride = (NCPU > 1) ? (n >>> 3) / NCPU : n) < MIN_TRANSFER_STRIDE)
            stride = MIN_TRANSFER_STRIDE; // subdivide range


        //条件成立：表示当前线程为触发本次扩容的线程，需要做一些扩容准备工作
        //条件不成立：表示当前线程是协助扩容的线程..
        if (nextTab == null) {            // initiating
            try {
                //创建了一个比扩容之前大一倍的table
                @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 ，方便协助扩容线程 拿到新表
            nextTable = nextTab;
            //记录迁移数据整体位置的一个标记。index计数是从1开始计算的。
            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

        //i 表示分配给当前线程任务，执行到的桶位
        //bound 表示分配给当前线程任务的下界限制
        int i = 0, bound = 0;
        //自旋
        for (;;) {
            //f 桶位的头结点
            //fh 头结点的hash
            Node<K,V> f; int fh;


            /**
             * 1.给当前线程分配任务区间
             * 2.维护当前线程任务进度（i 表示当前处理的桶位）
             * 3.维护map对象全局范围内的进度
             */
            while (advance) {
                //分配任务的开始下标
                //分配任务的结束下标
                int nextIndex, nextBound;

                //CASE1:
                //条件一：--i >= bound
                //成立：表示当前线程的任务尚未完成，还有相应的区间的桶位要处理，--i 就让当前线程处理下一个 桶位.
                //不成立：表示当前线程任务已完成 或 者未分配
                if (--i >= bound || finishing)
                    advance = false;
                //CASE2:
                //前置条件：当前线程任务已完成 或 者未分配
                //条件成立：表示对象全局范围内的桶位都分配完毕了，没有区间可分配了，设置当前线程的i变量为-1 跳出循环后，执行退出迁移任务相关的程序
                //条件不成立：表示对象全局范围内的桶位尚未分配完毕，还有区间可分配
                else if ((nextIndex = transferIndex) <= 0) {
                    i = -1;
                    advance = false;
                }
                //CASE3:
                //前置条件：1、当前线程需要分配任务区间  2.全局范围内还有桶位尚未迁移
                //条件成立：说明给当前线程分配任务成功
                //条件失败：说明分配给当前线程失败，应该是和其它线程发生了竞争吧
                else if (U.compareAndSwapInt
                         (this, TRANSFERINDEX, nextIndex,
                          nextBound = (nextIndex > stride ?
                                       nextIndex - stride : 0))) {

                    bound = nextBound;
                    i = nextIndex - 1;
                    advance = false;
                }
            }

            //CASE1：
            //条件一：i < 0
            //成立：表示当前线程未分配到任务
            if (i < 0 || i >= n || i + n >= nextn) {
                //保存sizeCtl 的变量
                int sc;
                if (finishing) {
                    nextTable = null;
                    table = nextTab;
                    sizeCtl = (n << 1) - (n >>> 1);
                    return;
                }

                //条件成立：说明设置sizeCtl 低16位  -1 成功，当前线程可以正常退出
                if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, sc - 1)) {
                    //1000 0000 0001 1011 0000 0000 0000 0000
                    //条件成立：说明当前线程不是最后一个退出transfer任务的线程
                    if ((sc - 2) != resizeStamp(n) << RESIZE_STAMP_SHIFT)
                        //正常退出
                        return;

                    finishing = advance = true;
                    i = n; // recheck before commit
                }
            }
            //前置条件：【CASE2~CASE4】 当前线程任务尚未处理完，正在进行中

            //CASE2:
            //条件成立：说明当前桶位未存放数据，只需要将此处设置为fwd节点即可。
            else if ((f = tabAt(tab, i)) == null)
                advance = casTabAt(tab, i, null, fwd);
            //CASE3:
            //条件成立：说明当前桶位已经迁移过了，当前线程不用再处理了，直接再次更新当前线程任务索引，再次处理下一个桶位 或者 其它操作
            else if ((fh = f.hash) == MOVED)
                advance = true; // already processed
            //CASE4:
            //前置条件：当前桶位有数据，而且node节点 不是 fwd节点，说明这些数据需要迁移。
            else {
                //sync 加锁当前桶位的头结点
                synchronized (f) {
                    //防止在你加锁头对象之前，当前桶位的头对象被其它写线程修改过，导致你目前加锁对象错误...
                    if (tabAt(tab, i) == f) {
                        //ln 表示低位链表引用
                        //hn 表示高位链表引用
                        Node<K,V> ln, hn;

                        //条件成立：表示当前桶位是链表桶位
                        if (fh >= 0) {


                            //lastRun
                            //可以获取出 当前链表 末尾连续高位不变的 node
                            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;
                                }
                            }

                            //条件成立：说明lastRun引用的链表为 低位链表，那么就让 ln 指向 低位链表
                            if (runBit == 0) {
                                ln = lastRun;
                                hn = null;
                            }
                            //否则，说明lastRun引用的链表为 高位链表，就让 hn 指向 高位链表
                            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;
                        }
                        //条件成立：表示当前桶位是 红黑树 代理结点TreeBin
                        else if (f instanceof TreeBin) {
                            //转换头结点为 treeBin引用 t
                            TreeBin<K,V> t = (TreeBin<K,V>)f;

                            //低位双向链表 lo 指向低位链表的头  loTail 指向低位链表的尾巴
                            TreeNode<K,V> lo = null, loTail = null;
                            //高位双向链表 lo 指向高位链表的头  loTail 指向高位链表的尾巴
                            TreeNode<K,V> hi = null, hiTail = null;


                            //lc 表示低位链表元素数量
                            //hc 表示高位链表元素数量
                            int lc = 0, hc = 0;

                            //迭代TreeBin中的双向链表，从头结点 至 尾节点
                            for (Node<K,V> e = t.first; e != null; e = e.next) {
                                // h 表示循环处理当前元素的 hash
                                int h = e.hash;
                                //使用当前节点 构建出来的 新的 TreeNode
                                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;
                                    //将低位链表尾指针指向 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;
                        }
                    }
                }
            }
        }
    }

2.6 remove()

这里最后有一个红黑树删除节点，然后调用untreeify操作

 else if (t.removeTreeNode(p))
     setTabAt(tab, i, untreeify(t.first));

可以从removeTreeNode方法中看到，一般情况下，其返回的false，只有当树节点很少时，才会返回true。

            if (first == null) {
                root = null;
                return true;
            }
            if ((r = root) == null || r.right == null || // too small
                (rl = r.left) == null || rl.left == null)
                return true;

这里红黑树的删除，首先是从双向链表中删除，然后才是从红黑树中删除。如果节点较少，直接从双向链表删除就返回，然后红黑树节点也不删除。然后untreeify操作直接遍历的就是双向链表，自然而然就是删除节点后的样子，这里代码设计的操作非常精简。

    public V remove(Object key) {
        return replaceNode(key, null, null);
    }

    final V replaceNode(Object key, V value, Object cv) {
        //计算key经过扰动运算后的hash
        int hash = spread(key.hashCode());
        //自旋
        for (Node<K,V>[] tab = table;;) {
            //f表示桶位头结点
            //n表示当前table数组长度
            //i表示hash命中桶位下标
            //fh表示桶位头结点 hash
            Node<K,V> f; int n, i, fh;

            //CASE1：
            //条件一：tab == null  true->表示当前map.table尚未初始化..  false->已经初始化
            //条件二：(n = tab.length) == 0  true->表示当前map.table尚未初始化..  false->已经初始化
            //条件三：(f = tabAt(tab, i = (n - 1) & hash)) == null true -> 表示命中桶位中为null，直接break， 会返回
            if (tab == null || (n = tab.length) == 0 ||
                (f = tabAt(tab, i = (n - 1) & hash)) == null)
                break;

            //CASE2：
            //前置条件CASE2 ~ CASE3：当前桶位不是null
            //条件成立：说明当前table正在扩容中，当前是个写操作，所以当前线程需要协助table完成扩容。
            else if ((fh = f.hash) == MOVED)
                tab = helpTransfer(tab, f);

            //CASE3:
            //前置条件CASE2 ~ CASE3：当前桶位不是null
            //当前桶位 可能是 "链表" 也可能 是  "红黑树" TreeBin
            else {
                //保留替换之前的数据引用
                V oldVal = null;
                //校验标记
                boolean validated = false;
                //加锁当前桶位 头结点，加锁成功之后会进入 代码块。
                synchronized (f) {
                    //判断sync加锁是否为当前桶位 头节点，防止其它线程，在当前线程加锁成功之前，修改过 桶位 的头结点。
                    //条件成立：当前桶位头结点 仍然为f，其它线程没修改过。
                    if (tabAt(tab, i) == f) {
                        //条件成立：说明桶位 为 链表 或者 单个 node
                        if (fh >= 0) {
                            validated = true;

                            //e 表示当前循环处理元素
                            //pred 表示当前循环节点的上一个节点
                            Node<K,V> e = f, pred = null;
                            for (;;) {
                                //当前节点key
                                K ek;
                                //条件一：e.hash == hash true->说明当前节点的hash与查找节点hash一致
                                //条件二：((ek = e.key) == key || (ek != null && key.equals(ek)))
                                //if 条件成立，说明key 与查询的key完全一致。
                                if (e.hash == hash &&
                                    ((ek = e.key) == key ||
                                     (ek != null && key.equals(ek)))) {
                                    //当前节点的value
                                    V ev = e.val;

                                    //条件一：cv == null true->替换的值为null 那么就是一个删除操作
                                    //条件二：cv == ev || (ev != null && cv.equals(ev))  那么是一个替换操作
                                    if (cv == null || cv == ev ||
                                        (ev != null && cv.equals(ev))) {
                                        //删除 或者 替换

                                        //将当前节点的值 赋值给 oldVal 后续返回会用到
                                        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;
                            }
                        }

                        //条件成立：TreeBin节点。
                        else if (f instanceof TreeBin) {
                            validated = true;

                            //转换为实际类型 TreeBin t
                            TreeBin<K,V> t = (TreeBin<K,V>)f;
                            //r 表示 红黑树 根节点
                            //p 表示 红黑树中查找到对应key 一致的node
                            TreeNode<K,V> r, p;

                            //条件一：(r = t.root) != null 理论上是成立
                            //条件二：TreeNode.findTreeNode 以当前节点为入口，向下查找key（包括本身节点）
                            //      true->说明查找到相应key 对应的node节点。会赋值给p
                            if ((r = t.root) != null &&
                                (p = r.findTreeNode(hash, key, null)) != null) {
                                //保存p.val 到pv
                                V pv = p.val;

                                //条件一：cv == null  成立：不必对value，就做替换或者删除操作
                                //条件二：cv == pv ||(pv != null && cv.equals(pv)) 成立：说明“对比值”与当前p节点的值 一致
                                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));
                                }
                            }
                        }
                    }
                }
                //当其他线程修改过桶位 头结点时，当前线程 sync 头结点 锁错对象时，validated 为false，会进入下次for 自旋
                if (validated) {

                    if (oldVal != null) {
                        //替换的值 为null，说明当前是一次删除操作，oldVal ！=null 成立，说明删除成功，更新当前元素个数计数器。
                        if (value == null)
                            addCount(-1L, -1);
                        return oldVal;
                    }
                    break;
                }
            }
        }
        return null;
    }