1.JDK1.7

數(shù)據(jù)結(jié)構(gòu)：

• 分為兩級數(shù)組蜓陌，外面有一個Segment數(shù)組窍株，大小與并發(fā)級別有關(guān)
• 每個Segment管理一個HashEntry數(shù)組

Segment鎖機(jī)制：

• 比如put，在Segment里面put時，先要加鎖tryLock()
• Segment繼承了ReentrantLock
• tryLock()失敗后，進(jìn)入while(!tryLock)循環(huán)，創(chuàng)建HashEntry饵逐，自旋達(dá)到閾值后（64/1），直接lock()阻塞

哈希尋址：

• 第一步用來定位Segment位置彪标，這里取的是高位
• 第二步用來定位Segment里面小數(shù)組的位置

擴(kuò)容rehash()：

• 是Segment里面的數(shù)組進(jìn)行擴(kuò)容
• lastRun機(jī)制
  末尾放到同一個位置的連續(xù)鏈表梳毙；
  直接插入到新數(shù)組位置；
  移動：只用移動鏈表頭到lastRun的元素捐下。

get()：

• 首先定位Segment
• 其次定位HashEntry
• 最后遍歷鏈表

size()：

• 第一次不加鎖
• 第二次也不加鎖账锹，如果與第一次相等萌业，則返回統(tǒng)計數(shù)值
• 第三次加鎖統(tǒng)計（對所有segment都加鎖）

2.JDK1.8

2.1 數(shù)據(jù)結(jié)構(gòu)

基本數(shù)據(jù)結(jié)構(gòu)是數(shù)組，發(fā)送哈希沖突時采用鏈表解決奸柬，如果數(shù)組大小達(dá)到64并且鏈表長度達(dá)到8生年，則轉(zhuǎn)換為紅黑樹。

通過節(jié)點的hash值區(qū)分不同節(jié)點：

• ForwardingNode廓奕，擴(kuò)容時被轉(zhuǎn)移的節(jié)點抱婉，hash值是-1
• TreeBin，紅黑樹桌粉，hash值是-2
• 正常鏈表Node節(jié)點蒸绩，會通過spread()后的，會跟0x7fffffff相與铃肯，是個大于0的數(shù)

2.1.1 數(shù)組大小

數(shù)組的大小為2的冪次方：返回>=c的最小的2的次方數(shù)

    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 表示當(dāng)前table正在初始化（有線程在創(chuàng)建table數(shù)組）患亿，當(dāng)前線程需要自旋等待..
  2）表示當(dāng)前table數(shù)組正在進(jìn)行擴(kuò)容 ,高16位表示：擴(kuò)容的標(biāo)識戳 低16位表示：（1 + nThread） 當(dāng)前參與并發(fā)擴(kuò)容的線程數(shù)量
• sizeCtl = 0，表示創(chuàng)建table數(shù)組時 使用DEFAULT_CAPACITY為大小
• sizeCtl > 0
  1）如果table未初始化押逼，表示初始化大小
  2）如果table已經(jīng)初始化步藕，表示下次擴(kuò)容時的 觸發(fā)條件（閾值）

 /**
     * sizeCtl < 0
     * 1. -1 表示當(dāng)前table正在初始化（有線程在創(chuàng)建table數(shù)組），當(dāng)前線程需要自旋等待..
     * 2.表示當(dāng)前table數(shù)組正在進(jìn)行擴(kuò)容 ,高16位表示：擴(kuò)容的標(biāo)識戳   低16位表示：（1 + nThread） 當(dāng)前參與并發(fā)擴(kuò)容的線程數(shù)量
     *
     * sizeCtl = 0挑格，表示創(chuàng)建table數(shù)組時 使用DEFAULT_CAPACITY為大小
     *
     * sizeCtl > 0
     *
     * 1. 如果table未初始化咙冗，表示初始化大小
     * 2. 如果table已經(jīng)初始化，表示下次擴(kuò)容時的 觸發(fā)條件（閾值）
     */
    private transient volatile int sizeCtl;

2.1.3 數(shù)組初始化

在put()中進(jìn)行延遲初始化

    /**
     * Initializes table, using the size recorded in sizeCtl.
     *      * sizeCtl < 0
     *      * 1. -1 表示當(dāng)前table正在初始化（有線程在創(chuàng)建table數(shù)組）漂彤，當(dāng)前線程需要自旋等待..
     *      * 2.表示當(dāng)前table數(shù)組正在進(jìn)行擴(kuò)容 ,高16位表示：擴(kuò)容的標(biāo)識戳   低16位表示：（1 + nThread） 當(dāng)前參與并發(fā)擴(kuò)容的線程數(shù)量
     *      *
     *      * sizeCtl = 0雾消，表示創(chuàng)建table數(shù)組時 使用DEFAULT_CAPACITY為大小
     *      *
     *      * sizeCtl > 0
     *      *
     *      * 1. 如果table未初始化，表示初始化大小
     *      * 2. 如果table已經(jīng)初始化挫望，表示下次擴(kuò)容時的 觸發(fā)條件（閾值）
     */
    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立润，表示其它線程正在進(jìn)行創(chuàng)建table的過程，當(dāng)前線程沒有競爭到初始化table的鎖士骤。
                Thread.yield(); // lost initialization race; just spin

            //1.sizeCtl = 0范删，表示創(chuàng)建table數(shù)組時 使用DEFAULT_CAPACITY為大小
            //2.如果table未初始化，表示初始化大小
            //3.如果table已經(jīng)初始化拷肌，表示下次擴(kuò)容時的 觸發(fā)條件（閾值）
            else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
                try {
                    //這里為什么又要判斷呢到旦？ 防止其它線程已經(jīng)初始化完畢了，然后當(dāng)前線程再次初始化..導(dǎo)致丟失數(shù)據(jù)巨缘。
                    //條件成立添忘，說明其它線程都沒有進(jìn)入過這個if塊，當(dāng)前線程就是具備初始化table權(quán)利了若锁。
                    if ((tab = table) == null || tab.length == 0) {

                        //sc大于0 創(chuàng)建table時 使用 sc為指定大小搁骑，否則使用 16 默認(rèn)值.
                        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 表示下一次擴(kuò)容時的觸發(fā)條件。
                        sc = n - (n >>> 2);
                    }
                } finally {
                    //1.如果當(dāng)前線程是第一次創(chuàng)建map.table的線程話，sc表示的是 下一次擴(kuò)容的閾值
                    //2.表示當(dāng)前線程 并不是第一次創(chuàng)建map.table的線程仲器，當(dāng)前線程進(jìn)入到else if 塊 時煤率，將
                    //sizeCtl 設(shè)置為了-1 ，那么這時需要將其修改為 進(jìn)入時的值乏冀。
                    sizeCtl = sc;
                }
                break;
            }
        }
        return tab;
    }

