摘要：接下來就來說下我眼中的。鏈表轉(zhuǎn)換為樹的閾值，超過這個(gè)長(zhǎng)度的鏈表會(huì)被轉(zhuǎn)換為紅黑樹，當(dāng)然，不止這一個(gè)條件，在下面的源碼部分會(huì)看到。

源碼部分從HashMap說起是因?yàn)楣P者看了很多遍這個(gè)類的源碼部分，同時(shí)感覺網(wǎng)上很多都是粗略的介紹，有些可能還不正確，最后只能自己看源碼來驗(yàn)證理解，寫下這篇文章一方面是為了促使自己能深入，另一方面也是給一些新人一些指導(dǎo)，不求有功，但求無過。有錯(cuò)誤的地方請(qǐng)?jiān)谠u(píng)論中指出，我會(huì)及時(shí)驗(yàn)證修改，謝謝。

接下來就來說下我眼中的HashMap。

jdk版本：1.8

在深入源碼之前，了解HashMap的整體結(jié)構(gòu)是非常重要的事情，結(jié)構(gòu)也體現(xiàn)出了源碼中一些對(duì)HashMap的操作，結(jié)構(gòu)大致如下：

從上邊的結(jié)構(gòu)圖大家應(yīng)該也能看出來HashMap的實(shí)現(xiàn)結(jié)構(gòu)：數(shù)組+鏈表+紅黑樹。

看下類注釋，直接看源碼部分最好，可能大多數(shù)都看不明白，這里可以看下別人的翻譯：類注釋翻譯。本文中筆者不打算對(duì)紅黑樹部分進(jìn)行講解說明，插入和刪除操作會(huì)引發(fā)各種狀態(tài)，需要做對(duì)應(yīng)的調(diào)整，之后會(huì)多帶帶寫一篇紅黑樹基礎(chǔ)，結(jié)合TreeNode來做講解。

先總結(jié)一些名詞概念方便初學(xué)者理解：

1.桶（bucket）:數(shù)組中存儲(chǔ)元素的位置，參考結(jié)構(gòu)圖，實(shí)際上是數(shù)組中的某個(gè)索引下的元素，這個(gè)元素有可能是樹的根節(jié)點(diǎn)或者鏈表的首節(jié)點(diǎn)，當(dāng)然，理解上還是一個(gè)鏈表或紅黑樹整體當(dāng)成桶
2.bin：桶中的每個(gè)元素，即紅黑樹中的某個(gè)元素或者是鏈表中的某個(gè)元素。

除了上邊的名詞，最好還能去理解下哈希表，可以參考下。HashMap也是對(duì)哈希表的一種實(shí)現(xiàn)，簡(jiǎn)單理解，可以類比數(shù)學(xué)中的求余操作，對(duì)范圍進(jìn)行固定，將大量的數(shù)據(jù)放入一個(gè)有界的范圍中，求余放置，這種操作算是哈希表的一種實(shí)現(xiàn)方式。

下面進(jìn)行源碼部分的說明：

public class HashMap extends AbstractMap
    implements Map, Cloneable, Serializable

繼承AbstractMap
實(shí)現(xiàn)Cloneable接口，提供克隆功能
實(shí)現(xiàn)Serializable接口，支持序列化，方便序列化傳輸

這里有個(gè)有意思的問題：為什么HashMap繼承了AbstractMap還要實(shí)現(xiàn)Map接口？有興趣的可以去看下stackoverflow上的回答：

