[[417785]]

前幾天H同學(xué)和我聊了下去谷歌的面試經(jīng)驗(yàn)，令我詫異的是，沒想到谷歌也問集合之后，我便覺得需要再整理一波集合相關(guān)的了。

看文章前可以先看看以下高頻考點(diǎn)，如果覺得莫得問題，可以直接跳過該篇文章了，不用浪費(fèi)時(shí)間。

• new HashMap() 和 new HashMap(int initialCapacity) ，具體有什么區(qū)別?
• HashMap中的數(shù)據(jù)多于多少個(gè)時(shí)才會(huì)進(jìn)行擴(kuò)容?
• HashMap中的鏈表結(jié)構(gòu)什么時(shí)候轉(zhuǎn)成紅黑樹?一定會(huì)轉(zhuǎn)嗎?
• 紅黑樹結(jié)構(gòu)又什么時(shí)候才會(huì)轉(zhuǎn)回鏈表?
• 說說看HashMap的懶加載?負(fù)載因子的作用?

特征解析

為了搞清楚一個(gè)概念，這篇文章引入竹籃和雞蛋的概念，緩存的數(shù)據(jù)就是雞蛋，而節(jié)點(diǎn)就是竹籃，HashMap底層是一個(gè)竹籃數(shù)組，每個(gè)竹籃是一個(gè)鏈表或者紅黑樹的結(jié)構(gòu)，每個(gè)竹籃也可以放多個(gè)雞蛋，因此其實(shí)可以當(dāng)成二維數(shù)組來看待，只是在這里的第二維數(shù)組是一個(gè)鏈表或者紅黑樹，至于這個(gè)竹籃的結(jié)構(gòu)是鏈表還是紅黑樹，就看竹籃內(nèi)的的雞蛋個(gè)數(shù)有多少，并且鏈表和紅黑樹之間可以進(jìn)行轉(zhuǎn)換。

通過散列函數(shù)將雞蛋定位到表中的具體竹籃，以提升查詢速度，其底層用于存放數(shù)據(jù)的數(shù)組也叫散列表。所謂散列函數(shù)，簡(jiǎn)單來說就是將一個(gè)無限大的集合(在 HashMap 中，key值是一個(gè)無限大集合)，經(jīng)過 hash 運(yùn)算取模，均勻的分布在一個(gè)有限的集合(我們定義的哈希表容量，比如長(zhǎng)度 16 的數(shù)組)

源碼解析

成員變量和常量

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 默認(rèn)的初始容量，預(yù)計(jì)所有竹籃累計(jì)可以放16個(gè)雞蛋 
static final int MAXIMUM_CAPACITY = 1 << 30; // 最大容量，所有竹籃最多可以放多少個(gè)雞蛋 
static final float DEFAULT_LOAD_FACTOR = 0.75f; // 默認(rèn)加載因子，裝逼用，一般都會(huì)在應(yīng)用探討bb的時(shí)候提一嘴 
static final int TREEIFY_THRESHOLD = 8;  // 單個(gè)竹籃放的雞蛋個(gè)數(shù)超過8轉(zhuǎn)紅黑樹 
static final int UNTREEIFY_THRESHOLD = 6; // 單個(gè)竹籃放的雞蛋個(gè)數(shù)小于6則轉(zhuǎn)鏈表 
static final int MIN_TREEIFY_CAPACITY = 64; // 如果竹籃個(gè)數(shù)小于64個(gè)，會(huì)先進(jìn)行擴(kuò)容，而不會(huì)鏈表轉(zhuǎn)紅黑樹 
 
transient Node<K,V>[] table;  // 哈希表數(shù)組，存儲(chǔ)數(shù)據(jù)的地方，每個(gè)竹籃結(jié)構(gòu)可能為鏈表或者紅黑樹，總是2的冪次倍 
transient Set<Map.Entry<K,V>> entrySet; // 存放具體元素的集合，可用于遍歷Map 
transient int size; // 總的雞蛋個(gè)數(shù) 
transient int modCount;  // 插入刪除元素，modCount++,用于記錄改變次數(shù) 
int threshold; // 容量閾值，所有竹籃允許緩存雞蛋的個(gè)數(shù)，超過這個(gè)值需要擴(kuò)容，默認(rèn)為0，看看后續(xù)是如何變化的，對(duì)理解擴(kuò)容那塊很重要 
final float loadFactor; // 加載因子，能夠權(quán)衡時(shí)間復(fù)雜度和空間復(fù)雜度 

