深入理解HashMap(五): 關鍵源碼逐行分析之put

APICloud 發布于2019-08-19 10:51 / 1336人閱讀

摘要：當鏈表長度超過默認是個時，會將鏈表轉換成紅黑樹以提升查找性能。

前言

系列文章目錄

上一篇我們討論了HashMap的擴容操作, 提到擴容操作發生在table的初始化或者table大小超過threshold后，而這兩個條件的觸發基本上就發生在put操作中。

本篇我們就來聊聊HashMap的put操作。

本文的源碼基于 jdk8 版本.

put方法

HashMap 實現了Map接口, 因此必須要實現put方法:

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
    /*final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) */
}

可以看到, put方法是有返回值的, 這里調用了 putVal 方法, 這個方法很重要, 我們將通過代碼注釋的方式逐行說明.

在這之前我們先看該方法的參數:

hash

由上面的調用可知, 該值為hash(key), 是key的hash值, 關于hash的概念之前已經講過了, 這里不再贅述.

key, value

待存儲的鍵值對

onlyIfAbsent

這個參數用于決定待存儲的key已經存在的情況下,要不要用新值覆蓋原有的value, 如果為true, 則保留原有值, false 則覆蓋原有值, 從上面的調用看, 該值為false, 說明當key值已經存在時, 會直接覆蓋原有值。

evict

該參數用來區分當前是否是構造模式, 我們在講解構造函數的時候曾經提到，HashMap的第四個構造函數可以通過已經存在的Map初始化一個HashMap, 如果為 false, 說明在構造模式下, 這里我們是用在put函數而不是構造函數里面, 所以為true。

參數解釋完了之后, 下面我們來逐行看代碼:

final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
    Node[] tab; Node p; int n, i;
    
    // 首先判斷table是否是空的
    // 我們知道, HashMap的三個構造函數中, 都不會初始Table, 因此第一次put值時, table一定是空的, 需要初始化
    // table的初始化用到了resize函數, 這個我們上一篇文章已經講過了
    // 由此可見table的初始化是延遲到put操作中的
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
        
    // 這里利用 `(n-1) & hash` 方法計算 key 所對應的下標
    // 如果key所對應的桶里面沒有值, 我們就新建一個Node放入桶里面
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    
    // 到這里說明目標位置桶里已經有東西了
    else {
        Node e; K k;
        // 這里先判斷當前待存儲的key值和已經存在的key值是否相等
        // key值相等必須滿足兩個條件
        //    1. hash值相同
        //    2. 兩者 `==` 或者 `equals` 等
        if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
            e = p; // key已經存在的情況下, e保存原有的鍵值對
        
        // 到這里說明要保存的桶已經被占用, 且被占用的位置存放的key與待存儲的key值不一致
        
        // 前面已經說過, 當鏈表長度超過8時, 會用紅黑樹存儲, 這里就是判斷存儲桶中放的是鏈表還是紅黑樹
        else if (p instanceof TreeNode)
            // 紅黑樹的部分以后有機會再說吧
            e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);
        
        //到這里說明是鏈表存儲, 我們需要順序遍歷鏈表
        else {
            for (int binCount = 0; ; ++binCount) {
                // 如果已經找到了鏈表的尾節點了,還沒有找到目標key, 則說明目標key不存在，那我們就新建一個節點, 把它接在尾節點的后面
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    // 如果鏈表的長度達到了8個, 就將鏈表轉換成紅黑數以提升查找性能
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                // 如果在鏈表中找到了目標key則直接退出
                // 退出時e保存的是目標key的鍵值對
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        
        // 到這里說明要么待存儲的key存在, e保存已經存在的值
        // 要么待存儲的key不存在, 則已經新建了Node將key值插入, e的值為Null
        
        // 如果待存儲的key值已經存在
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            
            // 前面已經解釋過, onlyIfAbsent的意思
            // 這里是說舊值存在或者舊值為null的情況下, 用新值覆蓋舊值
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e); //這個函數只在LinkedHashMap中用到, 這里是空函數
            // 返回舊值
            return oldValue;
        }
    }
    
    // 到這里說明table中不存在待存儲的key, 并且我們已經將新的key插入進數組了
    
    ++modCount; // 這個暫時用不到
    
    // 因為又插入了新值, 所以我們得把數組大小加1, 并判斷是否需要重新擴容
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict); //這個函數只在LinkedHashMap中用到, 這里是空函數
    return null;
}