https://stackoverflow.com/que...

    /**
     * Node數(shù)組的默認(rèn)長(zhǎng)度，16
     */
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

    /**
     * Node數(shù)組的最大長(zhǎng)度，最大擴(kuò)容長(zhǎng)度
     */
 
    /**
     * 默認(rèn)負(fù)載因子
     * 這個(gè)是干嘛的呢？
     * 負(fù)載因子是哈希表在自動(dòng)擴(kuò)容之前能承受容量的一種尺度。
     * 當(dāng)哈希表的數(shù)目超出了負(fù)載因子與當(dāng)前容量的乘積時(shí)，則要對(duì)該哈希表進(jìn)行rehash操作（擴(kuò)容操作）。
     */
    static final float DEFAULT_LOAD_FACTOR = 0.75f;

    /**
     * 鏈表轉(zhuǎn)換為樹的閾值，超過這個(gè)長(zhǎng)度的鏈表會(huì)被轉(zhuǎn)換為紅黑樹，
     * 當(dāng)然，不止這一個(gè)條件，在下面的源碼部分會(huì)看到。
     */
    static final int TREEIFY_THRESHOLD = 8;

    /**
     * 當(dāng)進(jìn)行resize操作時(shí)，小于這個(gè)長(zhǎng)度的樹會(huì)被轉(zhuǎn)換為鏈表       
     */
    static final int UNTREEIFY_THRESHOLD = 6;

    /**
     * 鏈表被轉(zhuǎn)換成樹形的最小容量，
     * 如果沒有達(dá)到這個(gè)容量只會(huì)執(zhí)行resize進(jìn)行擴(kuò)容
     * 可以理解成一種計(jì)算規(guī)則
     */
    static final int MIN_TREEIFY_CAPACITY = 64;
    /**
     * 
     * 第一次使用的時(shí)候進(jìn)行初始化，put操作才會(huì)初始化對(duì)象
     * 調(diào)用構(gòu)造函數(shù)時(shí)不會(huì)初始化，后面源碼可參考
     */
    transient Node[] table;

    /**
     * 
     * entrySet保存key和value 用于迭代
     */
    transient Set> entrySet;

    /**
     * 
     * 存放元素的個(gè)數(shù)，但不等于數(shù)組的長(zhǎng)度
     */
    transient int size;

    /**
     * 
     * 計(jì)數(shù)器，fail-fast機(jī)制相關(guān)，不詳細(xì)介紹，有興趣的自己google下
     * 你可以當(dāng)成一個(gè)在高并發(fā)讀寫操作時(shí)的判斷，舉個(gè)例子：
     * 一個(gè)線程A迭代遍歷a,modCount=expectedModCount值為1，執(zhí)行過程中，一個(gè)線程B修改了a,modCount=2，線程A在遍歷時(shí)判斷了modCount<>expectedModCount,拋錯(cuò)
     * 當(dāng)然，這個(gè)只是簡(jiǎn)單的檢查，并不能得到保證
     */
    transient int modCount;

    /**
     * 
     * 閾值，當(dāng)實(shí)際大小超過閾值（容量*負(fù)載因子）的時(shí)候，會(huì)進(jìn)行擴(kuò)容
     */
    int threshold;

    /**
     * 
     * 負(fù)載因子
     */
    final float loadFactor;

在看方法之前先看下Node實(shí)現(xiàn)：

    /**
     * Node的實(shí)現(xiàn) 
     * 看出來是最多實(shí)現(xiàn)單向鏈表 僅有一個(gè)next引用
     * 比較簡(jiǎn)單明了，應(yīng)該都能看明白
     */
    static class Node implements Map.Entry {
        final int hash;
        final K key;
        V value;
        Node next;

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

        public final K getKey()        { return key; }
        public final V getValue()      { return value; }
        public final String toString() { return key + "=" + value; }

        public final int hashCode() {
            return Objects.hashCode(key) ^ Objects.hashCode(value);
        }

        public final V setValue(V newValue) {
            V oldValue = value;
            value = newValue;
            return oldValue;
        }
        
        /**
         * Map.Entry 判斷類型
         * 鍵值對(duì)進(jìn)行比較 判斷是否相等
         */
        public final boolean equals(Object o) {
            if (o == this)
                return true;
            if (o instanceof Map.Entry) {
                Map.Entry e = (Map.Entry)o;
                if (Objects.equals(key, e.getKey()) &&
                    Objects.equals(value, e.getValue()))
                    return true;
            }
            return false;
        }
    }