筆試or面試需要記住幾個(gè)死記硬背的點(diǎn)，那就是：hashmap的默認(rèn)初始容量為16，加載因子是0.75，鏈表長(zhǎng)過8則轉(zhuǎn)紅黑樹，小于6則轉(zhuǎn)鏈表，容量低于64則先擴(kuò)容，而不會(huì)鏈表轉(zhuǎn)紅黑樹。

看看構(gòu)造方法

HashMap有四個(gè)構(gòu)造方法，這里只列出我們常用的兩個(gè)

• 第一個(gè)是默認(rèn)構(gòu)造方法，我們不指定默認(rèn)所有竹籃累計(jì)可以放16個(gè)雞蛋
• 第二個(gè)是指定初始容量，也是我們比較推薦的做法，根據(jù)需要設(shè)置大小，避免后面resize擴(kuò)容開銷

日常開發(fā)中如果知道大小，我們都會(huì)用第二種，可以避免resize擴(kuò)容開銷，新手開發(fā)經(jīng)常會(huì)直接用第一種，一般我review代碼看到都會(huì)直接打回改，然后告訴他們?yōu)樯?，想想看，如果你已?jīng)知道這個(gè)map容器要裝的元素是100個(gè)，你還不指定初始容量，那么就會(huì)導(dǎo)致在第一次put數(shù)據(jù)的時(shí)候進(jìn)行擴(kuò)容，此時(shí)第一次擴(kuò)容因?yàn)闆]有初始容量，計(jì)算出的容量閾值為默認(rèn)大小16，16*加載因子0.75f就是12，之后當(dāng)你繼續(xù)put值超過12個(gè)的時(shí)候又會(huì)繼續(xù)擴(kuò)容，第二次擴(kuò)容后容量閾值為24，循環(huán)剛剛的過程直到容量閾值大于100，而如果指定了默認(rèn)大小則第一次擴(kuò)容就夠用了，不用走后面那么多次擴(kuò)容，可以節(jié)省性能;

其次是命名也要注意下，最好是直接用Map結(jié)合，比如xxxMap，這是規(guī)范。

擴(kuò)容

我們先回顧下上面的一個(gè)成員變量threshold

「int threshold; // 容量閾值，所有竹籃允許放入雞蛋的個(gè)數(shù)」

ok了，繼續(xù)講擴(kuò)容，擴(kuò)容分為多種情況

• 如果我們使用了無參構(gòu)造方法，可以看到

其中并未對(duì)成員變量threshold容量閾值進(jìn)行初始化，反調(diào)threshold賦值的地方可以看到在put第一個(gè)元素的時(shí)候會(huì)調(diào)用resize方法，該方法有做了容量閾值的計(jì)算，計(jì)算方式為：DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY，也就是默認(rèn)的加載因子 * 默認(rèn)容量，即 0.75f * 16，即12

• 如果指定了初始容量

可以看到初始容量閾值的計(jì)算公式是：

這么一坨東西是啥呢，其實(shí)就是一個(gè)算法，看不懂也莫得關(guān)系，畢竟我也看不懂，記住就好，這個(gè)算法其實(shí)就是返回大于輸入?yún)?shù)且最近的2的整數(shù)次冪的數(shù)，比如設(shè)置的初始容量為10，那么這個(gè)算法則返回16。

但是，到了這里其實(shí)也并沒有分配好數(shù)組，可以看到resize方法，其實(shí)也是在put的時(shí)候才會(huì)真正進(jìn)行數(shù)組的分配，也就是懶加載了。

• 二次擴(kuò)容，最終都會(huì)走向resize方法，每次擴(kuò)容量都會(huì)是原先的2倍。