2.1.4 TreeBin鎖狀態(tài)

1.寫鎖狀態(tài) 寫是獨(dú)占狀態(tài)蝶糯，以散列表來看，真正進(jìn)入到TreeBin中的寫線程 同一時刻 只有一個線程辆沦。 1
2.讀鎖狀態(tài) 讀鎖是共享昼捍，同一時刻可以有多個線程 同時進(jìn)入到 TreeBin對象中獲取數(shù)據(jù)。 每一個線程 都會給 lockStat + 4
3.等待者狀態(tài)（寫線程在等待）肢扯，當(dāng)TreeBin中有讀線程目前正在讀取數(shù)據(jù)時妒茬，寫線程無法修改數(shù)據(jù)，那么就將lockState的最低2位 設(shè)置為 0b 10

        /**
         * 1.寫鎖狀態(tài) 寫是獨(dú)占狀態(tài)蔚晨，以散列表來看乍钻，真正進(jìn)入到TreeBin中的寫線程 同一時刻 只有一個線程。 1
         * 2.讀鎖狀態(tài) 讀鎖是共享蛛株，同一時刻可以有多個線程 同時進(jìn)入到 TreeBin對象中獲取數(shù)據(jù)团赁。 每一個線程 都會給 lockStat + 4
         * 3.等待者狀態(tài)（寫線程在等待）育拨，當(dāng)TreeBin中有讀線程目前正在讀取數(shù)據(jù)時谨履，寫線程無法修改數(shù)據(jù)，那么就將lockState的最低2位 設(shè)置為 0b 10
         */
        volatile int lockState;

2.2 get()

    public V get(Object key) {
        //tab 引用map.table
        //e 當(dāng)前元素
        //p 目標(biāo)節(jié)點
        //n table數(shù)組長度
        //eh 當(dāng)前元素hash
        //ek 當(dāng)前元素key
        Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
        //擾動運(yùn)算后得到 更散列的hash值
        int h = spread(key.hashCode());

        //條件一：(tab = table) != null
        //true->表示已經(jīng)put過數(shù)據(jù)熬丧，并且map內(nèi)部的table也已經(jīng)初始化完畢
        //false->表示創(chuàng)建完map后笋粟，并沒有put過數(shù)據(jù)，map內(nèi)部的table是延遲初始化的析蝴，只有第一次寫數(shù)據(jù)時會觸發(fā)創(chuàng)建邏輯害捕。
        //條件二：(n = tab.length) > 0 true->表示table已經(jīng)初始化
        //條件三：(e = tabAt(tab, (n - 1) & h)) != null
        //true->當(dāng)前key尋址的桶位 有值
        //false->當(dāng)前key尋址的桶位中是null，是null直接返回null
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (e = tabAt(tab, (n - 1) & h)) != null) {
            //前置條件：當(dāng)前桶位有數(shù)據(jù)

            //對比頭結(jié)點hash與查詢key的hash是否一致
            //條件成立：說明頭結(jié)點與查詢Key的hash值 完全一致
            if ((eh = e.hash) == h) {
                //完全比對 查詢key 和 頭結(jié)點的key
                //條件成立：說明頭結(jié)點就是查詢數(shù)據(jù)
                if ((ek = e.key) == key || (ek != null && key.equals(ek)))
                    return e.val;
            }

            //條件成立：
            //1.-1  fwd 說明當(dāng)前table正在擴(kuò)容闷畸，且當(dāng)前查詢的這個桶位的數(shù)據(jù) 已經(jīng)被遷移走了
            //2.-2  TreeBin節(jié)點尝盼，需要使用TreeBin 提供的find 方法查詢。
            else if (eh < 0)
                return (p = e.find(h, key)) != null ? p.val : null;




            //當(dāng)前桶位已經(jīng)形成鏈表的這種情況
            while ((e = e.next) != null) {
                if (e.hash == h &&
                    ((ek = e.key) == key || (ek != null && key.equals(ek))))
                    return e.val;
            }

        }
        return null;
    }

這里對hash值進(jìn)行了處理佑菩，使高位向低位融合盾沫，是為了得到更散列的hash值。

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

上面eh < 0殿漠，有兩種情況：