在注釋中我會(huì)添加一些標(biāo)記幫助理清流程，同時(shí)方便我后邊總結(jié)對(duì)照和參考（例如A1,A2是同一級(jí)）。

    /**
     * 負(fù)載因子設(shè)置成默認(rèn)值 0.75f
     * A1
     */
    public HashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
    }
    /**
     * 初始數(shù)組長(zhǎng)度設(shè)置，負(fù)載因子默認(rèn)值
     * A2
     */
    public HashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }
    /**
     * 初始長(zhǎng)度和負(fù)載因子設(shè)置
     * A2
     */   
    public HashMap(int initialCapacity, float loadFactor) {
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);
        this.loadFactor = loadFactor;
        // 根據(jù)初始容量設(shè)置閾值
        // 二進(jìn)制操作，比較繞，需要自己好好理解下
        // 這值在resize有用，resize代碼可以注意下，主要是為了區(qū)分是否是有參構(gòu)造函數(shù)還是無參構(gòu)造函數(shù)以便之后的操作
        // 可以參考文章：https://www.cnblogs.com/liujinhong/p/6576543.html
        // 是否有更深層次的考慮筆者還未想到，有大神可以在評(píng)論區(qū)告知我
        this.threshold = tableSizeFor(initialCapacity);
    }
    /**
     * 將m存入當(dāng)前map中
     */  
    public HashMap(Map m) {
        this.loadFactor = DEFAULT_LOAD_FACTOR;
        putMapEntries(m, false);
    }
    /**
     * evict參數(shù)相當(dāng)于占位符，是為了擴(kuò)展性，可以追溯到afterNodeInsertion(evict)，方法是空的
     * 在LinkedHashMap中有實(shí)現(xiàn)，有興趣可以去看看
     */  
    final void putMapEntries(Map m, boolean evict) {
        int s = m.size();
        if (s > 0) {
            /**
             * 判斷table是否已經(jīng)被初始化
             */
            if (table == null) { // pre-size
                // 未被初始化，判斷m中元素的個(gè)數(shù)放入當(dāng)前map中是否會(huì)超出最大容量的閾值
                float ft = ((float)s / loadFactor) + 1.0F;
                int t = ((ft < (float)MAXIMUM_CAPACITY) ?
                         (int)ft : MAXIMUM_CAPACITY);
                // 計(jì)算得到的t大于閾值 閾值設(shè)置
                if (t > threshold)
                    threshold = tableSizeFor(t);
            }
            else if (s > threshold)
                /**
                 * 當(dāng)前map已經(jīng)初始化，并且添加的元素長(zhǎng)度大于閾值，需要進(jìn)行擴(kuò)容操作
                 */  
                resize();
            /**
             * 上邊已經(jīng)初始化并處理好閾值設(shè)置，下面使用entrySet循環(huán)putVal保存m中的Node對(duì)象的key和value
             * 這里有個(gè)重要的地方，
             * putVal的第一個(gè)參數(shù)，hash(key)，map的put操作也是同樣的調(diào)用方式
             * 可以參考文章：https://www.cnblogs.com/liujinhong/p/6576543.html
             * 順便看下源碼上的注釋，主要是減少?zèng)_突和性能上的考慮
             */  
            for (Map.Entry e : m.entrySet()) {
                K key = e.getKey();
                V value = e.getValue();
                putVal(hash(key), key, value, false, evict);
            }
        }
    }
    
    /**
     * 擴(kuò)容操作,重點(diǎn)部分
     * 
     * 如果第一次帶容量參數(shù)時(shí)，創(chuàng)建時(shí)閾值設(shè)置為對(duì)應(yīng)容量的最小的2的N次方（大于等于傳入容量參數(shù)），去看下上邊HashMap(int initialCapacity)，
     * 如果添加一個(gè)元素，會(huì)執(zhí)行resize將閾值設(shè)置為了閾值 * 負(fù)載因子，
     * 比如設(shè)置1000 創(chuàng)建時(shí)閾值threshold=1024，負(fù)載因子默認(rèn)，其他值都未進(jìn)行操作，
     * 添加一個(gè)元素 閾值變?yōu)?024 * 0.75 = 768，創(chuàng)建的Node數(shù)組長(zhǎng)度為1024，size=1,
     * 添加第769個(gè)元素時(shí)，進(jìn)行resize操作，threshold=1536，Node數(shù)組長(zhǎng)度為2048，數(shù)組拷貝到新數(shù)組中，
     * 如果有確認(rèn)的數(shù)據(jù)長(zhǎng)度，不想讓HashMap進(jìn)行擴(kuò)容操作，那么則需要在構(gòu)造時(shí)填上計(jì)算好的數(shù)組容量
     * 強(qiáng)烈建議自己寫代碼debug試試
     */
    final Node[] resize() {
        //oldTab 保存擴(kuò)容前的Node數(shù)組
        Node[] oldTab = table;
        // oldCap null的話即為0，否則就是擴(kuò)容前的Node數(shù)組的容量大小
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
        // 擴(kuò)容前的閾值
        int oldThr = threshold;
        // 擴(kuò)容后的數(shù)組容量（長(zhǎng)度），擴(kuò)容后的閾值
        int newCap, newThr = 0;
        // 1.擴(kuò)容前的數(shù)組不為空
        // B1
        if (oldCap > 0) {
            // 擴(kuò)容前的Node數(shù)組容量大于等于設(shè)置的最大容量，不會(huì)進(jìn)行擴(kuò)容，閾值設(shè)置為Integer.MAX_VALUE
            if (oldCap >= MAXIMUM_CAPACITY) {
                // C1
                threshold = Integer.MAX_VALUE;
                return oldTab;
            }
            // 如果擴(kuò)容前的數(shù)組容量擴(kuò)大為2倍依然沒有超過最大容量，
            // 并且擴(kuò)容前的Node數(shù)組容量大于等于數(shù)組的默認(rèn)容量，
            // 擴(kuò)容后的數(shù)組容量值為擴(kuò)容前的map的容量的2倍，并且擴(kuò)容后的閾值同樣設(shè)置為擴(kuò)容前的兩倍,
            // 反之，則只設(shè)置擴(kuò)容后的容量值為擴(kuò)容前的map的容量的2倍
            // 這里newCap已經(jīng)在條件里賦值了
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)
                // C2
                newThr = oldThr << 1; // double threshold
        }
        // 2.擴(kuò)容前的數(shù)組未初始化并且使用了有參構(gòu)造函數(shù)構(gòu)造
        // 這里在oldCap = 0時(shí)執(zhí)行，這里oldThr > 0說明初始化時(shí)是有參初始化構(gòu)造的map
        // 自己可以試下無參構(gòu)造函數(shù)，threshold的值為0
        // B2
        else if (oldThr > 0) // initial capacity was placed in threshold
            // 使用有參初始化構(gòu)造函數(shù)并且在第一次put操作時(shí)會(huì)進(jìn)入執(zhí)行（去看下put源碼）
            // 擴(kuò)容后的容量大小設(shè)置為原有閾值
            // 例如我上邊的注釋中的例子，這里第一次添加鍵值對(duì)時(shí)容量設(shè)置為了1024
            newCap = oldThr;
        // 3.擴(kuò)容前的數(shù)組未初始化并且使用了無參構(gòu)造函數(shù)構(gòu)造
        // B3
        else {               // zero initial threshold signifies using defaults
            // 擴(kuò)容后的容量 = 默認(rèn)容量，擴(kuò)容后的閾值 = 默認(rèn)容量 * 負(fù)載因子
            // 擴(kuò)容后的容量為16，閾值為12
            newCap = DEFAULT_INITIAL_CAPACITY;
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        }
        /**
         * 上邊設(shè)置了新容量和新的閾值，執(zhí)行到這里，你應(yīng)該發(fā)現(xiàn)只有newThr可能沒被賦值，所以這里要繼續(xù)進(jìn)行一個(gè)操作，來對(duì)newThr進(jìn)行賦值
         * 新閾值等于0，照上邊邏輯：
         * 兩種情況：
         * 1.擴(kuò)容前的node數(shù)組容量有值且擴(kuò)容后容量超過最大值或者原node數(shù)組容量小于默認(rèn)初始容量16
         * 2.使用有參構(gòu)造函數(shù)，第一次put操作時(shí)上邊代碼里沒有設(shè)置newThr
         * D1
         */
        if (newThr == 0) {
            // 應(yīng)該得到的新閾值ft = 新容量 * 負(fù)載因子
            float ft = (float)newCap * loadFactor;
            // 假如新容量小于最大容量并且ft小于最大容量則新的閾值設(shè)置為ft,否則設(shè)置成int最大值
            newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                      (int)ft : Integer.MAX_VALUE);
        }
        // 執(zhí)行到這，擴(kuò)容后的容量和閾值都計(jì)算完畢
        // 閾值設(shè)置為新閾值
        threshold = newThr;
        @SuppressWarnings({"rawtypes","unchecked"})
        // 創(chuàng)建擴(kuò)容后的Node數(shù)組 
        Node[] newTab = (Node[])new Node[newCap];
        // 切換為擴(kuò)容后的Node數(shù)組，此時(shí)還未進(jìn)行將舊數(shù)組拷貝到新數(shù)組
        table = newTab;
        // E1
        if (oldTab != null) {
            // 原有數(shù)組不為空，將原有數(shù)組數(shù)據(jù)拷貝到新數(shù)組中
            for (int j = 0; j < oldCap; ++j) {
                Node e;
                // 非空元素才進(jìn)行賦值
                if ((e = oldTab[j]) != null) {
                    // 原有數(shù)值引用置空，方便GC
                    oldTab[j] = null;
                    if (e.next == null)
                        // 桶對(duì)應(yīng)的Node只有當(dāng)前一個(gè)節(jié)點(diǎn),鏈表長(zhǎng)度為1
                        // 中括號(hào)中計(jì)算原有數(shù)組元素在新數(shù)組中存放的位置，
                        // 為什么這么計(jì)算？
                        // 正常的想，添加了一個(gè)鍵值對(duì)，鍵的hash值（當(dāng)然，這里在HashMap的hash(key)進(jìn)行了統(tǒng)一處理）
                        // 那么長(zhǎng)度是有限的，在這個(gè)有限長(zhǎng)度下如何放置，類比整數(shù)取余操作，
                        // &操作表明只取e.hash的低n位，n是newCap - 1轉(zhuǎn)換成二進(jìn)制的有效位數(shù)
                        // 這里記得初始不設(shè)長(zhǎng)度時(shí)默認(rèn)16，二進(jìn)制為10000，減一為1111，低4位
                        // 設(shè)置長(zhǎng)度時(shí)tableSizeFor重新設(shè)置了長(zhǎng)度和16處理類似
                        // 通過&操作所有添加的鍵值對(duì)都分配到了數(shù)組中，當(dāng)然，分配到數(shù)組中同一個(gè)位置時(shí)會(huì)擴(kuò)展成鏈表或紅黑樹
                        // 添加詳細(xì)操作看后邊putVal源碼，這里先不用糾結(jié)
                        newTab[e.hash & (newCap - 1)] = e;
                    else if (e instanceof TreeNode)
                        // 到此說明e.next不為空，那么需要判斷了，
                        // 因?yàn)橛袃煞N結(jié)構(gòu)，一種是鏈表，一種為紅黑樹
                        // 這里先進(jìn)行紅黑樹處理，樹的具體處理后邊有時(shí)間多帶帶做一章進(jìn)行說明講解，
                        // 這里先簡(jiǎn)單了解，擴(kuò)容之后，需要對(duì)原有的樹進(jìn)行處理，使得數(shù)據(jù)分散比較均勻。
                        ((TreeNode)e).split(this, newTab, j, oldCap);
                    else { // preserve order
                        /**
                         * 到這里結(jié)合HashMap的結(jié)構(gòu)，
                         * 排除上邊兩個(gè)條件，這里就進(jìn)行鏈表結(jié)構(gòu)的處理
                         * 進(jìn)行鏈表復(fù)制操作
                         * 復(fù)制的時(shí)候就有個(gè)問題了，舉個(gè)例子，原來我是16，現(xiàn)在擴(kuò)容成了32（原數(shù)組兩倍，我上邊分析里有說明）
                         * 那么我復(fù)制時(shí)怎么辦？
                         * 不移動(dòng)原來的鏈表？
                         * 這里就要想到了我擴(kuò)容之后訪問的時(shí)候不能影響
                         * 那么就需要看下put操作時(shí)是怎樣存的，這里先說下，putVal里也可以看到
                         * (n - 1) & hash 和上邊newTab[e.hash & (newCap - 1)] 分析是一樣的
                         * 這里不知道你想到了嗎？擴(kuò)容之后有什么不同？
                         * 如果還沒什么想法，請(qǐng)繼續(xù)往下看，我等下會(huì)說明
                         * 新擴(kuò)容部分頭尾節(jié)點(diǎn)（hi可以理解成高位）設(shè)置為hiHead,hiTail
                         * 原有部分頭尾節(jié)點(diǎn)（lo可以理解成低位）設(shè)置為loHead,loTail
                         * 這里什么意思呢？
                         * 往下看就好，我下面的注釋詳細(xì)說明了為什么定義了兩個(gè)鏈表頭尾節(jié)點(diǎn)
                         */
                        Node loHead = null, loTail = null;
                        Node hiHead = null, hiTail = null;
                        Node next;
                        // 這里循環(huán)獲取鏈表元素進(jìn)行處理
                        do {
                            next = e.next;
                            /**
                             * e.hash & oldCap = 0
                             * 位與操作，這里初學(xué)者要自己寫下多理解下
                             * 舉個(gè)例子：
                             * oldCap=32=100000（二進(jìn)制），newCap=64=1000000（二進(jìn)制）
                             * 在未擴(kuò)容之前計(jì)算元素所處位置是(oldCap-1) & hash
                             * 全1位與操作，取值范圍落在0~oldCap-1
                             * e.hash & oldCap 只判斷了最高位的那個(gè)1位置是否相同
                             * 相同則非0，不同則為0
                             * 為什么要判斷這一位呢？
                             * 我們想一想，擴(kuò)容之后，計(jì)算bucket（桶）位置（即元素落在數(shù)組那個(gè)索引位置）時(shí)
                             * (newCap-1) & hash和(oldCap-1) & hash兩者對(duì)比，只有一位不同
                             * 比如32和64，最高位是1不同，其他位相同
                             * 如果擴(kuò)容之后最高位為0，則擴(kuò)容前后得到的bucket位置相同，不需要調(diào)整位置
                             * 如果非0，則是1，則需要將桶位置調(diào)整到更高的索引位置
                             * 而且這里也應(yīng)該明白，同一個(gè)bucket下的鏈表（非單一元素）在擴(kuò)容后
                             * 因?yàn)橹挥幸晃欢M(jìn)制不同，不是1就是0
                             * 最多分到兩個(gè)bucket中，一個(gè)是擴(kuò)容前的bucket（當(dāng)前所在的bucket），
                             * 一個(gè)是擴(kuò)容后的bucket（新的bucket），
                             * 這里也說明了上邊為什么設(shè)置了兩組頭尾節(jié)點(diǎn)，一組低位鏈表，一組高位鏈表
                             * 擴(kuò)容前后兩個(gè)bucket位置之間差值為原數(shù)組容量值
                             * 上邊32和64，差值為63-31=32=oldCap=10000（二進(jìn)制）
                             * 所以這下面使用的是oldCap
                             */
                            if ((e.hash & oldCap) == 0) {
                                // 說明當(dāng)前Node元素位置 = 原數(shù)組中的位置
                                // 放入loHead,loTail這一組中，低位鏈表
                                if (loTail == null)
                                    // 鏈表還未放元素，鏈表頭賦值
                                    loHead = e;
                                else
                                    // 鏈表存在元素，新元素放置在鏈表尾部，next指向新元素
                                    loTail.next = e;
                                // 尾節(jié)點(diǎn)指向改變，變成了新添加的節(jié)點(diǎn)
                                loTail = e;
                            }
                            else {
                                // 類似上邊
                                if (hiTail == null)
                                    hiHead = e;
                                else
                                    hiTail.next = e;
                                hiTail = e;
                            }
                        } while ((e = next) != null);
                        
                        // 上面已經(jīng)處理完了，分成了高低位兩個(gè)鏈表，下面就是將這兩個(gè)鏈表放置擴(kuò)容后的新數(shù)組中
                        if (loTail != null) {
                            // 低位鏈表不為空，添加到新數(shù)組，尾節(jié)點(diǎn)next指向置空，因?yàn)樵泄?jié)點(diǎn)可能還存在next指向
                            loTail.next = null;
                            // 新數(shù)組j處就是原有數(shù)組j處，這里直接將低位首節(jié)點(diǎn)引用賦值給新數(shù)組節(jié)點(diǎn)
                            newTab[j] = loHead;
                        }
                        if (hiTail != null) {
                            hiTail.next = null;
                            // 這里和我上邊注釋分析是一致的，相差的值即為oldCap，即原數(shù)組的容量
                            newTab[j + oldCap] = hiHead;
                        }
                    }
                }
            }
        }
        return newTab;
    }

    /**
     * put操作方法主體
     * hash，key的hash值，上邊講過，HashMap自己處理過的
     * onlyIfAbsent，是否覆蓋原有值，true,不覆蓋原有值
     * evict，LinkedHashMap實(shí)現(xiàn)afterNodeInsertion方法時(shí)調(diào)用，這里相當(dāng)于占位符的作用
     */    
    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node[] tab; Node p; int n, i;
        // F1
        if ((tab = table) == null || (n = tab.length) == 0)
            // table為空或長(zhǎng)度為0時(shí)，對(duì)table進(jìn)行初始化，上邊已經(jīng)分析過了
            // 這里也說明了第一次初始化是在這里，而不是使用構(gòu)造方法，排除putMapEntries方式
            n = (tab = resize()).length;
        // 判斷當(dāng)前需要存儲(chǔ)的鍵值對(duì)存放到數(shù)組中的位置是否已經(jīng)存在值（鏈表或者紅黑樹）
        // 即是否已經(jīng)有對(duì)應(yīng)key
        // G1
        if ((p = tab[i = (n - 1) & hash]) == null)
            // 不存在，則創(chuàng)建一個(gè)新節(jié)點(diǎn)保存
            tab[i] = newNode(hash, key, value, null);
        // G2
        else {
            // 將桶上的值進(jìn)行匹配，判斷是否存在
            Node e; K k;
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                // 鏈表頭節(jié)點(diǎn)（或紅黑樹根節(jié)點(diǎn)）與當(dāng)前需要保存的hash值相等
                // 并且key值相等，e和p是同一個(gè)，說明添加了相同的key
                // e指向p對(duì)應(yīng)的節(jié)點(diǎn)
                e = p;
            else if (p instanceof TreeNode)
                // 紅黑樹添加節(jié)點(diǎn)處理，本文不詳細(xì)將紅黑樹部分，后面有空會(huì)多帶帶抽出講解
                // 返回值可以理解成如果有相同key,則返回對(duì)應(yīng)Node,否則返回null(創(chuàng)建了新的Node)
                e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);
            else {
                // 這里說明非頭節(jié)點(diǎn)（數(shù)組中對(duì)應(yīng)的桶的第一個(gè)節(jié)點(diǎn)），非紅黑樹結(jié)構(gòu)，
                // 說明需要匹配鏈表，判斷鏈表中對(duì)應(yīng)的key是否已存在
                // 設(shè)置binCount計(jì)算當(dāng)前桶中bin的數(shù)量，即鏈表長(zhǎng)度
                for (int binCount = 0; ; ++binCount) {
                    if ((e = p.next) == null) {
                        // next 為空 無下一個(gè)元素 不再繼續(xù)查找 直接新創(chuàng)建直接賦值next
                        p.next = newNode(hash, key, value, null);
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            // 判斷是否樹化，這里就是鏈表樹化條件，在treeifyBin還有個(gè)數(shù)組容量判斷，方法也可能只進(jìn)行擴(kuò)容操作
                            // 總結(jié)下，即桶中bin數(shù)量大于等于TREEIFY_THRESHOLD=8，數(shù)組容量不能小于MIN_TREEIFY_CAPACITY=64時(shí)進(jìn)行樹化轉(zhuǎn)化
                            // 怎么轉(zhuǎn)成紅黑樹結(jié)構(gòu)這里也不做深入，后續(xù)會(huì)進(jìn)行說明
                            treeifyBin(tab, hash);
                        break;
                    }
                    // 不為空 且節(jié)點(diǎn)為尋找的節(jié)點(diǎn) 終止循環(huán)
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            // 上邊已經(jīng)檢查完map中是否存在對(duì)應(yīng)key的Node節(jié)點(diǎn)，不存在的新創(chuàng)建節(jié)點(diǎn)，這里處理下存在對(duì)應(yīng)key的節(jié)點(diǎn)數(shù)據(jù)
            // H1
            if (e != null) { // existing mapping for key
                // 保存下原來的節(jié)點(diǎn)值
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    // onlyIfAbsent 是否需要覆蓋操作，是則覆蓋
                    e.value = value;
                // 子類實(shí)現(xiàn)方法的話可以進(jìn)行對(duì)應(yīng)的后置操作
                afterNodeAccess(e);
                // 返回原值
                return oldValue;
            }
        }
        ++modCount;
        // 實(shí)際元素長(zhǎng)度，不是容量，是每次添加一個(gè)新的鍵值對(duì)會(huì)加1，覆蓋不增加
        // 判斷是否大于閾值，進(jìn)行擴(kuò)容操作
        // I1
        if (++size > threshold)
            resize();
        // 同afterNodeAccess，子類實(shí)現(xiàn)方法的話可以進(jìn)行對(duì)應(yīng)的后置操作
        afterNodeInsertion(evict);
        return null;
    }

