是時候來了解JDK8 HashMap的實現(xiàn)原理了

一 HashMap底層存儲結(jié)構(gòu)

hashmap.png

? ? ? ?HashMap底層結(jié)構(gòu)采用（數(shù)組）+（鏈表 or 紅黑樹）的形式來存儲節(jié)點慈缔。

首先HashMap是一個數(shù)組，而且數(shù)組里面每個位置可以放入多個元素檀夹，形象一點铭拧，咱們把數(shù)組的這些個位置稱為桶。HashMap里面每個元素通過key值取hash在 & （數(shù)組長度容量-1）就可以唯一確定該元素屬于哪個桶。
HashMap為了最大限度的提高效率论熙，在桶的設計上也是相當?shù)木佟Ｍ翱赡苁擎湵硪部赡苁羌t黑樹摄狱。開始桶里面元素不多的時候采用鏈表形式保存脓诡。后續(xù)隨著HashMap里面的元素越來越多，桶里面里面的元素元素也越來越多媒役，當元素個數(shù)>8（TREEIFY_THRESHOLD）并且數(shù)組的長度>64（MIN_TREEIFY_CAPACITY）的時候誉券，會把鏈表變成紅黑樹（樹化）；如果桶當前采用的是紅黑樹保存節(jié)點元素信息隨著節(jié)點個數(shù)的減少（HashMap remove操作）刊愚，當節(jié)點元素個數(shù)<6（UNTREEIFY_THRESHOLD）的時候踊跟，又會把紅黑樹降級為鏈表。

? ? ? ?看到這里鸥诽，咱們可能會想了商玫，HashMap的桶有了鏈表為啥還要轉(zhuǎn)換為紅黑樹？HashMap源碼大神考慮到鏈表太長的話牡借。節(jié)點元素的查找效率不高拳昌。所以有鏈表轉(zhuǎn)紅黑樹，紅黑樹轉(zhuǎn)鏈表的操作钠龙【嫣伲可能你又會想為啥不用平衡二叉樹來替換紅黑樹御铃。那是因為HashMap源碼大神兼顧了節(jié)點的插入刪除效率和節(jié)點的查詢效率。紅黑樹不追求"完全平衡"沈矿。所以往紅黑樹里面插入或者刪除節(jié)點的時候任何不平衡都會在三次旋轉(zhuǎn)之內(nèi)解決上真。而平衡二叉樹插入或者刪除節(jié)點的時候為了追求完全平衡，旋轉(zhuǎn)的次數(shù)是不固定的羹膳，花費的時間跟多睡互。(關(guān)于紅黑樹和平衡二叉樹的更多知識，大家可以自行去百度下陵像，我們這里就不具體展開了就珠，里面還是挺有趣的)

二 HashMap源碼分析

image-20200626155911680.png

? ? ? ?了解了HashMap的存儲結(jié)構(gòu)之后，咱們著重對HashMap添加節(jié)點的過程做一個簡單的分析醒颖。我相信只要咱們搞懂了HashMap里面添加元素的過程妻怎。HashMap里面大部分的實現(xiàn)邏輯咱們都能搞懂。因為HashMap中最關(guān)鍵的部分（擴容泞歉、樹化）在HashMap添加元素過程中都很好的體現(xiàn)出來了蹂季。這里我們先給出HashMap添加元素的簡單流程圖（HashMap里面putVal()函數(shù)流程圖）。

HashMap流程圖.png

? ? ? ?上面流程圖里面有幾個重要的地方是我們需要重點關(guān)注的：resize()擴容疏日，treeifyBin()樹化。下面我們對resize()擴容撒汉，treeifyBin()樹化的具體邏輯做一個簡單的分析沟优。

2.1 準備工作

HashMap里面一些關(guān)鍵屬性介紹

/**
* 默認初始容量(默認數(shù)組桶的個數(shù))16-必須為2的冪。
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

/**
* 最大容量2的30次方睬辐。桶的最大個數(shù)
*/
static final int MAXIMUM_CAPACITY = 1 << 30;