• ForwardingNode赴精，此時回去nextTable里面查找
• TreeBin，此時獲取紅黑樹查找（這里嘗試加讀鎖進(jìn)行樹查找绞幌，如果沒加成功蕾哟，則進(jìn)行鏈表查找）

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 表示為擴(kuò)容而創(chuàng)建的 新表的長度
                //e 表示在擴(kuò)容而創(chuàng)建新表使用 尋址算法 得到的 桶位頭結(jié)點
                Node<K,V> e; int n;

                //條件一：永遠(yuǎn)不成立
                //條件二：永遠(yuǎn)不成立
                //條件三：永遠(yuǎn)不成立
                //條件四：在新擴(kuò)容表中 重新定位 hash 對應(yīng)的頭結(jié)點
                //true -> 1.在oldTable中 對應(yīng)的桶位在遷移之前就是null
                //        2.擴(kuò)容完成后，有其它寫線程，將此桶位設(shè)置為了null
                if (k == null || tab == null || (n = tab.length) == 0 ||
                    (e = tabAt(tab, (n - 1) & h)) == null)
                    return null;

                //前置條件：擴(kuò)容后的表 對應(yīng)hash的桶位一定不是null谭确，e為此桶位的頭結(jié)點
                //e可能為哪些node類型帘营？
                //1.node 類型
                //2.TreeBin 類型
                //3.FWD 類型

                for (;;) {
                    //eh 新擴(kuò)容后表指定桶位的當(dāng)前節(jié)點的hash
                    //ek 新擴(kuò)容后表指定桶位的當(dāng)前節(jié)點的key
                    int eh; K ek;
                    //條件成立：說明新擴(kuò)容 后的表，當(dāng)前命中桶位中的數(shù)據(jù)逐哈，即為 查詢想要數(shù)據(jù)仪吧。
                    if ((eh = e.hash) == h &&
                        ((ek = e.key) == k || (ek != null && k.equals(ek))))
                        return e;

                    //eh<0
                    //1.TreeBin 類型    2.FWD類型（新擴(kuò)容的表，在并發(fā)很大的情況下鞠眉，可能在此方法 再次拿到FWD類型..）
                    if (eh < 0) {
                        if (e instanceof ForwardingNode) {
                            tab = ((ForwardingNode<K,V>)e).nextTable;
                            continue outer;
                        }
                        else
                            //說明此桶位 為 TreeBin 節(jié)點薯鼠，使用TreeBin.find 查找紅黑樹中相應(yīng)節(jié)點。
                            return e.find(h, k);
                    }

                    //前置條件：當(dāng)前桶位頭結(jié)點 并沒有命中查詢械蹋，說明此桶位是 鏈表
                    //1.將當(dāng)前元素 指向鏈表的下一個元素
                    //2.判斷當(dāng)前元素的下一個位置 是否為空
                    //   true->說明迭代到鏈表末尾出皇，未找到對應(yīng)的數(shù)據(jù)，返回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 表示循環(huán)迭代的當(dāng)前節(jié)點   迭代的是first引用的鏈表
                for (Node<K,V> e = first; e != null; ) {
                    //s 保存的是lock臨時狀態(tài)
                    //ek 鏈表當(dāng)前節(jié)點 的key
                    int s; K ek;


                    //(WAITER|WRITER) => 0010 | 0001 => 0011
                    //lockState & 0011 != 0 條件成立：說明當(dāng)前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;
                    }

                    //前置條件：當(dāng)前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.當(dāng)前線程查詢紅黑樹結(jié)束哗戈，釋放當(dāng)前線程的讀鎖 就是讓 lockstate 值 - 4
                            //(READER|WAITER) = 0110 => 表示當(dāng)前只有一個線程在讀郊艘，且“有一個線程在等待”
                            //當(dāng)前讀線程為 TreeBin中的最后一個讀線程。

                            //2.(w = waiter) != null 說明有一個寫線程在等待讀操作全部結(jié)束唯咬。
                            if (U.getAndAddInt(this, LOCKSTATE, -READER) ==
                                (READER|WAITER) && (w = waiter) != null)
                                //使用unpark 讓 寫線程 恢復(fù)運(yùn)行狀態(tài)纱注。
                                LockSupport.unpark(w);
                        }
                        return p;
                    }
                }
            }
            return null;
        }

2.3 put()

binCount的含義：

• binCount表示當(dāng)前k-v 封裝成node后插入到指定桶位后，在桶位中的所屬鏈表的下標(biāo)位置（兩種情況：1.當(dāng)前插入key與鏈表當(dāng)中所有元素的key都不一致時胆胰，當(dāng)前的插入操作是追加到鏈表的末尾狞贱，binCount表示鏈表長度；2.當(dāng)前插入key與鏈表當(dāng)中的某個元素的key一致時蜀涨，當(dāng)前插入操作可能就是替換了瞎嬉。binCount表示沖突位置（binCount - 1））
• 0表示當(dāng)前桶位為null，node可以直接放著
• 2表示當(dāng)前桶位已經(jīng)可能是紅黑樹

總體來說分為幾種情況：