重點(diǎn)的部分也就是在上面這幾個(gè)方法，剩下的源碼部分就不一一貼出來分析了，能看懂我上面說明的部分，基本上除了紅黑樹和jdk1.8的新特性相關(guān)部分，其余部分應(yīng)該基本都能看懂，這里再補(bǔ)充一個(gè)序列化方面的問題：

為什么HashMap中的table變量要設(shè)置為transient？在理解這個(gè)問題之前，自行去看下序列化代碼writeObject和readObject，然后參考以下鏈接來思考：

https://segmentfault.com/q/10...

HashMap中，由于Entry的存放位置是根據(jù)Key的Hash值來計(jì)算，然后存放到數(shù)組中的，對(duì)于同一個(gè)Key，在不同的JVM實(shí)現(xiàn)中計(jì)算得出的Hash值可能是不同的。這里不同意思是說我原來在window機(jī)器上A是放在Node數(shù)組中0的位置，在Mac上可能是放在Node數(shù)組中5的位置，但是不修改的話，反序列化之后Mac上也是0的位置，這樣導(dǎo)致后續(xù)增加節(jié)點(diǎn)會(huì)錯(cuò)亂，不是我們想要的結(jié)果，故在序列化中HashMap對(duì)每個(gè)鍵值對(duì)的鍵和值序列化，而不是整體，反序列化一個(gè)一個(gè)取出來，不會(huì)造成位置錯(cuò)亂。

