循序漸進(jìn)分析源碼之 HashMap put 方法的示例分析

循序漸進(jìn)分析源碼之 HashMap put 方法的執(zhí)行流程（jdk 1.8 ）的示例分析，很多新手對(duì)此不是很清楚，為了幫助大家解決這個(gè)難題，下面小編將為大家詳細(xì)講解，有這方面需求的人可以來(lái)學(xué)習(xí)下，希望你能有所收獲。

預(yù)備知識(shí)

注意：這里不會(huì)講紅黑樹是什么，以及如何具體實(shí)現(xiàn)。我們只需知道它長(zhǎng)什么樣子并了解它的好處即可。

為什么 在jdk1.8 中采用數(shù)組+鏈表/紅黑樹的數(shù)據(jù)結(jié)構(gòu)存儲(chǔ)數(shù)據(jù)？

當(dāng) Hash 沖突嚴(yán)重時(shí)，在數(shù)組上的鏈表會(huì)越來(lái)越長(zhǎng)，此時(shí)就會(huì)會(huì)降低查詢時(shí)的效率；時(shí)間復(fù)雜度為 O(N)。 引入紅黑樹之后查詢效率直接提高到了 O(logn)。

引入紅黑樹后，HashMap 內(nèi)部數(shù)據(jù)結(jié)構(gòu)長(zhǎng)什么樣子？

什么時(shí)候會(huì)采用鏈表，什么時(shí)候用紅黑樹？

當(dāng)鏈表的大小大于預(yù)設(shè)的閾值（8）時(shí)就要轉(zhuǎn)換為紅黑樹

put 方法源碼(帶注釋)

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; // 局部變量，指向容器
    Node<K,V> p; // 局部變量
    int n, i;
    // 1. 如果 HashMap 沒有初始化,需要進(jìn)行初始化
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // 2. 根據(jù)計(jì)算出的元素所在數(shù)組中的位置，并判斷目標(biāo)位置是否為空
    // 2.1 如果為空. new 一個(gè)新的 Node 放置在目標(biāo)位置
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    // 2.2 如果不為空, 再分情況討論
    else {
        Node<K,V> e; 
        K k;
        // 2.2.1 如果目標(biāo)位置有值（有可能是紅黑樹的根節(jié)點(diǎn)，也有可能是鏈表的表頭），就比較key 是否相同（相當(dāng)于提前判斷吧）
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        // 2.2.2 如果目標(biāo)位置放的是一個(gè)紅黑樹，就按照紅黑樹的方式，寫入數(shù)據(jù)
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        // 2.2.3 如果目標(biāo)位置放置的是一個(gè)鏈表，就遍歷整個(gè)鏈表。
        else {
            for (int binCount = 0; ; ++binCount) {
            	// 如果當(dāng)前節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)為空，就 new 一個(gè)新的節(jié)點(diǎn)，然后當(dāng)前節(jié)點(diǎn)指向這個(gè)新節(jié)點(diǎn)
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    // 對(duì)這個(gè)增加了一個(gè)節(jié)點(diǎn)的鏈表進(jìn)行長(zhǎng)度判斷，如果長(zhǎng)度大于閥值，就將鏈表轉(zhuǎn)成紅黑樹
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                // 如果當(dāng)前節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)不為空，就要判斷 key 是否相同，如果相同，就跳出循環(huán)。
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        // 對(duì) 2.2.1 和 2.2.2 和 2.2.3 進(jìn)行判斷。判斷成立表示要覆蓋原有位置的元素。
        if (e != null) { 
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    // 下面是擴(kuò)容代碼，暫時(shí)忽略
    ++modCount;
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

put 方法的流程圖

看完上述內(nèi)容是否對(duì)您有幫助呢？如果還想對(duì)相關(guān)知識(shí)有進(jìn)一步的了解或閱讀更多相關(guān)文章，請(qǐng)關(guān)注億速云行業(yè)資訊頻道，感謝您對(duì)億速云的支持。