• CASE1：當(dāng)前map中的table尚未初始化
• CASE2：定位的桶位（槽位）為null厚柳。i 表示key使用路由尋址算法得到 key對應(yīng) table數(shù)組的下標(biāo)位置氧枣，tabAt 獲取指定桶位的頭結(jié)點 f
• CASE3：前置條件，桶位的頭結(jié)點一定不是null别垮。當(dāng)前桶位的頭結(jié)點 為 FWD結(jié)點便监，表示目前map正處于擴(kuò)容過程中..
• CASE4：當(dāng)前桶位 可能是 鏈表 也可能是 紅黑樹代理結(jié)點TreeBin

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

        //通過spread方法，可以讓高位也能參與進(jìn)尋址運(yùn)算碳想。
        int hash = spread(key.hashCode());
        //binCount表示當(dāng)前k-v 封裝成node后插入到指定桶位后烧董，在桶位中的所屬鏈表的下標(biāo)位置
        //0 表示當(dāng)前桶位為null，node可以直接放著
        //2 表示當(dāng)前桶位已經(jīng)可能是紅黑樹
        int binCount = 0;

        //tab 引用map對象的table
        //自旋
        for (Node<K,V>[] tab = table;;) {
            //f 表示桶位的頭結(jié)點
            //n 表示散列表數(shù)組的長度
            //i 表示key通過尋址計算后移袍，得到的桶位下標(biāo)
            //fh 表示桶位頭結(jié)點的hash值
            Node<K,V> f; int n, i, fh;

            //CASE1：成立解藻，表示當(dāng)前map中的table尚未初始化..
            if (tab == null || (n = tab.length) == 0)
                //最終當(dāng)前線程都會獲取到最新的map.table引用。
                tab = initTable();
            //CASE2：i 表示key使用路由尋址算法得到 key對應(yīng) table數(shù)組的下標(biāo)位置葡盗，tabAt 獲取指定桶位的頭結(jié)點 f
            else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
                //進(jìn)入到CASE2代碼塊 前置條件 當(dāng)前table數(shù)組i桶位是Null時螟左。
                //使用CAS方式 設(shè)置 指定數(shù)組i桶位 為 new Node<K,V>(hash, key, value, null),并且期望值是null
                //cas操作成功 表示ok啡浊，直接break for循環(huán)即可
                //cas操作失敗，表示在當(dāng)前線程之前胶背，有其它線程先你一步向指定i桶位設(shè)置值了巷嚣。
                //當(dāng)前線程只能再次自旋，去走其它邏輯钳吟。
                if (casTabAt(tab, i, null,
                             new Node<K,V>(hash, key, value, null)))
                    break;                   // no lock when adding to empty bin
            }

            //CASE3：前置條件廷粒，桶位的頭結(jié)點一定不是null。
            //條件成立表示當(dāng)前桶位的頭結(jié)點 為 FWD結(jié)點红且，表示目前map正處于擴(kuò)容過程中..
            else if ((fh = f.hash) == MOVED)
                //看到fwd節(jié)點后坝茎，當(dāng)前節(jié)點有義務(wù)幫助當(dāng)前map對象完成遷移數(shù)據(jù)的工作
                //學(xué)完擴(kuò)容后再來看。
                tab = helpTransfer(tab, f);

            //CASE4：當(dāng)前桶位 可能是 鏈表 也可能是 紅黑樹代理結(jié)點TreeBin
            else {
                //當(dāng)插入key存在時暇番，會將舊值賦值給oldVal嗤放，返回給put方法調(diào)用處..
                V oldVal = null;

                //使用sync 加鎖“頭節(jié)點”，理論上是“頭結(jié)點”
                synchronized (f) {
                    //為什么又要對比一下壁酬，看看當(dāng)前桶位的頭節(jié)點 是否為 之前獲取的頭結(jié)點次酌？
                    //為了避免其它線程將該桶位的頭結(jié)點修改掉，導(dǎo)致當(dāng)前線程從sync 加鎖 就有問題了舆乔。之后所有操作都不用在做了岳服。
                    if (tabAt(tab, i) == f) {//條件成立，說明咱們 加鎖 的對象沒有問題希俩，可以進(jìn)來造了吊宋！

                        //條件成立，說明當(dāng)前桶位就是普通鏈表桶位斜纪。
                        if (fh >= 0) {
                            //1.當(dāng)前插入key與鏈表當(dāng)中所有元素的key都不一致時贫母，當(dāng)前的插入操作是追加到鏈表的末尾文兑，binCount表示鏈表長度
                            //2.當(dāng)前插入key與鏈表當(dāng)中的某個元素的key一致時盒刚，當(dāng)前插入操作可能就是替換了。binCount表示沖突位置（binCount - 1）
                            binCount = 1;

                            //迭代循環(huán)當(dāng)前桶位的鏈表绿贞，e是每次循環(huán)處理節(jié)點因块。
                            for (Node<K,V> e = f;; ++binCount) {
                                //當(dāng)前循環(huán)節(jié)點 key
                                K ek;
                                //條件一：e.hash == hash 成立 表示循環(huán)的當(dāng)前元素的hash值與插入節(jié)點的hash值一致，需要進(jìn)一步判斷
                                //條件二：((ek = e.key) == key ||(ek != null && key.equals(ek)))
                                //       成立：說明循環(huán)的當(dāng)前節(jié)點與插入節(jié)點的key一致籍铁，發(fā)生沖突了
                                if (e.hash == hash &&
                                    ((ek = e.key) == key ||
                                     (ek != null && key.equals(ek)))) {
                                    //將當(dāng)前循環(huán)的元素的 值 賦值給oldVal
                                    oldVal = e.val;

                                    if (!onlyIfAbsent)
                                        e.val = value;
                                    break;
                                }
                                //當(dāng)前元素 與 插入元素的key不一致 時涡上，會走下面程序。
                                //1.更新循環(huán)處理節(jié)點為 當(dāng)前節(jié)點的下一個節(jié)點
                                //2.判斷下一個節(jié)點是否為null拒名，如果是null吩愧，說明當(dāng)前節(jié)點已經(jīng)是隊尾了，插入數(shù)據(jù)需要追加到隊尾節(jié)點的后面增显。

                                Node<K,V> pred = e;
                                if ((e = e.next) == null) {
                                    pred.next = new Node<K,V>(hash, key,
                                                              value, null);
                                    break;
                                }
                            }
                        }
                        //前置條件雁佳，該桶位一定不是鏈表
                        //條件成立，表示當(dāng)前桶位是 紅黑樹代理結(jié)點TreeBin
                        else if (f instanceof TreeBin) {
                            //p 表示紅黑樹中如果與你插入節(jié)點的key 有沖突節(jié)點的話 ，則putTreeVal 方法 會返回沖突節(jié)點的引用糖权。
                            Node<K,V> p;
                            //強(qiáng)制設(shè)置binCount為2堵腹，因為binCount <= 1 時有其它含義，所以這里設(shè)置為了2 回頭講 addCount星澳。
                            binCount = 2;

                            //條件一：成立疚顷，說明當(dāng)前插入節(jié)點的key與紅黑樹中的某個節(jié)點的key一致，沖突了
                            if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
                                                           value)) != null) {
                                //將沖突節(jié)點的值 賦值給 oldVal
                                oldVal = p.val;
                                if (!onlyIfAbsent)
                                    p.val = value;
                            }
                        }
                    }
                }

                //說明當(dāng)前桶位不為null禁偎，可能是紅黑樹 也可能是鏈表
                if (binCount != 0) {
                    //如果binCount>=8 表示處理的桶位一定是鏈表
                    if (binCount >= TREEIFY_THRESHOLD)
                        //調(diào)用轉(zhuǎn)化鏈表為紅黑樹的方法
                        treeifyBin(tab, i);
                    //說明當(dāng)前線程插入的數(shù)據(jù)key腿堤，與原有k-v發(fā)生沖突，需要將原數(shù)據(jù)v返回給調(diào)用者如暖。
                    if (oldVal != null)
                        return oldVal;
                    break;
                }
            }
        }

        //1.統(tǒng)計當(dāng)前table一共有多少數(shù)據(jù)
        //2.判斷是否達(dá)到擴(kuò)容閾值標(biāo)準(zhǔn)释液，觸發(fā)擴(kuò)容。
        addCount(1L, binCount);

        return null;
    }

2.4 addCount()

這里的核心是sizeCtl：表示當(dāng)前table數(shù)組正在進(jìn)行擴(kuò)容 ,高16位表示：擴(kuò)容的標(biāo)識戳 低16位表示：（1 + nThread） 當(dāng)前參與并發(fā)擴(kuò)容的線程數(shù)量

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

上面這個條件代碼有一個bug：

• 條件二： JDK1.8 中有bug jira已經(jīng)提出來了 其實想表達(dá)的是 = sc == (rs << 16 ) + 1
  true-> 表示擴(kuò)容完畢装处，當(dāng)前線程不需要再參與進(jìn)來了
  false->擴(kuò)容還在進(jìn)行中误债，當(dāng)前線程可以參與