我們可以看看resize方法

final Node<K,V>[] resize() { 
        Node<K,V>[] oldTab = table; 
        int oldCap = (oldTab == null) ? 0 : oldTab.length; 
        int oldThr = threshold; 
        int newCap, newThr = 0; 
        if (oldCap > 0) { 
            // 如果竹籃個(gè)數(shù)大于最大容量，則將容量閾值設(shè)置成int的最大值 
            if (oldCap >= MAXIMUM_CAPACITY) { 
                threshold = Integer.MAX_VALUE; 
                return oldTab; 
            } 
           // 否則新閾值為舊閾值兩倍 
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && 
                     oldCap >= DEFAULT_INITIAL_CAPACITY) 
                newThr = oldThr << 1; 
        } 
        else if (oldThr > 0)  
            newCap = oldThr; 
        else {               
           // 只有默認(rèn)無參構(gòu)造方法才會(huì)走到這個(gè)分支，閾值為默認(rèn)算法，容量 * 0.75 
            newCap = DEFAULT_INITIAL_CAPACITY; 
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); 
        } 
        if (newThr == 0) { 
            float ft = (float)newCap * loadFactor; 
            newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? 
                      (int)ft : Integer.MAX_VALUE); 
        } 
        threshold = newThr; 
        @SuppressWarnings({"rawtypes","unchecked"}) 
    // 真正進(jìn)行擴(kuò)容的地方，也是凌亂的算法我大致講講，首先要?jiǎng)?chuàng)建一個(gè)新的哈希表，其容量為上面計(jì)算出來的 
        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; 
        table = newTab; 
        if (oldTab != null) { 
        // 輪詢操作，對(duì)所有元素重哈希 
        for (int j = 0; j < oldCap; ++j) { 
            Node<K,V> e; 
            if ((e = oldTab[j]) != null) { 
                oldTab[j] = null; 
                if (e.next == null) 
                    newTab[e.hash & (newCap - 1)] = e; 
                else if (e instanceof TreeNode) 
                    // 竹籃內(nèi)內(nèi)的雞蛋數(shù)據(jù)重hash，紅黑樹轉(zhuǎn)鏈表的地方，內(nèi)部處理主要是當(dāng)竹籃內(nèi)的雞蛋個(gè)數(shù)小于等于6時(shí)，樹結(jié)構(gòu)會(huì)還原成鏈表 
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap); 
                else { // preserve order 
                    // 略：鏈表元素重hash 
                } 
            } 
        } 
    } 
    return newTab; 
} 

HashMap擴(kuò)容可以分為三種：

• 使用默認(rèn)構(gòu)造方法初始化HashMap，從前文可以知道HashMap在一開始初始化的時(shí)候thershold容量閾值為0，默認(rèn)值DEFAULT_INITIAL_CAPACITY也就是16，DEFAULT_LOAD_FACTOR為0.75f，因此在第一次put數(shù)據(jù)的時(shí)候會(huì)進(jìn)行擴(kuò)容，擴(kuò)容后的容量閾值threshold為DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR = 12;
• 指定初始容量的構(gòu)造方法初始化HashMap，可以看到在初始化的時(shí)候便通過tableSizeFor進(jìn)行計(jì)算，也就是返回大于輸入?yún)?shù)且最近的2的整數(shù)次冪的數(shù);
• 當(dāng)HashMap不是第一次擴(kuò)容的時(shí)候，那么每次擴(kuò)容的容量以及容量閾值threshold為原有的兩倍。

hash計(jì)算

HashCode是啥其實(shí)大家都知道，無非就是用來確定對(duì)象在HashMap中的存儲(chǔ)地址，目的也很簡(jiǎn)單，為了快，貌似除了了那方面，其他都是越快越好，比如賺錢。

元素插入

我們先回顧下上面的一個(gè)成員變量table