/**
* 構(gòu)造函數(shù)中未指定時使用的負載系數(shù)挠阁，
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;

/**
* 桶結(jié)構(gòu)樹化需要兩個條件
* 1. 桶里面元素個數(shù)大于TREEIFY_THRESHOLD
* 2. 桶的個數(shù)(數(shù)組的長度)大于MIN_TREEIFY_CAPACITY
*/
static final int TREEIFY_THRESHOLD = 8;

/**
* 如果當前桶采用的是紅黑樹保存節(jié)點，當桶里面的元素小于該值時溯饵，紅黑樹降級為鏈表侵俗。
*/
static final int UNTREEIFY_THRESHOLD = 6;

/**
* 桶結(jié)構(gòu)樹化需要兩個條件
* 1. 桶里面元素個數(shù)大于TREEIFY_THRESHOLD
* 2. 桶的個數(shù)(數(shù)組的長度)大于MIN_TREEIFY_CAPACITY
*/
static final int MIN_TREEIFY_CAPACITY = 64;

/**
* HashMap數(shù)組。長度必須是2的冪次方
*/
transient Node<K,V>[] table;

/**
* HashMap中所有元素節(jié)點的個數(shù)
*/
transient int size;

/**
* 擴容（重hash）或者map結(jié)構(gòu)修改的次數(shù)
*/
transient int modCount;

/**
* 擴容閾值【當HashMap的所有元素個數(shù)大于threashold時會進行擴容操作】丰刊，threshold=容量*loadFactor(裝載因子)
*/
int threshold;

/**
* 裝載因子隘谣，用來衡量HashMap滿的程度。默認為0.75f
*/
final float loadFactor;

HashMap容量(數(shù)組大小啄巧，桶的個數(shù))永遠是2的整數(shù)次冪

? ? ? ?時時刻刻要記住HashMap的容量(桶的個數(shù))永遠是2的整數(shù)次冪寻歧。初始容量16，每次擴容之后的容量都是前一次容量的兩倍秩仆。比如當前容量是16擴容一次編程32码泛，再擴容一次變成64。

? ? ? ?而且如果我們在new HashMap的時候澄耍，給了初始容量噪珊，但是給定的容量不是2的整數(shù)次冪晌缘，構(gòu)造函數(shù)內(nèi)部也會調(diào)用tableSizeFor()函數(shù)轉(zhuǎn)換成2的整數(shù)次冪的。比如：傳遞3會轉(zhuǎn)換成4痢站，傳遞13會轉(zhuǎn)換成16磷箕。

/**
* 返回大于輸入?yún)?shù)且最近的2的整數(shù)次冪的數(shù)
* 比如 cap = 2 的時候返回 2
*     cap = 3 的時候返回 4
*     cap = 9 的時候返回 16
*/
static final int tableSizeFor(int cap) {
    int n = cap - 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;
}

HashMap里面的元素桶的位置是怎么確定的(HashMap元素在數(shù)組中的索引位置)

? ? ? ?很簡單通過對元素的key做hash處理在 &（容量-1），就可以精確找到找個這個元素應該放入哪個桶中瑟押。

2.2 resize()擴容

? ? ? ?一定要時刻記住HashMap的容量(數(shù)組的大小搀捷，我們也說桶的個數(shù))永遠都是2的整數(shù)次冪，擴容就是把容量擴大一倍多望。擴容之后的容量=原來容量*2嫩舟。（桶的個數(shù)翻倍）就算你new HashMap()的時候給定的容量不是2的整數(shù)次冪。HashMap內(nèi)部也是會通過tableSizeFor()函數(shù)把容量轉(zhuǎn)換成2的整數(shù)次冪怀偷。

? ? ? ?HashMap確定元素屬于哪個桶是通過對該元素的key取hash之后再 & （容量-1）家厌。這樣就找到了桶的位置（其實是數(shù)組的下標）。