總結

在put之前會檢查table是否為空，說明table真正的初始化并不是發生在構造函數中，而是發生在第一次put的時候。

查找當前key是否存在的條件是p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))

如果插入的key值不存在，則值會插入到鏈表的末尾。

每次插入操作結束后，都會檢查當前table節點數是否大于threshold, 若超過，則擴容。

當鏈表長度超過TREEIFY_THRESHOLD（默認是8）個時，會將鏈表轉換成紅黑樹以提升查找性能。

(完)

查看更多系列文章：系列文章目錄

GPU云服務器云服務器深入理解webrtc之aec 深入理解系列深入理解linux 深入理解webrtc

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/76560.html

系列文章目錄

摘要：為了避免一篇文章的篇幅過長，于是一些比較大的主題就都分成幾篇來講了，這篇文章是筆者所有文章的目錄，將會持續更新，以給大家一個查看系列文章的入口。前言大家好，筆者是今年才開始寫博客的，寫作的初衷主要是想記錄和分享自己的學習經歷。因為寫作的時候發現，為了弄懂一個知識，不得不先去了解另外一些知識，這樣以來，為了說明一個問題，就要把一系列知識都了解一遍，寫出來的文章就特別長。為了避免一篇...

lijy91 2019-06-28 16:36 評論0 收藏0
系列文章目錄

摘要：為了避免一篇文章的篇幅過長，于是一些比較大的主題就都分成幾篇來講了，這篇文章是筆者所有文章的目錄，將會持續更新，以給大家一個查看系列文章的入口。前言大家好，筆者是今年才開始寫博客的，寫作的初衷主要是想記錄和分享自己的學習經歷。因為寫作的時候發現，為了弄懂一個知識，不得不先去了解另外一些知識，這樣以來，為了說明一個問題，就要把一系列知識都了解一遍，寫出來的文章就特別長。為了避免一篇...

Yumenokanata 2019-08-19 10:58 評論0 收藏0
深入理解HashMap(四): 關鍵源碼逐行分析之resize擴容

摘要：前言系列文章目錄上一篇我們說明了的構造函數談到構造函數中并不會初始化變量變量是在過程中初始化的本篇我們就來聊聊的擴容本文的源碼基于版本用于以下兩種情況之一初始化在大小超過之后進行擴容下面我們直接來對照源碼分析原中已經有值已經超過最大限制不再前言系列文章目錄上一篇我們說明了HashMap的構造函數, 談到構造函數中并不會初始化table 變量, table 變量是在 resize過...

aristark 2019-08-19 10:50 評論0 收藏0
深入理解HashMap(二): 關鍵源碼逐行分析之hash算法

摘要：散列函數把消息或數據壓縮成摘要，使得數據量變小，將數據的格式固定下來。該函數將數據打亂混合，重新創建一個叫做散列值，，，或的指紋。前言系列文章目錄前面我們討論了HashMap的結構, 接下來幾篇我們從源碼角度來看HashMap的實現細節. 本篇我們就來聊聊HashMap的hash算法本文的源碼基于 jdk8 版本. hash算法上一篇文章我們提到, 為了利用數組索引進行快速查...

chunquedong 2019-08-19 10:50 評論0 收藏0
深入理解HashMap(三): 關鍵源碼逐行分析之構造函數

摘要：前言系列文章目錄上一篇我們說明了的算法說到在構造時會自動將設為的整數次冪本篇我們就來聊聊的構造函數本文的源碼基于版本構造函數共有四個構造函數默認初始大小默認負載因子沒有指定時使用默認值即默認初始大小默認負載因子指定初始大小但使用默認負載因子前言系列文章目錄上一篇我們說明了HashMap的hash算法, 說到HashMap在構造時會自動將table設為2的整數次冪. 本篇我們就來聊...

QiuyueZhong 2019-08-19 10:50 評論0 收藏0