HashMap源碼重點分析

目錄

一、為啥要使用數組+連結清單+紅黑樹的結構

二、雜湊演算法及put過程部分分析

三、哈希擴容

四、死鎖發生

一、為啥要使用數組+連結清單+紅黑樹的結構

• 數組+連結清單（jdk1.8之前）
• 數組+連結清單+紅黑樹（紅黑樹是jdk1.8引進，當連結清單長度 >= 8即為9（最後會插入一個元素）時轉為紅黑樹，這裡具體不研究紅黑樹）

資料結構特點及為啥使用這種結構

• 數組：查找非常快。
• 連結清單：增加/删除非常快。查找效率不高。
• 紅黑樹：確定最壞查詢效率，就是解決連結清單長度過長。

二、雜湊演算法及put過程部分分析

1、put之前，調用雜湊演算法

2、深入雜湊演算法

發現hash算法，當不為空時，是傳回key.hashCode() ^ (key.hashCode() >>> 16)

為什麼要這樣子呢？

如下圖分析：

目的是為了不讓高16位特征丢失。進行異或（^）運算是為了之後的索引均勻散列。

put過程（hash值計算重點）

具體put實作（計算下标hash & (n - 1)效率比 hash % n高）

/**
     * Map.put和其他相關方法的實作需要的方法
     * putVal方法可以分為下面的幾個步驟:
     * 1.如果哈希表為空，調用resize()建立一個哈希表。
     * 2.如果指定參數hash在表中沒有對應的桶，即為沒有碰撞，直接将鍵值對插入到哈希表中即可。
     * 3.如果有碰撞，周遊桶，找到key映射的節點
     * 3.1桶中的第一個節點就比對了，将桶中的第一個節點記錄起來。
     * 3.2如果桶中的第一個節點沒有比對，且桶中結構為紅黑樹，則調用紅黑樹對應的方法插入鍵值對。
     * 3.3如果不是紅黑樹，那麼就肯定是連結清單。周遊連結清單，如果找到了key映射的節點，就記錄這個節點，退出循環。如果沒有找到，在連結清單尾部插入節點。插入後，如果鍊的長度大于TREEIFY_THRESHOLD這個臨界值，則使用treeifyBin方法把連結清單轉為紅黑樹。
     * 4.如果找到了key映射的節點，且節點不為null
     * 4.1記錄節點的vlaue。
     * 4.2如果參數onlyIfAbsent為false，或者oldValue為null，替換value，否則不替換。
     * 4.3傳回記錄下來的節點的value。
     * 5.如果沒有找到key映射的節點（2、3步中講了，這種情況會插入到hashMap中），插入節點後size會加1，這時要檢查size是否大于臨界值threshold，如果大于會使用resize方法進行擴容。
     *
     * @param hash         指定參數key的哈希值
     * @param key          指定參數key
     * @param value        指定參數value
     * @param onlyIfAbsent 如果為true，即使指定參數key在map中已經存在，也不會替換value
     * @param evict        如果為false，數組table在建立模式中
     * @return 如果value被替換，則傳回舊的value，否則傳回null。當然，可能key對應的value就是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;
        //如果哈希表為空，調用resize()建立一個哈希表，并用變量n記錄哈希表長度
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        /**
         * 如果指定參數hash在表中沒有對應的桶，即為沒有碰撞
         * Hash函數，(n - 1) & hash 計算key将被放置的槽位
         * (n - 1) & hash 本質上是hash % n，位運算更快
         */
        if ((p = tab[i = (n - 1) & hash]) == null)
            //直接将鍵值對插入到map中即可
            tab[i] = newNode(hash, key, value, null);
        else {// 桶中已經存在元素
            Node<K, V> e;
            K k;
            // 比較桶中第一個元素(數組中的結點)的hash值相等，key相等
            if (p.hash == hash &&
                    ((k = p.key) == key || (key != null && key.equals(k))))
                // 将第一個元素指派給e，用e來記錄
                e = p;
                // 目前桶中無該鍵值對，且桶是紅黑樹結構，按照紅黑樹結構插入
            else if (p instanceof TreeNode)
                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);
                        // 檢查連結清單長度是否達到門檻值，達到将該槽位節點組織形式轉為紅黑樹
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                    // 連結清單節點的<key, value>與put操作<key, value>相同時，不做重複操作，跳出循環
                    if (e.hash == hash &&
                            ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            // 找到或建立一個key和hashCode與插入元素相等的鍵值對，進行put操作
            if (e != null) { // existing mapping for key
                // 記錄e的value
                V oldValue = e.value;
                /**
                 * onlyIfAbsent為false或舊值為null時，允許替換舊值
                 * 否則無需替換
                 */
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                // 通路後回調
                afterNodeAccess(e);
                // 傳回舊值
                return oldValue;
            }
        }
        // 更新結構化修改資訊
        ++modCount;
        // 鍵值對數目超過門檻值時，進行rehash
        if (++size > threshold)
            resize();
        // 插入後回調
        afterNodeInsertion(evict);
        return null;
    }
           