? ? ? ?擴容前后桶的關(guān)系也要特別注意椎工，擴容前屬于同一個桶(桶的索引位置相同)里面的元素饭于，在擴容之后只會有兩個桶來放他們：要不還保留擴容前的桶的索引位置，要不就是通過擴容前的索引位置+擴容前的容量得和值確定位置维蒙。我們舉個例子掰吕，假設原來的容量是16，那么擴容之后的容量就是32颅痊。假設原來桶的位置為index殖熟。那么這個桶里面的元素只會去到擴容之后桶的index位置，或者桶的index+16位置斑响。為什么會有這樣的規(guī)律菱属，關(guān)鍵在容量永遠都是2的整數(shù)次冪。而且擴容是*2的擴容舰罚。為了加深大家的理解纽门，我用一個圖例來說明。

HashMap擴容.png

? ? ? ?有了上面的理解营罢，接下來赏陵，我們看HashMap的擴容邏輯就簡單了，我們就直接貼代碼饲漾，加注釋了瘟滨。

/**
* HashMap擴容函數(shù)
* 1. 容量，擴容闕值等都相應的擴大兩倍
* 2. 擴容前每個桶里面的元素能颁，重新放入擴容之后對應桶里面
*/
final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;// 擴容前容量(擴容前桶的個數(shù))
    int oldThr = threshold; // 擴容前閾值
    int newCap, newThr = 0; // 擴容后容量杂瘸，擴容后閾值
    if (oldCap > 0) {
        if (oldCap >= MAXIMUM_CAPACITY) {
            // 如果擴容前容量大于最大容量
            threshold = Integer.MAX_VALUE; // 閾值設置為最大值
            return oldTab; // 直接返回不需要擴容
        }
        // 擴容，容量伙菊，閾值都擴大一倍
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold
    }
    else if (oldThr > 0) // initial capacity was placed in threshold
        // 初始容量設置為閾值
        newCap = oldThr;
    else {               // 零初始閾值表示使用默認值
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    if (newThr == 0) {
        // 如果擴容后的閾值等于0败玉，重新計算擴容后的閾值 = 擴容后的容量*默認擴容因子
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    threshold = newThr; // 擴容后的閾值賦值給閾值
    @SuppressWarnings({"rawtypes","unchecked"})
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; // 創(chuàng)建擴容之后的桶數(shù)組
    table = newTab; // 賦值給table
    if (oldTab != null) {
        // 遍歷擴容之前的桶數(shù)組敌土，遍歷擴容前的每個桶
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            // 如果擴容之前的桶里面有元素
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null;
                if (e.next == null)
                    // 擴容前桶里面只有一個元素，直接放到新數(shù)組中(是可以直接放的运翼，因為不會有別的桶的元素放到這個位置的)
                    newTab[e.hash & (newCap - 1)] = e;
                else if (e instanceof TreeNode)
                    // 擴容前桶是紅黑樹返干，做對應紅黑樹的拆分處理
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                else { // preserve order
                    // 擴容前桶是鏈表，這里要再次強調(diào)下血淌，擴容前同一個桶里面的元素矩欠，擴容之后只會往兩個桶放這些元素，我們前面講的很清楚悠夯。要不就是還是保留原來的索引位置癌淮，要不就是原來的索引位置在加上擴容前的容量
                    Node<K,V> loHead = null, loTail = null; // 保留擴容前索引位置的，頭和尾
                    Node<K,V> hiHead = null, hiTail = null; // 擴容索引位置+擴容前容量的位置沦补，頭和尾
                    Node<K,V> next;
                    do {
                        next = e.next;
                        if ((e.hash & oldCap) == 0) { // 擴容后桶的索引位置還是擴容前索引位置
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        }
                        else { // 擴容后桶的索引位置 = 擴容前索引位置 + 擴容前容量
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;// 把鏈表的頭告訴桶
                    }
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;// 把鏈表的頭告訴桶
                    }
                }
            }
        }
    }
    return newTab;
}