「itransient Node<K,V>[] table; // 哈希表數(shù)組，存儲(chǔ)數(shù)據(jù)的地方，每個(gè)竹籃結(jié)構(gòu)可能為鏈表或者紅黑樹，總是2的冪次倍」

  
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, 
                boolean evict) { 
    Node<K,V>[] tab; Node<K,V> p; int n, i; 
    // 這里如果發(fā)現(xiàn)動(dòng)態(tài)數(shù)組為null則會(huì)初始化數(shù)組。 
    if ((tab = table) == null || (n = tab.length) == 0) 
        // 第一次放入值時(shí)會(huì)在這里初始化數(shù)組，并且通過resize方法進(jìn)行擴(kuò)容 
        n = (tab = resize()).length; 
    // 通過hash發(fā)現(xiàn)要放入的雞蛋的數(shù)組位置為null，說明沒有hash沖突，則直接把該雞蛋放在這里即可 
    if ((p = tab[i = (n - 1) & hash]) == null) 
        tab[i] = newNode(hash, key, value, null); 
    else { 
        // 如果要放入的位置已經(jīng)有該雞蛋了 
        Node<K,V> e; K k; 
        // 判斷竹籃的第一個(gè)雞蛋否和新元素key以及hash值都完全一致，如果是則不用看代碼都知道進(jìn)行覆蓋，覆蓋的邏輯在后面 
        if (p.hash == hash && 
            ((k = p.key) == key || (key != null && key.equals(k)))) 
            e = p; 
        // 確認(rèn)是否為樹解點(diǎn) 
        else if (p instanceof TreeNode) 
            // 如果是的話則按照紅黑樹方法放入竹籃內(nèi) 
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); 
        else { 
            // 說明不是，則是列表，按照列表方法放入 
            for (int binCount = 0; ; ++binCount) { 
                // 一直向下取，直到找到空的位置 
                if ((e = p.next) == null) { 
                    p.next = newNode(hash, key, value, null); 
                    //  判斷鏈表長(zhǎng)度是否大于8，這里其實(shí)減后為7，判斷的是binCount,但是因?yàn)椴迦肓艘粋€(gè)新節(jié)點(diǎn)了，所以其實(shí)為8 
                    if (binCount >= TREEIFY_THRESHOLD - 1)  
                        // 則將列表轉(zhuǎn)為紅黑樹，所以記住大于8的時(shí)候會(huì)轉(zhuǎn)成紅黑樹 
                        treeifyBin(tab, hash); 
                    break; 
                } 
                // 已經(jīng)找到了hash值和key一樣的，則直接break，不用找了，同樣在后面進(jìn)行覆蓋 
                if (e.hash == hash && 
                    ((k = e.key) == key || (key != null && key.equals(k)))) 
                    break; 
                p = e; 
            } 
        } 
 
        // 覆蓋操作在這里，新值和舊值的key完全相同，進(jìn)行覆蓋操作 
        if (e != null) {  
            V oldValue = e.value; 
            if (!onlyIfAbsent || oldValue == null) 
                e.value = value; 
            // 訪問后回調(diào) 
            afterNodeAccess(e); 
            return oldValue; 
        } 
    } 
    ++modCount; 
    // 當(dāng)map中所有的雞蛋個(gè)數(shù)大于容量閾值時(shí)則進(jìn)行擴(kuò)容，二次擴(kuò)容如上面所說，也就是兩倍 
    if (++size > threshold) 
        resize(); 
    afterNodeInsertion(evict); 
    return null; 
} 

  
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, 
                boolean evict) { 
    Node<K,V>[] tab; Node<K,V> p; int n, i; 
    // 這里如果發(fā)現(xiàn)動(dòng)態(tài)數(shù)組為null則會(huì)初始化數(shù)組。 
    if ((tab = table) == null || (n = tab.length) == 0) 
        // 第一次放入值時(shí)會(huì)在這里初始化數(shù)組，并且通過resize方法進(jìn)行擴(kuò)容 
        n = (tab = resize()).length; 
    // 通過hash發(fā)現(xiàn)要放入的雞蛋的數(shù)組位置為null，說明沒有hash沖突，則直接把該雞蛋放在這里即可 
    if ((p = tab[i = (n - 1) & hash]) == null) 
        tab[i] = newNode(hash, key, value, null); 
    else { 
        // 如果要放入的位置已經(jīng)有該雞蛋了 
        Node<K,V> e; K k; 
        // 判斷竹籃的第一個(gè)雞蛋否和新元素key以及hash值都完全一致，如果是則不用看代碼都知道進(jìn)行覆蓋，覆蓋的邏輯在后面 
        if (p.hash == hash && 
            ((k = p.key) == key || (key != null && key.equals(k)))) 
            e = p; 
        // 確認(rèn)是否為樹解點(diǎn) 
        else if (p instanceof TreeNode) 
            // 如果是的話則按照紅黑樹方法放入竹籃內(nèi) 
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); 
        else { 
            // 說明不是，則是列表，按照列表方法放入 
            for (int binCount = 0; ; ++binCount) { 
                // 一直向下取，直到找到空的位置 
                if ((e = p.next) == null) { 
                    p.next = newNode(hash, key, value, null); 
                    //  判斷鏈表長(zhǎng)度是否大于8，這里其實(shí)減后為7，判斷的是binCount,但是因?yàn)椴迦肓艘粋€(gè)新節(jié)點(diǎn)了，所以其實(shí)為8 
                    if (binCount >= TREEIFY_THRESHOLD - 1)  
                        // 則將列表轉(zhuǎn)為紅黑樹，所以記住大于8的時(shí)候會(huì)轉(zhuǎn)成紅黑樹 
                        treeifyBin(tab, hash); 
                    break; 
                } 
                // 已經(jīng)找到了hash值和key一樣的，則直接break，不用找了，同樣在后面進(jìn)行覆蓋 
                if (e.hash == hash && 
                    ((k = e.key) == key || (key != null && key.equals(k)))) 
                    break; 
                p = e; 
            } 
        } 
 
        // 覆蓋操作在這里，新值和舊值的key完全相同，進(jìn)行覆蓋操作 
        if (e != null) {  
            V oldValue = e.value; 
            if (!onlyIfAbsent || oldValue == null) 
                e.value = value; 
            // 訪問后回調(diào) 
            afterNodeAccess(e); 
            return oldValue; 
        } 
    } 
    ++modCount; 
    // 當(dāng)map中所有的雞蛋個(gè)數(shù)大于容量閾值時(shí)則進(jìn)行擴(kuò)容，二次擴(kuò)容如上面所說，也就是兩倍 
    if (++size > threshold) 
        resize(); 
    afterNodeInsertion(evict); 
    return null; 
} 