• 條件三：JDK1.8 中有bug jira已經(jīng)提出來了 其實想表達(dá)的是 = sc == (rs<<16) + MAX_RESIZERS
  true-> 表示當(dāng)前參與并發(fā)擴(kuò)容的線程達(dá)到了最大值 65535 - 1
  false->表示當(dāng)前線程可以參與進(jìn)來

    private final void addCount(long x, int check) {
        //as 表示 LongAdder.cells
        //b 表示LongAdder.base
        //s 表示當(dāng)前map.table中元素的數(shù)量
        CounterCell[] as; long b, s;
        //條件一：true->表示cells已經(jīng)初始化了，當(dāng)前線程應(yīng)該去使用hash尋址找到合適的cell 去累加數(shù)據(jù)
        //       false->表示當(dāng)前線程應(yīng)該將數(shù)據(jù)累加到 base
        //條件二：false->表示寫base成功妄迁，數(shù)據(jù)累加到base中了寝蹈，當(dāng)前競爭不激烈，不需要創(chuàng)建cells
        //       true->表示寫base失敗登淘，與其他線程在base上發(fā)生了競爭箫老，當(dāng)前線程應(yīng)該去嘗試創(chuàng)建cells。
        if ((as = counterCells) != null ||
            !U.compareAndSwapLong(this, BASECOUNT, b = baseCount, s = b + x)) {
            //有幾種情況進(jìn)入到if塊中黔州？
            //1.true->表示cells已經(jīng)初始化了耍鬓，當(dāng)前線程應(yīng)該去使用hash尋址找到合適的cell 去累加數(shù)據(jù)
            //2.true->表示寫base失敗，與其他線程在base上發(fā)生了競爭流妻，當(dāng)前線程應(yīng)該去嘗試創(chuàng)建cells牲蜀。

            //a 表示當(dāng)前線程hash尋址命中的cell
            CounterCell a;
            //v 表示當(dāng)前線程寫cell時的期望值
            long v;
            //m 表示當(dāng)前cells數(shù)組的長度
            int m;
            //true -> 未競爭  false->發(fā)生競爭
            boolean uncontended = true;


            //條件一：as == null || (m = as.length - 1) < 0
            //true-> 表示當(dāng)前線程是通過 寫base競爭失敗 然后進(jìn)入的if塊，就需要調(diào)用fullAddCount方法去擴(kuò)容 或者 重試.. LongAdder.longAccumulate
            //條件二：a = as[ThreadLocalRandom.getProbe() & m]) == null   前置條件：cells已經(jīng)初始化了
            //true->表示當(dāng)前線程命中的cell表格是個空绅这，需要當(dāng)前線程進(jìn)入fullAddCount方法去初始化 cell涣达，放入當(dāng)前位置.
            //條件三：!(uncontended = U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x)
            //      false->取反得到false，表示當(dāng)前線程使用cas方式更新當(dāng)前命中的cell成功
            //      true->取反得到true,表示當(dāng)前線程使用cas方式更新當(dāng)前命中的cell失敗证薇，需要進(jìn)入fullAddCount進(jìn)行重試 或者 擴(kuò)容 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里面的事情比較累，就讓當(dāng)前線程 不參與到 擴(kuò)容相關(guān)的邏輯了浑度，直接返回到調(diào)用點寇窑。
                return;
            }

            if (check <= 1)
                return;

            //獲取當(dāng)前散列表元素個數(shù)，這是一個期望值
            s = sumCount();
        }

        //表示一定是一個put操作調(diào)用的addCount
        if (check >= 0) {
            //tab 表示map.table
            //nt 表示map.nextTable
            //n 表示map.table數(shù)組的長度
            //sc 表示sizeCtl的臨時值
            Node<K,V>[] tab, nt; int n, sc;


            /**
             * sizeCtl < 0
             * 1. -1 表示當(dāng)前table正在初始化（有線程在創(chuàng)建table數(shù)組）箩张，當(dāng)前線程需要自旋等待..
             * 2.表示當(dāng)前table數(shù)組正在進(jìn)行擴(kuò)容 ,高16位表示：擴(kuò)容的標(biāo)識戳   低16位表示：（1 + nThread） 當(dāng)前參與并發(fā)擴(kuò)容的線程數(shù)量
             *
             * sizeCtl = 0甩骏，表示創(chuàng)建table數(shù)組時 使用DEFAULT_CAPACITY為大小
             *
             * sizeCtl > 0
             *
             * 1. 如果table未初始化完残，表示初始化大小
             * 2. 如果table已經(jīng)初始化，表示下次擴(kuò)容時的 觸發(fā)條件（閾值）
             */

            //自旋
            //條件一：s >= (long)(sc = sizeCtl)
            //       true-> 1.當(dāng)前sizeCtl為一個負(fù)數(shù) 表示正在擴(kuò)容中..
            //              2.當(dāng)前sizeCtl是一個正數(shù)横漏，表示擴(kuò)容閾值
            //       false-> 表示當(dāng)前table尚未達(dá)到擴(kuò)容條件
            //條件二：(tab = table) != null
            //       恒成立 true
            //條件三：(n = tab.length) < MAXIMUM_CAPACITY
            //       true->當(dāng)前table長度小于最大值限制谨设，則可以進(jìn)行擴(kuò)容。
            while (s >= (long)(sc = sizeCtl) && (tab = table) != null &&
                   (n = tab.length) < MAXIMUM_CAPACITY) {

                //擴(kuò)容批次唯一標(biāo)識戳
                //16 -> 32 擴(kuò)容 標(biāo)識為：1000 0000 0001 1011
                int rs = resizeStamp(n);

                //條件成立：表示當(dāng)前table正在擴(kuò)容
                //         當(dāng)前線程理論上應(yīng)該協(xié)助table完成擴(kuò)容
                if (sc < 0) {
                    //條件一：(sc >>> RESIZE_STAMP_SHIFT) != rs
                    //      true->說明當(dāng)前線程獲取到的擴(kuò)容唯一標(biāo)識戳 非 本批次擴(kuò)容
                    //      false->說明當(dāng)前線程獲取到的擴(kuò)容唯一標(biāo)識戳 是 本批次擴(kuò)容
                    //條件二： JDK1.8 中有bug jira已經(jīng)提出來了 其實想表達(dá)的是 =  sc == (rs << 16 ) + 1
                    //        true-> 表示擴(kuò)容完畢缎浇，當(dāng)前線程不需要再參與進(jìn)來了
                    //        false->擴(kuò)容還在進(jìn)行中扎拣，當(dāng)前線程可以參與
                    //條件三：JDK1.8 中有bug jira已經(jīng)提出來了 其實想表達(dá)的是 = sc == (rs<<16) + MAX_RESIZERS
                    //        true-> 表示當(dāng)前參與并發(fā)擴(kuò)容的線程達(dá)到了最大值 65535 - 1
                    //        false->表示當(dāng)前線程可以參與進(jìn)來
                    //條件四：(nt = nextTable) == null
                    //        true->表示本次擴(kuò)容結(jié)束
                    //        false->擴(kuò)容正在進(jìn)行中
                    if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
                        sc == rs + MAX_RESIZERS || (nt = nextTable) == null ||
                        transferIndex <= 0)
                        break;

                    //前置條件：當(dāng)前table正在執(zhí)行擴(kuò)容中.. 當(dāng)前線程有機(jī)會參與進(jìn)擴(kuò)容。
                    //條件成立：說明當(dāng)前線程成功參與到擴(kuò)容任務(wù)中素跺，并且將sc低16位值加1二蓝，表示多了一個線程參與工作
                    //條件失敗：1.當(dāng)前有很多線程都在此處嘗試修改sizeCtl指厌，有其它一個線程修改成功了刊愚，導(dǎo)致你的sc期望值與內(nèi)存中的值不一致 修改失敗
                    //        2.transfer 任務(wù)內(nèi)部的線程也修改了sizeCtl。
                    if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1))
                        //協(xié)助擴(kuò)容線程踩验，持有nextTable參數(shù)
                        transfer(tab, nt);
                }
                //1000 0000 0001 1011 0000 0000 0000 0000 +2 => 1000 0000 0001 1011 0000 0000 0000 0010
                //條件成立鸥诽，說明當(dāng)前線程是觸發(fā)擴(kuò)容的第一個線程，在transfer方法需要做一些擴(kuò)容準(zhǔn)備工作
                else if (U.compareAndSwapInt(this, SIZECTL, sc,
                                             (rs << RESIZE_STAMP_SHIFT) + 2))
                    //觸發(fā)擴(kuò)容條件的線程 不持有nextTable
                    transfer(tab, null);
                s = sumCount();
            }
        }
    }