/**
* 紅黑樹的拆分處理
*/
final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
    TreeNode<K,V> b = this;
    // Relink into lo and hi lists, preserving order
    /*
    這里需要再次強調(diào)一點乳蓄，在擴容的過程中，桶一個桶里面的元素夕膀，在擴容之后只會在兩個位置虚倒，要么還是保留擴容前桶索引位置，要么去到擴容前桶索引位置+擴容前容量
    什么意思产舞，我們舉個例子魂奥。假設原來的HashMap的數(shù)組長度是16，那么擴容之后的數(shù)組的長度是32
    在比如這個時候易猫，擴容前HashMap耻煤，數(shù)組下標3里面的所有的元素。在擴容之后擦囊。要么在擴容之后數(shù)組下標3里面要么在下標 3+16=19里面
    */
    TreeNode<K,V> loHead = null, loTail = null; // 低位(還是放入擴容器前桶的索引位置)，loHead首節(jié)點嘴办，loTail尾節(jié)點
    TreeNode<K,V> hiHead = null, hiTail = null; // 高位(放入擴容前桶索引位置+擴容前容量)瞬场，hiHead首節(jié)點，hiTail尾節(jié)點
    int lc = 0, hc = 0;
    /*
    先把紅黑樹里面的每個元素涧郊，找到對應的數(shù)組的數(shù)組下標贯被，并且組成一個雙向鏈表
    */
    for (TreeNode<K,V> e = b, next; e != null; e = next) {
        next = (TreeNode<K,V>)e.next;
        e.next = null;
        if ((e.hash & bit) == 0) { // 擴容之后還是保留原來的索引位置
            if ((e.prev = loTail) == null)
                loHead = e;
            else
                loTail.next = e;
            loTail = e;
            ++lc;
        }
        else { // 擴容之后去到 擴容前索引位置+擴容前容量
            if ((e.prev = hiTail) == null)
                hiHead = e;
            else
                hiTail.next = e;
            hiTail = e;
            ++hc;
        }
    }

    if (loHead != null) {
        if (lc <= UNTREEIFY_THRESHOLD)
            // 如果loHead上的樹節(jié)點小于等于6個那就去樹化變回鏈表
            tab[index] = loHead.untreeify(map);
        else {
            tab[index] = loHead;
            if (hiHead != null) // (else is already treeified)
                // 轉(zhuǎn)換成紅黑樹
                loHead.treeify(tab);
        }
    }
    if (hiHead != null) {
        if (hc <= UNTREEIFY_THRESHOLD)
            // 如果loHead上的樹節(jié)點小于等于6個那就去樹化變回鏈表
            tab[index + bit] = hiHead.untreeify(map);
        else {
            tab[index + bit] = hiHead;
            if (loHead != null)
                // 轉(zhuǎn)換成紅黑樹
                hiHead.treeify(tab);
        }
    }
}

2.3 treeifyBin()樹化

? ? ? ?HashMap的樹化，就是把鏈表轉(zhuǎn)換為紅黑樹妆艘。當往HashMap里面添加元素的時候彤灶，隨著桶里面元素的增加，當桶里面元素的個數(shù)大于8（TREEIFY_THRESHOLD）批旺，并且HashMap的容量大于64（MIN_TREEIFY_CAPACITY）的時候才會把鏈表樹化成紅黑樹幌陕。先轉(zhuǎn)換成二叉樹，在對二叉樹做紅黑樹的平衡旋轉(zhuǎn)處理汽煮。關(guān)于紅黑樹的原理搏熄，建議大家去網(wǎng)上找一些資料看看棚唆，還是挺有意思的。

紅黑樹特性

左子節(jié)點小于右子節(jié)點心例。（方便搜索）
節(jié)點是紅色或者黑色宵凌。
根節(jié)點是黑色。
每個葉子的節(jié)點都是黑色的空節(jié)點（NULL）止后。
每個紅色節(jié)點的兩個子節(jié)點都是黑色瞎惫。（從每個葉子節(jié)點到根節(jié)點的所有路徑上不能有兩個連續(xù)的紅色節(jié)點）
從任一節(jié)點到其每個葉子節(jié)點的所有路徑都包含相同數(shù)目的黑色節(jié)點。