final void treeifyBin(Node<K,V>[] tab, int hash) { 
    int n, index; Node<K,V> e; 
    // 當(dāng)tab為空或者竹籃個(gè)數(shù)小于64個(gè)，會(huì)先進(jìn)行擴(kuò)容，而不會(huì)鏈表轉(zhuǎn)紅黑樹 
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY) 
        resize(); 
    else if ((e = tab[index = (n - 1) & hash]) != null) { 
        // 真正進(jìn)行轉(zhuǎn)換的地方 
        TreeNode<K,V> hd = null, tl = null; 
        do { 
            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); 
        if ((tab[index] = hd) != null) 
            hd.treeify(tab); 
    } 
} 

put總體流程匯總?cè)缦拢?/p>

羅列幾個(gè)該注意的點(diǎn)，分別是：

• HashMap中緩存數(shù)據(jù)的數(shù)組table，我們可以看到初始化的時(shí)候默認(rèn)是null，是在第一次put數(shù)據(jù)的時(shí)候才進(jìn)行初始化的，這也是所謂的懶加載，記住了，不要每次提HashMap的懶加載機(jī)制都二臉懵逼了。
• HashMap中單個(gè)竹籃存放的雞蛋個(gè)數(shù)大于8，并且當(dāng)竹籃個(gè)數(shù)大于64個(gè)的時(shí)候則將列表轉(zhuǎn)為紅黑樹，否則進(jìn)行擴(kuò)容。
• 每次put數(shù)據(jù)時(shí)當(dāng)map中存放的所有雞蛋個(gè)數(shù)大于容量閾值時(shí)則進(jìn)行擴(kuò)容，并且是先put數(shù)據(jù)，再擴(kuò)容。