三、哈希擴容

這裡涉及到一些參數

1、HashMap預設長度16。而且一定是2^n次方，為啥？涉及到hashMap-put過程的索引确定，索引是(n - 1) & hash

這裡的(n - 1)二進制如果是2^n次方，那麼可以確定全1，這樣 （n-1）& hash就能確定均勻。

為啥不使用%？，因為&運算效率遠高于%。

2、預設擴容因子0.75。HashMap長度 大于 HashMap長度*擴容因子為觸發擴容的條件，剛開始為16*0.75，就是連結清單長度13，就會觸發擴容操作。

threshold = HashMap長度*擴容因子 = 16 * 0.75 = 12。下面源碼在第一次resize()中，目的是初始化數組，而不是擴容

size == 13時，就是HashMap容量，就會觸發第一次擴容。

3、轉換成紅黑樹

條件1：(n = tab.length) < MIN_TREEIFY_CAPACITY)，當數組長度達到64及以上時。不然會進行擴容。

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)
            resize();
           

條件2：當連結清單長度大于等8時（實際将添加進去的元素剛好是9個後才進行轉換，可以去源碼數一數binCount=7時，連結清單個數），觸發條件，将連結清單轉為紅黑樹。

小于等于6轉為連結清單

擴容源碼主要研究下面這段

if (oldTab != null) {
            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)
                        ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                    else { // preserve order
                        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;
                        }
                    }
                }
            }
        }
           

需要擴容時（連結清單有7個元素，桶大小為8，剛好觸發擴容）

擴容

四、死鎖發生

原因：

• jdk1.7及以下，HashMap在擴容 resize() 時，會發生死鎖，就是循環連結清單死循環。原因：多線程并發、擴容進行頭插法。
• jdk1.8版本及以上，HashMap使用了尾插法，解決了循環連結清單發生死鎖的問題。
• 或者使用ConcurrentHashMap也可以解決HashMap線程不安全的問題。它使用了分段鎖，根據需要鎖每個數組，細化鎖的粒度提高性能，jdk1.8取消了分段鎖用cas+synchronize提高性能。

圖解擴容過程，發生死鎖(jdk1.7）

圖文解析：

1、線程1、線程2，線程2在獲得了進行了第一步時（e = A），被線程1原因導緻挂起。此時線程2保留（e = A）

2、線程1進行第一步e = A，next = e.next(就是next = B)，e.next = newTable[i]，newTable[i] = e，e = next（元素A移動到新數組，元素e往下移一個）

動态圖文

線程A記錄了資料b後，next=a.next();，圖狀态

線程B來了，線程A被挂起

線程B進行擴容動态圖

e=next=null，結束傳回。此時線程A繼續運作

此時狀态，正要執行e.next()=table[3]，就是a.next=table[3]

産生環連結清單

傳回b，繼續循環...産生死鎖