/**
* treeifyBin方法用于把桶的兩遍轉(zhuǎn)換為紅黑樹
*/
final void treeifyBin(Node<K,V>[] tab, int hash) {
    int n, index; Node<K,V> e;
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
        // 雖然桶里面的元素大于8了译株，但是容量還沒到到64（MIN_TREEIFY_CAPACITY）瓜喇，還是進行擴容
        resize();
    else if ((e = tab[index = (n - 1) & hash]) != null) {
        TreeNode<K,V> hd = null, tl = null; // hd首節(jié)點，tl尾節(jié)點
        do {
            // Entry做結(jié)構(gòu)轉(zhuǎn)換每個節(jié)點都轉(zhuǎn)換成TreeNode古戴，先組成一個雙向鏈表(每個節(jié)點都有prev,next)
            TreeNode<K,V> p = replacementTreeNode(e, null);
            if (tl == null)
                hd = p;
            else {
                p.prev = tl;
                tl.next = p;
            }
            tl = p;
        } while ((e = e.next) != null);
        // 上面部分組成了一個雙向鏈表(每個節(jié)點都有prev,next)
        // 把組成的雙向鏈表欠橘，紅黑樹樹化，轉(zhuǎn)換成一個紅黑樹
        if ((tab[index] = hd) != null)
            hd.treeify(tab);
    }
}

/**
* 紅黑樹的樹化過程
*/
final void treeify(Node<K,V>[] tab) {
    TreeNode<K,V> root = null; // 紅黑樹的根節(jié)點
    /*
    依次遍歷现恼，雙向鏈表的每個節(jié)點肃续。root是組成之后紅黑樹的根節(jié)點，
    x是當前想放入紅黑樹的節(jié)點叉袍，next是下一個想放入紅黑樹的節(jié)點
    */
    for (TreeNode<K,V> x = this, next; x != null; x = next) {
        next = (TreeNode<K,V>)x.next;
        x.left = x.right = null; // 當前操作節(jié)點的左節(jié)點始锚，右節(jié)點清空
        if (root == null) {
            // 處理第一個節(jié)點
            x.parent = null;
            x.red = false;
            root = x;
        }
        else {
            K k = x.key; // 準備放入紅黑樹節(jié)點對應的key
            int h = x.hash; // 準備放入紅黑樹節(jié)點對應的hash
            Class<?> kc = null;
            for (TreeNode<K,V> p = root;;) { // 從紅黑樹的根節(jié)點開始遍歷，p是紅黑樹中當前遍歷到的節(jié)點
                int dir, ph; // dir:-1或0 左孩子喳逛，1 右孩子(紅黑樹也是二叉樹瞧捌，要保證左孩子小于右孩子)
                K pk = p.key;
                /*
                比較hash的大小，紅黑樹也是二叉樹润文，要保證左孩子小于右孩子
                */
                if ((ph = p.hash) > h) // 紅黑樹遍歷到的節(jié)點的hash大于當前準備放入節(jié)點的hash姐呐。所以需要放入的節(jié)點肯定放在紅黑樹遍歷到的當前節(jié)點的左孩子里面
                    dir = -1;
                else if (ph < h) // 紅黑樹遍歷到的節(jié)點的hash小于當前準備放入節(jié)點的hash。所以需要放入的節(jié)點肯定放在紅黑樹遍歷到的當前節(jié)點的右孩子里面
                    dir = 1;
                else if ((kc == null &&
                          (kc = comparableClassFor(k)) == null) ||
                         (dir = compareComparables(kc, k, pk)) == 0) // 相等的情況下典蝌，左其他方式的比較
                    dir = tieBreakOrder(k, pk);

                TreeNode<K,V> xp = p;
                /*
                找到需要放入紅黑樹節(jié)點的位置曙砂，
                */
                if ((p = (dir <= 0) ? p.left : p.right) == null) {
                    x.parent = xp;
                    if (dir <= 0)
                        xp.left = x; // 左孩子
                    else
                        xp.right = x; // 右孩子
                    root = balanceInsertion(root, x); // 紅黑樹平衡操作-其實上面一大段還只是形成了二叉樹，只有對二叉樹做了紅黑樹的平衡操作骏掀，才能成為紅黑樹
                    break;
                }
            }
        }
    }
    moveRootToFront(tab, root);
}