那么JDK1.8中HashMap在多線程環(huán)境下會(huì)造成死循環(huán)嗎？

從上邊結(jié)構(gòu)以及處理過程的分析來看，應(yīng)該是不會(huì)的，只不過數(shù)據(jù)丟失還是會(huì)發(fā)生，這一塊我就不進(jìn)行驗(yàn)證了，自行Google，手寫代碼來驗(yàn)證。同時(shí)想多說句，對(duì)于一般開發(fā)人員知道HashMap是非線程安全的，多線程情況下使用ConcurrentHashMap即可，后邊有時(shí)間ConcurrentHashMap的分析我也會(huì)整理出來。

在重點(diǎn)說明部分我已經(jīng)詳細(xì)解釋了resize和put操作的過程，可能有些新人還是不能梳理清楚，我在這里結(jié)合下日常使用總結(jié)下整個(gè)過程，方便各位理解：

1.HashMap創(chuàng)建過程（正常狀態(tài)）：

2.HashMap resize過程（正常狀態(tài)）：

3.HashMap put過程（正常狀態(tài)）：

HashMap首先需要理解清楚其內(nèi)部的實(shí)現(xiàn)結(jié)構(gòu)：數(shù)組+鏈表+紅黑樹，在結(jié)構(gòu)的基礎(chǔ)之上來對(duì)源碼進(jìn)行深入，resize和put操作是最為重要的兩部分，理解了這兩塊，基本上對(duì)HashMap的整體處理過程有了一定的認(rèn)知，另外，一定要自己動(dòng)手debug，理清數(shù)據(jù)的轉(zhuǎn)換，對(duì)了解HashMap有很大的幫助。

文章先從基礎(chǔ)部分說起，解釋了一些名詞，提及了哈希表，從實(shí)現(xiàn)結(jié)構(gòu)開始來幫助各位更好的理解源碼操作部分，對(duì)重點(diǎn)的幾個(gè)部分做出詳細(xì)的說明，resize和put操作難點(diǎn)部分也做了相應(yīng)的解釋，希望對(duì)各位有所幫助，后邊有空我會(huì)將紅黑樹部分的理解分享出來，謝謝。