2.5 擴(kuò)容

    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) {

            //拿當(dāng)前標(biāo)的長度 獲取 擴(kuò)容標(biāo)識戳   假設(shè) 16 -> 32 擴(kuò)容：1000 0000 0001 1011
            int rs = resizeStamp(tab.length);

            //條件一：nextTab == nextTable
            //成立：表示當(dāng)前擴(kuò)容正在進(jìn)行中
            //不成立：1.nextTable被設(shè)置為Null 了牡借，擴(kuò)容完畢后，會被設(shè)為Null
            //       2.再次出發(fā)擴(kuò)容了...咱們拿到的nextTab 也已經(jīng)過期了...
            //條件二：table == tab
            //成立：說明 擴(kuò)容正在進(jìn)行中袭异，還未完成
            //不成立：說明擴(kuò)容已經(jīng)結(jié)束了钠龙，擴(kuò)容結(jié)束之后，最后退出的線程 會設(shè)置 nextTable 為 table

            //條件三：(sc = sizeCtl) < 0
            //成立：說明擴(kuò)容正在進(jìn)行中
            //不成立：說明sizeCtl當(dāng)前是一個大于0的數(shù)御铃，此時代表下次擴(kuò)容的閾值碴里，當(dāng)前擴(kuò)容已經(jīng)結(jié)束。
            while (nextTab == nextTable && table == tab &&
                   (sc = sizeCtl) < 0) {


                //條件一：(sc >>> RESIZE_STAMP_SHIFT) != rs
                //      true->說明當(dāng)前線程獲取到的擴(kuò)容唯一標(biāo)識戳 非 本批次擴(kuò)容
                //      false->說明當(dāng)前線程獲取到的擴(kuò)容唯一標(biāo)識戳 是 本批次擴(kuò)容
                //條件二： JDK1.8 中有bug jira已經(jīng)提出來了 其實想表達(dá)的是 =  sc == (rs << 16 ) + 1
                //        true-> 表示擴(kuò)容完畢上真，當(dāng)前線程不需要再參與進(jìn)來了
                //        false->擴(kuò)容還在進(jìn)行中咬腋，當(dāng)前線程可以參與
                //條件三：JDK1.8 中有bug jira已經(jīng)提出來了 其實想表達(dá)的是 = sc == (rs<<16) + MAX_RESIZERS
                //        true-> 表示當(dāng)前參與并發(fā)擴(kuò)容的線程達(dá)到了最大值 65535 - 1
                //        false->表示當(dāng)前線程可以參與進(jìn)來
                //條件四：transferIndex <= 0
                //      true->說明map對象全局范圍內(nèi)的任務(wù)已經(jīng)分配完了，當(dāng)前線程進(jìn)去也沒活干..
                //      false->還有任務(wù)可以分配谷羞。
                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;
    }

核心擴(kuò)容方法帝火，核心分為兩大步驟：

• 1）給當(dāng)前線程分配任務(wù)區(qū)間；維護(hù)當(dāng)前線程任務(wù)進(jìn)度（i 表示當(dāng)前處理的桶位）湃缎；維護(hù)map對象全局范圍內(nèi)的進(jìn)度transferIndex
• 2）遷移自己負(fù)責(zé)的任務(wù)區(qū)間：鏈表和紅黑樹

    private final void transfer(Node<K,V>[] tab, Node<K,V>[] nextTab) {
        //n 表示擴(kuò)容之前table數(shù)組的長度
        //stride 表示分配給線程任務(wù)的步長
        int n = tab.length, stride;
        //方便講解源碼  stride 固定為 16
        if ((stride = (NCPU > 1) ? (n >>> 3) / NCPU : n) < MIN_TRANSFER_STRIDE)
            stride = MIN_TRANSFER_STRIDE; // subdivide range


        //條件成立：表示當(dāng)前線程為觸發(fā)本次擴(kuò)容的線程，需要做一些擴(kuò)容準(zhǔn)備工作
        //條件不成立：表示當(dāng)前線程是協(xié)助擴(kuò)容的線程..
        if (nextTab == null) {            // initiating
            try {
                //創(chuàng)建了一個比擴(kuò)容之前大一倍的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 蠢壹，方便協(xié)助擴(kuò)容線程 拿到新表
            nextTable = nextTab;
            //記錄遷移數(shù)據(jù)整體位置的一個標(biāo)記嗓违。index計數(shù)是從1開始計算的。
            transferIndex = n;
        }

        //表示新數(shù)組的長度
        int nextn = nextTab.length;
        //fwd 節(jié)點图贸，當(dāng)某個桶位數(shù)據(jù)處理完畢后蹂季，將此桶位設(shè)置為fwd節(jié)點冕广，其它寫線程 或讀線程看到后，會有不同邏輯偿洁。
        ForwardingNode<K,V> fwd = new ForwardingNode<K,V>(nextTab);
        //推進(jìn)標(biāo)記
        boolean advance = true;
        //完成標(biāo)記
        boolean finishing = false; // to ensure sweep before committing nextTab

        //i 表示分配給當(dāng)前線程任務(wù)撒汉，執(zhí)行到的桶位
        //bound 表示分配給當(dāng)前線程任務(wù)的下界限制
        int i = 0, bound = 0;
        //自旋
        for (;;) {
            //f 桶位的頭結(jié)點
            //fh 頭結(jié)點的hash
            Node<K,V> f; int fh;


            /**
             * 1.給當(dāng)前線程分配任務(wù)區(qū)間
             * 2.維護(hù)當(dāng)前線程任務(wù)進(jìn)度（i 表示當(dāng)前處理的桶位）
             * 3.維護(hù)map對象全局范圍內(nèi)的進(jìn)度
             */
            while (advance) {
                //分配任務(wù)的開始下標(biāo)
                //分配任務(wù)的結(jié)束下標(biāo)
                int nextIndex, nextBound;

                //CASE1:
                //條件一：--i >= bound
                //成立：表示當(dāng)前線程的任務(wù)尚未完成，還有相應(yīng)的區(qū)間的桶位要處理涕滋，--i 就讓當(dāng)前線程處理下一個 桶位.
                //不成立：表示當(dāng)前線程任務(wù)已完成 或 者未分配
                if (--i >= bound || finishing)
                    advance = false;
                //CASE2:
                //前置條件：當(dāng)前線程任務(wù)已完成 或 者未分配
                //條件成立：表示對象全局范圍內(nèi)的桶位都分配完畢了睬辐，沒有區(qū)間可分配了，設(shè)置當(dāng)前線程的i變量為-1 跳出循環(huán)后宾肺，執(zhí)行退出遷移任務(wù)相關(guān)的程序
                //條件不成立：表示對象全局范圍內(nèi)的桶位尚未分配完畢溯饵，還有區(qū)間可分配
                else if ((nextIndex = transferIndex) <= 0) {
                    i = -1;
                    advance = false;
                }
                //CASE3:
                //前置條件：1、當(dāng)前線程需要分配任務(wù)區(qū)間  2.全局范圍內(nèi)還有桶位尚未遷移
                //條件成立：說明給當(dāng)前線程分配任務(wù)成功
                //條件失斚怯谩：說明分配給當(dāng)前線程失敗丰刊，應(yīng)該是和其它線程發(fā)生了競爭吧
                else if (U.compareAndSwapInt
                         (this, TRANSFERINDEX, nextIndex,
                          nextBound = (nextIndex > stride ?
                                       nextIndex - stride : 0))) {

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

            //CASE1：
            //條件一：i < 0
            //成立：表示當(dāng)前線程未分配到任務(wù)
            if (i < 0 || i >= n || i + n >= nextn) {
                //保存sizeCtl 的變量
                int sc;
                if (finishing) {
                    nextTable = null;
                    table = nextTab;
                    sizeCtl = (n << 1) - (n >>> 1);
                    return;
                }

                //條件成立：說明設(shè)置sizeCtl 低16位  -1 成功，當(dāng)前線程可以正常退出
                if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, sc - 1)) {
                    //1000 0000 0001 1011 0000 0000 0000 0000
                    //條件成立：說明當(dāng)前線程不是最后一個退出transfer任務(wù)的線程
                    if ((sc - 2) != resizeStamp(n) << RESIZE_STAMP_SHIFT)
                        //正常退出
                        return;

                    finishing = advance = true;
                    i = n; // recheck before commit
                }
            }
            //前置條件：【CASE2~CASE4】 當(dāng)前線程任務(wù)尚未處理完增拥，正在進(jìn)行中

            //CASE2:
            //條件成立：說明當(dāng)前桶位未存放數(shù)據(jù)啄巧，只需要將此處設(shè)置為fwd節(jié)點即可。
            else if ((f = tabAt(tab, i)) == null)
                advance = casTabAt(tab, i, null, fwd);
            //CASE3:
            //條件成立：說明當(dāng)前桶位已經(jīng)遷移過了掌栅，當(dāng)前線程不用再處理了棵帽，直接再次更新當(dāng)前線程任務(wù)索引，再次處理下一個桶位 或者 其它操作
            else if ((fh = f.hash) == MOVED)
                advance = true; // already processed
            //CASE4:
            //前置條件：當(dāng)前桶位有數(shù)據(jù)渣玲，而且node節(jié)點 不是 fwd節(jié)點逗概，說明這些數(shù)據(jù)需要遷移。
            else {
                //sync 加鎖當(dāng)前桶位的頭結(jié)點
                synchronized (f) {
                    //防止在你加鎖頭對象之前忘衍，當(dāng)前桶位的頭對象被其它寫線程修改過逾苫，導(dǎo)致你目前加鎖對象錯誤...
                    if (tabAt(tab, i) == f) {
                        //ln 表示低位鏈表引用
                        //hn 表示高位鏈表引用
                        Node<K,V> ln, hn;

                        //條件成立：表示當(dāng)前桶位是鏈表桶位
                        if (fh >= 0) {


                            //lastRun
                            //可以獲取出 當(dāng)前鏈表 末尾連續(xù)高位不變的 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;
                        }
                        //條件成立：表示當(dāng)前桶位是 紅黑樹 代理結(jié)點TreeBin
                        else if (f instanceof TreeBin) {
                            //轉(zhuǎn)換頭結(jié)點為 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 表示低位鏈表元素數(shù)量
                            //hc 表示高位鏈表元素數(shù)量
                            int lc = 0, hc = 0;

                            //迭代TreeBin中的雙向鏈表，從頭結(jié)點 至 尾節(jié)點
                            for (Node<K,V> e = t.first; e != null; e = e.next) {
                                // h 表示循環(huán)處理當(dāng)前元素的 hash
                                int h = e.hash;
                                //使用當(dāng)前節(jié)點 構(gòu)建出來的 新的 TreeNode
                                TreeNode<K,V> p = new TreeNode<K,V>
                                    (h, e.key, e.val, null, null);

                                //條件成立：表示當(dāng)前循環(huán)節(jié)點 屬于低位鏈 節(jié)點
                                if ((h & n) == 0) {
                                    //條件成立：說明當(dāng)前低位鏈表 還沒有數(shù)據(jù)
                                    if ((p.prev = loTail) == null)
                                        lo = p;
                                    //說明 低位鏈表已經(jīng)有數(shù)據(jù)了搀捷，此時當(dāng)前元素 追加到 低位鏈表的末尾就行了
                                    else
                                        loTail.next = p;
                                    //將低位鏈表尾指針指向 p 節(jié)點
                                    loTail = p;
                                    ++lc;
                                }
                                //當(dāng)前節(jié)點 屬于 高位鏈 節(jié)點
                                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()

這里最后有一個紅黑樹刪除節(jié)點星掰，然后調(diào)用untreeify操作

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

可以從removeTreeNode方法中看到，一般情況下嫩舟，其返回的false氢烘，只有當(dāng)樹節(jié)點很少時，才會返回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;

這里紅黑樹的刪除播玖，首先是從雙向鏈表中刪除，然后才是從紅黑樹中刪除饭于。如果節(jié)點較少蜀踏，直接從雙向鏈表刪除就返回维蒙，然后紅黑樹節(jié)點也不刪除。然后untreeify操作直接遍歷的就是雙向鏈表果覆，自然而然就是刪除節(jié)點后的樣子颅痊，這里代碼設(shè)計的操作非常精簡。

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

    final V replaceNode(Object key, V value, Object cv) {
        //計算key經(jīng)過擾動運(yùn)算后的hash
        int hash = spread(key.hashCode());
        //自旋
        for (Node<K,V>[] tab = table;;) {
            //f表示桶位頭結(jié)點
            //n表示當(dāng)前table數(shù)組長度
            //i表示hash命中桶位下標(biāo)
            //fh表示桶位頭結(jié)點 hash
            Node<K,V> f; int n, i, fh;

            //CASE1：
            //條件一：tab == null  true->表示當(dāng)前map.table尚未初始化..  false->已經(jīng)初始化
            //條件二：(n = tab.length) == 0  true->表示當(dāng)前map.table尚未初始化..  false->已經(jīng)初始化
            //條件三：(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：當(dāng)前桶位不是null
            //條件成立：說明當(dāng)前table正在擴(kuò)容中，當(dāng)前是個寫操作燎猛，所以當(dāng)前線程需要協(xié)助table完成擴(kuò)容恋捆。
            else if ((fh = f.hash) == MOVED)
                tab = helpTransfer(tab, f);

            //CASE3:
            //前置條件CASE2 ~ CASE3：當(dāng)前桶位不是null
            //當(dāng)前桶位 可能是 "鏈表" 也可能 是  "紅黑樹" TreeBin
            else {
                //保留替換之前的數(shù)據(jù)引用
                V oldVal = null;
                //校驗標(biāo)記
                boolean validated = false;
                //加鎖當(dāng)前桶位 頭結(jié)點，加鎖成功之后會進(jìn)入 代碼塊重绷。
                synchronized (f) {
                    //判斷sync加鎖是否為當(dāng)前桶位 頭節(jié)點沸停，防止其它線程，在當(dāng)前線程加鎖成功之前昭卓，修改過 桶位 的頭結(jié)點愤钾。
                    //條件成立：當(dāng)前桶位頭結(jié)點 仍然為f，其它線程沒修改過候醒。
                    if (tabAt(tab, i) == f) {
                        //條件成立：說明桶位 為 鏈表 或者 單個 node
                        if (fh >= 0) {
                            validated = true;

                            //e 表示當(dāng)前循環(huán)處理元素
                            //pred 表示當(dāng)前循環(huán)節(jié)點的上一個節(jié)點
                            Node<K,V> e = f, pred = null;
                            for (;;) {
                                //當(dāng)前節(jié)點key
                                K ek;
                                //條件一：e.hash == hash true->說明當(dāng)前節(jié)點的hash與查找節(jié)點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)))) {
                                    //當(dāng)前節(jié)點的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))) {
                                        //刪除 或者 替換

                                        //將當(dāng)前節(jié)點的值 賦值給 oldVal 后續(xù)返回會用到
                                        oldVal = ev;

                                        //條件成立：說明當(dāng)前是一個替換操作
                                        if (value != null)
                                            //直接替換
                                            e.val = value;
                                        //條件成立：說明當(dāng)前節(jié)點非頭結(jié)點
                                        else if (pred != null)
                                            //當(dāng)前節(jié)點的上一個節(jié)點倒淫，指向當(dāng)前節(jié)點的下一個節(jié)點伙菊。
                                            pred.next = e.next;

                                        else
                                            //說明當(dāng)前節(jié)點即為 頭結(jié)點，只需要將 桶位設(shè)置為頭結(jié)點的下一個節(jié)點敌土。
                                            setTabAt(tab, i, e.next);
                                    }
                                    break;
                                }
                                pred = e;
                                if ((e = e.next) == null)
                                    break;
                            }
                        }

                        //條件成立：TreeBin節(jié)點镜硕。
                        else if (f instanceof TreeBin) {
                            validated = true;

                            //轉(zhuǎn)換為實際類型 TreeBin t
                            TreeBin<K,V> t = (TreeBin<K,V>)f;
                            //r 表示 紅黑樹 根節(jié)點
                            //p 表示 紅黑樹中查找到對應(yīng)key 一致的node
                            TreeNode<K,V> r, p;

                            //條件一：(r = t.root) != null 理論上是成立
                            //條件二：TreeNode.findTreeNode 以當(dāng)前節(jié)點為入口，向下查找key（包括本身節(jié)點）
                            //      true->說明查找到相應(yīng)key 對應(yīng)的node節(jié)點返干。會賦值給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)) 成立：說明“對比值”與當(dāng)前p節(jié)點的值 一致
                                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));
                                }
                            }
                        }
                    }
                }
                //當(dāng)其他線程修改過桶位 頭結(jié)點時矩欠，當(dāng)前線程 sync 頭結(jié)點 鎖錯對象時财剖，validated 為false，會進(jìn)入下次for 自旋
                if (validated) {

                    if (oldVal != null) {
                        //替換的值 為null癌淮，說明當(dāng)前是一次刪除操作躺坟，oldVal ！=null 成立该默，說明刪除成功瞳氓，更新當(dāng)前元素個數(shù)計數(shù)器。
                        if (value == null)
                            addCount(-1L, -1);
                        return oldVal;
                    }
                    break;
                }
            }
        }
        return null;
    }