/**
紅黑樹的平衡算法鸠澈，當樹結(jié)構(gòu)中新插入了一個節(jié)點后，要對樹進行重新的結(jié)構(gòu)化截驮，以保證樹始終維持紅黑樹特性
*/
static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root,
                                            TreeNode<K,V> x) {
    x.red = true; // 新插入的節(jié)點標記為紅色節(jié)點
    /*
    這一步即定義了變量笑陈，又開啟了循環(huán)，循環(huán)沒有控制條件葵袭，只能從內(nèi)部跳出
    xp：父節(jié)點涵妥、xpp：爺爺節(jié)點、xppl：左叔叔節(jié)點坡锡、xppr：右叔叔節(jié)點
    */
    for (TreeNode<K,V> xp, xpp, xppl, xppr;;) {
        // 如果父節(jié)點為空妹笆、說明當前節(jié)點就是根節(jié)點块请，那么把當前節(jié)點標為黑色，返回當前節(jié)點
        if ((xp = x.parent) == null) {
            x.red = false;
            return x;
        }
        else if (!xp.red || (xpp = xp.parent) == null)
            return root;
        if (xp == (xppl = xpp.left)) { // 父節(jié)點是爺爺節(jié)點的左孩子
            if ((xppr = xpp.right) != null && xppr.red) { // 如果右叔叔不為空 并且 為紅色
                xppr.red = false; // 右叔叔置為黑色
                xp.red = false; // 父節(jié)點置為黑色
                xpp.red = true; // 爺爺節(jié)點置為紅色
                x = xpp;
            }
            else { // 如果右叔叔為空 或者 為黑色
                if (x == xp.right) { // 如果當前節(jié)點是父節(jié)點的右孩子
                    root = rotateLeft(root, x = xp); // 父節(jié)點左旋
                    xpp = (xp = x.parent) == null ? null : xp.parent; // 獲取爺爺節(jié)點
                }
                if (xp != null) { // 如果父節(jié)點不為空
                    xp.red = false; // 父節(jié)點 置為黑色
                    if (xpp != null) { // 爺爺節(jié)點不為空
                        xpp.red = true; // 爺爺節(jié)點置為 紅色
                        root = rotateRight(root, xpp); //爺爺節(jié)點右旋
                    }
                }
            }
        }
        else { // 父節(jié)點是爺爺節(jié)點的右孩子
            if (xppl != null && xppl.red) { // 如果左叔叔是紅色
                xppl.red = false; // 左叔叔置為 黑色
                xp.red = false; // 父節(jié)點置為黑色
                xpp.red = true; // 爺爺置為紅色
                x = xpp;
            }
            else { // 如果左叔叔為空或者是黑色
                if (x == xp.left) { // 如果當前節(jié)點是個左孩子
                    root = rotateRight(root, x = xp); // 針對父節(jié)點做右旋
                    xpp = (xp = x.parent) == null ? null : xp.parent; // 獲取爺爺節(jié)點
                }
                if (xp != null) { // 如果父節(jié)點不為空
                    xp.red = false; // 父節(jié)點置為黑色
                    if (xpp != null) { //如果爺爺節(jié)點不為空
                        xpp.red = true; // 爺爺節(jié)點置為紅色
                        root = rotateLeft(root, xpp); // 針對爺爺節(jié)點做左旋
                    }
                }
            }
        }
    }
}

三總結(jié)

? ? ? ?通過對HashMap的實現(xiàn)做簡單的分析拳缠，咱們可以總結(jié)出如下信息：

HashMap的初始容量是16墩新。
HashMap的容量永遠都是2的整數(shù)次冪，擴容之后的容量 = 擴容之前的容量*2窟坐。
HashMap擴容時機海渊，當HashMap里面的元素個數(shù) > 容量 * loadFactor (默認0.75)。
HashMap樹化時機(鏈表轉(zhuǎn)紅黑樹)哲鸳，當桶里面的元素個數(shù) >= 8(TREEIFY_THRESHOLD)臣疑，并且HashMap的容量 > 64(MIN_TREEIFY_CAPACITY)。
HashMap去樹化的時機(紅黑樹轉(zhuǎn)鏈表)徙菠，當紅黑樹里面的元素個數(shù) <= 6(UNTREEIFY_THRESHOLD)讯沈。
HashMap是線程不安全的，我們在分析過程中沒有看到任何線程安全的保障婿奔。

? ? ? ?以上就是對HashMap做的一個簡單分析缺狠，希望對大家有幫助。