循序漸進分析源碼之 HashMap put 方法的示例分析

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

預備知識

注意：這里不會講紅黑樹是什么，以及如何具體實現。我們只需知道它長什么樣子并了解它的好處即可。

為什么 在jdk1.8 中采用數組+鏈表/紅黑樹的數據結構存儲數據？

當 Hash 沖突嚴重時，在數組上的鏈表會越來越長，此時就會會降低查詢時的效率；時間復雜度為 O(N)。 引入紅黑樹之后查詢效率直接提高到了 O(logn)。

引入紅黑樹后，HashMap 內部數據結構長什么樣子？

什么時候會采用鏈表，什么時候用紅黑樹？

當鏈表的大小大于預設的閾值（8）時就要轉換為紅黑樹

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 沒有初始化,需要進行初始化
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // 2. 根據計算出的元素所在數組中的位置，并判斷目標位置是否為空
    // 2.1 如果為空. new 一個新的 Node 放置在目標位置
    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 如果目標位置有值（有可能是紅黑樹的根節點，也有可能是鏈表的表頭），就比較key 是否相同（相當于提前判斷吧）
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        // 2.2.2 如果目標位置放的是一個紅黑樹，就按照紅黑樹的方式，寫入數據
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        // 2.2.3 如果目標位置放置的是一個鏈表，就遍歷整個鏈表。
        else {
            for (int binCount = 0; ; ++binCount) {
            	// 如果當前節點的下一個節點為空，就 new 一個新的節點，然后當前節點指向這個新節點
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    // 對這個增加了一個節點的鏈表進行長度判斷，如果長度大于閥值，就將鏈表轉成紅黑樹
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                // 如果當前節點的下一個節點不為空，就要判斷 key 是否相同，如果相同，就跳出循環。
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        // 對 2.2.1 和 2.2.2 和 2.2.3 進行判斷。判斷成立表示要覆蓋原有位置的元素。
        if (e != null) { 
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    // 下面是擴容代碼，暫時忽略
    ++modCount;
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

put 方法的流程圖

看完上述內容是否對您有幫助呢？如果還想對相關知識有進一步的了解或閱讀更多相關文章，請關注億速云行業資訊頻道，感謝您對億速云的支持。