元素查詢

final Node<K,V> getNode(int hash, Object key) { 
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k; 
    if ((tab = table) != null && (n = tab.length) > 0 && 
        (first = tab[(n - 1) & hash]) != null) { 
       // 如果計(jì)算hash值和第一個(gè)節(jié)點(diǎn)的key值相同，直接返回 
        if (first.hash == hash && // always check first node 
            ((k = first.key) == key || (key != null && key.equals(k)))) 
            return first; 
        if ((e = first.next) != null) { 
           //如果為紅黑樹節(jié)點(diǎn)，以紅黑樹方式查找 
            if (first instanceof TreeNode) 
                return ((TreeNode<K,V>)first).getTreeNode(hash, key); 
            do { 
               //如果hash值相同，key不同，則遍歷鏈表找到相同的key，返回 
                if (e.hash == hash && 
                    ((k = e.key) == key || (key != null && key.equals(k)))) 
                    return e; 
            } while ((e = e.next) != null); 
        } 
    } 
    return null; 
} 

查找這里，總結(jié)下來流程便是：

• 根據(jù)hash值從竹籃數(shù)組內(nèi)找到竹籃，判斷頭節(jié)點(diǎn)key值與當(dāng)前key相同，直接返回
• 如果該竹籃為TreeNode節(jié)點(diǎn)，以紅黑樹方式查找
• 如果不是則循環(huán)遍歷鏈表，直到查到對(duì)應(yīng)的key相同

元素刪除

final Node<K,V> removeNode(int hash, Object key, Object value, 
                               boolean matchValue, boolean movable) { 
        Node<K,V>[] tab; Node<K,V> p; int n, index; 
        if ((tab = table) != null && (n = tab.length) > 0 && 
            (p = tab[index = (n - 1) & hash]) != null) { 
            Node<K,V> node = null, e; K k; V v; 
            if (p.hash == hash && 
                ((k = p.key) == key || (key != null && key.equals(k)))) 
                node = p; 
            else if ((e = p.next) != null) { 
               //紅黑樹的查找方式 
                if (p instanceof TreeNode) 
                    node = ((TreeNode<K,V>)p).getTreeNode(hash, key); 
                else { 
                   //鏈表遍歷查找方式 
                    do { 
                        if (e.hash == hash && 
                            ((k = e.key) == key || 
                             (key != null && key.equals(k)))) { 
                            node = e; 
                            break; 
                        } 
                        p = e; 
                    } while ((e = e.next) != null); 
                } 
            } 
           //刪除node 
            if (node != null && (!matchValue || (v = node.value) == value || 
                                 (value != null && value.equals(v)))) { 
               //如果node為紅黑樹結(jié)點(diǎn)，采用紅黑樹刪除方式 
                if (node instanceof TreeNode) 
                    ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable); 
               // 如果是鏈表并且node為頭結(jié)點(diǎn)，當(dāng)前數(shù)組下標(biāo)元素直接替換為next 
                else if (node == p) 
                    tab[index] = node.next; 
                else 
                   //鏈表非頭元素刪除方式 
                    p.next = node.next; 
                ++modCount; 
                --size; 
                afterNodeRemoval(node); 
                return node; 
            } 
        } 
        return null; 
    } 

刪除操作很簡(jiǎn)單，先根據(jù)hash找到對(duì)應(yīng)雞蛋，然后根據(jù)不同類型的節(jié)點(diǎn)進(jìn)行刪除，沒什么注意的點(diǎn)，如果有，那就是如果是鏈表表頭的話，則需要將下一個(gè)節(jié)點(diǎn)賦值為表頭。

本文轉(zhuǎn)載自微信公眾號(hào)「稀飯下雪」，可以通過以下二維碼關(guān)注。轉(zhuǎn)載本文請(qǐng)聯(lián)系稀飯下雪公眾號(hào)。