• <menu id="sssag"></menu>
  • <menu id="sssag"></menu>
  • HashMap 源碼分析

    每當你想要努力一把的時候,都是未來的你在求救?。?!

    1. 概述

    HashMap 是我們開發中很常用的一個鍵值對集合。底層基于散列算法實現,HashMap 允許 Null 值和 Null 鍵,并且鍵不能重復(重復會被覆蓋),計算鍵的 Hash 值時 Null 鍵的哈希值是 0。另外,HashMap 不保證插入順序,并且 HashMap 是非線程安全的,在多線程下可能會導致一些問題,如:

    • HashMap 進行put操作會引起死循環,導致CPU利用率接近100%(后面有解釋為什么會死循環哦);
    • 多線程本來一共要 put 進1000個不同的鍵,結果只 put 進了 998個。

    2. 原理

    HashMap 底層是基于拉鏈式的散列算法實現的,在 JDK1.7 中是數組+鏈表,在JDK1.8 中是 數組+鏈表+紅黑樹,使用紅黑樹優化過長的鏈表。JDK1.8 中數據結構示意圖:

    JDK1.8 中是 數組+鏈表+紅黑樹。在對HashMap進行增刪查操作時,先要定位到元素所在桶數組的位置,之后再通鏈表或者紅黑樹中定位對應的元素,比如現在要查詢上圖中的元素 35,就有以下步驟:

    1. 定位元素 3 所在的桶數組的位置,index = 35 % 16 = 3;所以元素在數組下標為 3 的位置
    2. 在 3 號下標的位置是一個鏈表,然后遍歷鏈表查詢元素 3

    HashMap 的大致原理就是這樣,下面再看看HashMap的源碼分析。

    3. 源碼分析

    3.1 構造方法分析

    3.1.1 構造方法源碼

    構造方法只會初始化一些重要的變量,比如負載因子和容量。底層的數據結構(如桶數組)是延遲在put 操作時進行初始化的。

    // 構造方法 1
    public HashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
    }
    
    // 構造方法 2
    public HashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }
    
    // 構造方法 3
    public HashMap(int initialCapacity, float loadFactor) {
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);
        this.loadFactor = loadFactor;
        this.threshold = tableSizeFor(initialCapacity);
    }
    
    // 構造方法 4
    public HashMap(Map<? extends K, ? extends V> m) {
        this.loadFactor = DEFAULT_LOAD_FACTOR;
        putMapEntries(m, false);
    }
    

    構造方法 1 是我們平時用的最多的,它默認初始容量為 16,負載因子是 0.75,閾值=初始容量*負載因子。

    構造方法 2 是自定義了初始容量,這里負載因子還是使用默認的 0.75,這里如果自定義的初始容量不是 2 的 n 次冪,會有一個坑,后面講解。

    構造方法 3 是自定義了初始容量和負載因子。

    構造方法 4 是將另一個 Map 中的映射拷貝一份到自己的存儲結構中來,這個方法不是很常用。

    3.1.2 初始容量,負載因子,閾值

    三個名詞介紹

    initialCapacity:HashMap 初始容量,默認 16

    loadFactor:負載因子,默認 0.75

    threshold :當前 HashMap 所能容納鍵值對數量的最大值,超過這個值,則需擴容,等于 initialCapacity*loadFactor
    源碼如下

    // The default initial capacity - MUST be a power of two.
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
    
    /**
         * The maximum capacity, used if a higher value is implicitly specified
         * by either of the constructors with arguments.
         * MUST be a power of two <= 1<<30.
         */
    static final int MAXIMUM_CAPACITY = 1 << 30;
    
    // The load factor used when none specified in constructor.
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
    
    // The next size value at which to resize (capacity * load factor).
    int threshold;
    
    // The load factor for the hash table.
    final float loadFactor;
    
    3.1.3 經典問題

    問題一:為什么HashMap的加載因子是 0.75,不是 0.5 或者 1

    如果負載因子是 1

    如果負載因子是 1,意味著要把 HashMap 填滿之后才擴容,就會發生大量的哈希沖突,然后鏈表變長,鏈表長度達到8就會轉化成紅黑樹,大量的哈希沖突還會使紅黑樹更復雜,查詢效率就會變低??偨Y一句話就是:負載因子越大,空間利用率越高,時間效率就越低

    如果負載因子是 0.5

    如果負載因子是 0.5,就意味著容量達到一半時就要擴容,哈希沖突會減少,查詢效率會變高,但是空間利用率就變低了。

    如果負載因子是 0.75

    負載因子默認 0.75,是時間效率和空間效率的權衡。

    問題二:是HashMap 的數組占用達到閾值就擴容,還是集合中元素總和達到閾值就擴容

    去 debug 一下 HashMap 的源碼就可以知道了,是集合中元素總和達到閾值就會擴容。這里我理解的是這樣可以避免小概率的大量哈希沖突導致紅黑樹復雜度變高吧!

    問題三:如果自定義初始化容量為 18,那實際初始化的容量是多少,經歷一次擴容后又是多少

    先上結論:實際初始化的容量是 32(閾值是 24),經歷一次擴容之后容量是 64

    看上面的構造方法 2 指定了初始化容量,然后構造方法 2是調用了構造方法 3,在構造方法 3 中有這么一行代碼this.threshold = tableSizeFor(initialCapacity);,我們來看看tableSizeFor(initialCapacity) 做了什么:

    static final int tableSizeFor(int cap) {
        int n = cap - 1;
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    }
    

    如果看不懂這個方法,沒關系,我們把這個方法拿出來測試一下,測試代碼如下:

    public class TestHashMap {
        static final int MAXIMUM_CAPACITY = 1 << 30;
    
        public static void main(String[] args) {
            // 這里傳入任何值 ,最后打印的都是大于傳入值的2的n次冪,
            // 如傳入5,返回8;傳入 18,返回 32
            System.out.println(tableSizeFor(5));
        }
    
        static int tableSizeFor(int cap) {
            int n = cap - 1;
            n |= n >>> 1;
            n |= n >>> 2;
            n |= n >>> 4;
            n |= n >>> 8;
            n |= n >>> 16;
            return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
        }
    }
    

    經過上面的測試應該就明白了吧,不管你自定義初始化容量是多大,它都會給你轉化成大于自定義初始化容量,并且最近的一個 2 的 n 次冪??赡苡悬c繞,舉個例子:

    • 如果你自定義初始化容量是 -1,它會給你轉成 1(2的0次冪);
    • 如果你自定義初始化容量是 5,它會給你轉成 8(2的3次冪);
    • 如果你自定義初始化容量是 18,它會給你轉成 32(2的5次冪);

    那有人可能要說了,這里在上面的構造方法中的代碼this.threshold = tableSizeFor(initialCapacity);,明明是給 threshold 賦值的, threshold 不是閾值嘛,它不是初始容量啊,初始容量不應該是 threshold/loadFactor 嗎?這個問題就要說HashMap 的數據結構初始化是在put 操作時延遲初始化的了,留在后面講插入(put 方法)的時候說吧(看了擴容的方法就明白了)。

    問題四:多線程下使用 HashMap 為什么會出現死循環

    • HashMap 是采用鏈表解決哈希沖突,因為是鏈表結構,那么就很容易形成閉合的鏈路,這樣在循環的時候只要有線程對這個 HashMap 進行 get 操作就會產生死循環。
    • 在單線程情況下,只有一個線程對HashMap的數據結構進行操作,是不可能產生閉合的回路的。
    • 那就只有在多線程并發的情況下才會出現這種情況,那就是在 put 操作的時候,如果size>initialCapacity*loadFactor,那么這時候HashMap 就會進行 rehash 操作,隨之HashMap的結構就會發生翻天覆地的變化。很有可能就是在兩個線程在這個時候同時觸發了rehash操作,產生了閉合的回路。

    3.2 插入(put 方法)

    3.2.1 補充說明

    這里先補充一下HashMap的數據結構吧,前面說了在JDK1.8中,HashMap數組+鏈表+紅黑樹實現的??匆幌聰祿Y構的源碼:

    // 數組
    transient Node<K,V>[] table;
    
    // 鏈表
    static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        Node<K,V> next;
        //...
    }
    
    // 紅黑樹
    static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
        TreeNode<K,V> parent;  // red-black tree links
        TreeNode<K,V> left;
        TreeNode<K,V> right;
        TreeNode<K,V> prev;    // needed to unlink next upon deletion
        boolean red;
        TreeNode(int hash, K key, V val, Node<K,V> next) {
            super(hash, key, val, next);
        }
        //...
    }
    
    
    3.2.1 插入方法

    話不多說,直接看我們常用的 put 方法

    public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }
    

    在這里調用了putVal 方法進行插入,并計算了 key 的哈希值,先看看哈希值怎么計算的:

    static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }
    

    可以看到這里并不是直接使用hashcode() 方法去計算哈希值的,而是這樣操作的:

    • 如果 key 是 null,哈希值就會 0;
    • 如果 key 不是 null,就獲取對象的哈希值然后再進行位移和異或操作,獲取最終的哈希值。

    這里引出一個問題,為什么取到哈希值之后要進行位移和異或操作?

    先上結論:就是為了減少哈希碰撞,讓元素更均勻的分布在散列表中。

    再看原因:

    • 如果直接使用key.hashCode()作為hash值的話,存在一些問題:

      HashMap 的默認長度為16,并且是通過(table.length - 1) & hash的方式得到 key 在 table 數組中的下標。

      如果key1.hashCode()=1661580827(二進制為0110,0011,0000,1001,1011,0110,0001,1011),key2.hashCode()=1661711899(二進制為0110,0011,0000,1011,1011,0110,0001,1011)。

      在與掩碼進行與的過程中,只有后4位起作用,導致(table.length - 1) & hash得到的下標值均為11,導致高位完全失效,加大了沖突的可能性。

      一句話總結:就是如果不進行位移和異或的操作,在計算元素所處的 table 數組下標的位置時,哈希值的二進制高位就會失效,只有低位參與計算,增大了哈希沖突的可能性

    • 如果通過高位向低位異或傳播的話,高位同樣參與到key在table中下標的運算,減少了碰撞的可能性

      key1.hashCode() ^ (key1.hashCode() >>>16)=1661588754(二進制為0110,0011,0000,1001,1101,0101,0001,0010)

      key2.hashCode() ^ (key2.hashCode() >>>16)=1661719824(二進制為0110,0011,0000,1011,1101,0101,0001,0000)

      在和掩碼進行與操作((table.length - 1) & hash)得到的下標分別為2和0,減少了沖突的可能性。

    上面說了hash(Object key) 方法,我們接著往下看,就是 put 方法實際調用的 putVal

    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        // 初始化桶數組 table,table 被延遲到插入新數據時再進行初始化
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        // 計算當前元素的key的下標位置,并判斷這個下標位置是不是空的,不是空的就直接將元素放在這里
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
            Node<K,V> e; K k;
            // 如果鍵的值以及節點 hash 等于鏈表中的第一個鍵值對節點時,則將 e 指向該鍵值對
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            // 如果桶中的引用類型為 TreeNode,則調用紅黑樹的插入方法
            else if (p instanceof TreeNode)
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {
                // 對鏈表進行遍歷,并統計鏈表長度, binCount 就是鏈表的長度
                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;
                    }
                    // 條件為 true,表示當前鏈表包含要插入的鍵值對,終止遍歷
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            
            // 判斷要插入的鍵值對是否存在 HashMap 中,如果存在,前面就已經給 e 賦值了
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                // onlyIfAbsent 表示是否僅在 oldValue 為 null 的情況下更新鍵值對的值
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        // 鍵值對數量超過閾值時,則進行擴容
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }
    

    上面寫在代碼中的注釋已經比較清楚了,putVal 主要做了以下幾件事情:

    1. 當桶數組 table 為空時,通過擴容的方式初始化 table(這里第一次put的時候就會進行一次擴容,其實就是初始化 table)
    2. 查找要插入的鍵值對是否已經存在,存在的話根據條件判斷是否用新值替換舊值
    3. 如果不存在,則將鍵值對鏈入鏈表中(是放在鏈表尾部哦),并根據鏈表長度決定是否將鏈表轉為紅黑樹
    4. 判斷鍵值對數量是否大于閾值,大于的話則進行擴容操作

    3.3 擴容(resize 方法)

    擴容方法相對會復雜一點,先說一下擴容的大概過程:

    • put 第一個元素時,會先初始化數據結構,按照默認的是初始化容量為 16,負載因子是 0.75
    • HashMap 中的鍵值對達到 最大容量*負載因子(也就是 12)之后,會進行擴容。
    • 擴容就是將數組(table)的長度變為原來的 2 倍,閾值也會變為原來的 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;
        // 如果 table 不為空,表明已經初始化過了
        if (oldCap > 0) {
            // 當 table 容量超過容量最大值,則不再擴容
            if (oldCap >= MAXIMUM_CAPACITY) {
                threshold = Integer.MAX_VALUE;
                return oldTab;
            }
            // 按舊容量和閾值的2倍計算新容量和閾值的大小
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)
                newThr = oldThr << 1; // double threshold
        }
        else if (oldThr > 0) // initial capacity was placed in threshold
            // 初始化時,將 threshold 的值賦值給 newCap
            // HashMap 使用 threshold 變量暫時保存 initialCapacity 參數的值
            newCap = oldThr;
        else {               // zero initial threshold signifies using defaults
            // 調用無參構造方法時,桶數組容量為默認容量
            // 閾值為默認容量與默認負載因子乘積
            newCap = DEFAULT_INITIAL_CAPACITY;
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        }
        // newThr 為 0 時,按閾值計算公式進行計算
        if (newThr == 0) {
            float ft = (float)newCap * loadFactor;
            newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                      (int)ft : Integer.MAX_VALUE);
        }
        threshold = newThr;
        
        // 創建新的桶數組,桶數組的初始化也是在這里完成的
        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
        table = newTab;
        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)
                        // 如果 oldTable 此處下表位置就一個元素,則直接填充到 newTab
                        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;
                        }
                    }
                }
            }
        }
        return newTab;
    }
    

    這個源碼稍微有點長,可以多看幾遍。主要做了以下幾件事情:

    • 計算新桶數組的容量 newCap 和新閾值 newThr
    • 根據計算出的 newCap 創建新的桶數組,桶數組 table 也是在這里進行初始化的
    • 將鍵值對節點重新映射到新的桶數組里。如果節點是 TreeNode 類型,則需要拆分紅黑樹。如果是普通節點,則節點按原順序進行分組。(具體情況后面紅黑樹和鏈表互相轉換時講解)

    這里也查閱了一些資料,關于 JDK1.7JDK1.8 擴容的區別:

    JDK 1.8 版本下 HashMap 擴容效率要高于之前版本。如果大家看過 JDK 1.7 的源碼會發現,JDK 1.7 為了防止因 hash 碰撞引發的拒絕服務攻擊,在計算 hash 過程中引入隨機種子。以增強 hash 的隨機性,使得鍵值對均勻分布在桶數組中。在擴容過程中,相關方法會根據容量判斷是否需要生成新的隨機種子,并重新計算所有節點的 hash。而在 JDK 1.8 中,則通過引入紅黑樹替代了該種方式。從而避免了多次計算 hash 的操作,提高了擴容效率。

    3.4 鏈表轉為紅黑樹

    很多資料說當鏈表長度達到 8 的時候,就會轉化為紅黑樹,我們先看一下源碼,到底是不是這樣:

    來吧,看一下treeifyBin 方法的源碼:

    static final int TREEIFY_THRESHOLD = 8;
    
    static final int MIN_TREEIFY_CAPACITY = 64;   
    // 將普通節點鏈表轉換成樹形節點鏈表
    final void treeifyBin(Node<K,V>[] tab, int hash) {
        int n, index; Node<K,V> e;
        // 桶數組容量小于 MIN_TREEIFY_CAPACITY,優先進行擴容而不是樹化
        if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
            resize();
        else if ((e = tab[index = (n - 1) & hash]) != null) {
            // hd 為頭節點(head),tl 為尾節點(tail)
            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);
        }
    }
    
    TreeNode<K,V> replacementTreeNode(Node<K,V> p, Node<K,V> next) {
        return new TreeNode<>(p.hash, p.key, p.value, next);
    }
    

    看看上面的代碼和截圖,可以很清楚,鏈表樹化需要兩個條件

    • 鏈表長度大于等于 TREEIFY_THRESHOLD

      就是我們常說的當鏈表長度大于 8 的時候,鏈表轉化為紅黑樹

    • 桶數組容量大于等于 MIN_TREEIFY_CAPACITY

      實際上進入轉化為紅黑樹的方法中(treeifyBin 方法)可以看到:桶數組(table數組)長度小于 64 時會優先進行擴容操作,而不是直接將鏈表轉化為紅黑樹。

      我的理解是當 table 數組長度比較小的時候,鍵的哈希碰撞會比較嚴重,導致鏈表變長,這個時候可以選擇優先進行擴容。畢竟高碰撞率是因為桶數組容量較小引起的。容量小時,優先擴容可以避免一些列的不必要的樹化過程。并且桶容量較小時,擴容會比較頻繁,擴容時需要拆分紅黑樹并重新映射(這個擴容方法中有)。所以在桶容量比較小的情況下,將長鏈表轉成紅黑樹,然后再經歷擴容,可能又將紅黑樹拆分轉成鏈表了,這是一件吃力不討好的事情。

    我們繼續說上面的 treeifyBin 方法,這個方法主要是將普通鏈表轉化為由 TreeNode 節點組成的鏈表,再調用treeify 方法將其轉化為紅黑樹??梢粤私庖幌?,HashMap 中的內部類TreeNode繼承了LinkedHashMap.Entry,LinkedHashMap.Entry 又繼承了 HashMap.Node。

    所以 TreeNode 里面還是包含有 next 引用的,這個在后面紅黑樹轉化為鏈表就會很有用了,后面再說哦。

    先來畫個圖,假設在樹化之前,HashMap 里面的數據是這樣的:

    然后說說調用treeify 方法將TreeNode 鏈表轉化為紅黑樹吧,因為紅黑樹的結構特點(自己去了解哦),這個就涉及到 key 的比較了,這里直接說一下怎么比較的(就不再深追了):

    • 比較鍵與鍵之間 hash 的大小,如果 hash 相同,繼續往下比較
    • 檢測鍵類是否實現了 Comparable 接口,如果實現調用 compareTo 方法進行比較
    • 如果仍未比較出大小,就需要進行仲裁了,仲裁方法為 tieBreakOrder

    通過上面說的三種比較,就可以按照紅黑樹的結構特性去構造紅黑樹了,樹化后是這樣子的:

    黃色箭頭代表TreeNode 保留的next引用,其實還有 prev 引用,這里就不畫了。這里就是說明鏈表轉化為紅黑樹后,原來鏈表的順序結構依然保留著,這樣就可以按照鏈表的方式去遍歷紅黑樹,而且這個結構給后面紅黑樹轉化成鏈表提供了便利。

    那下面再看一下紅黑樹轉化為鏈表是怎么操作的吧!

    3.5 紅黑樹轉為鏈表

    3.5.1 紅黑樹拆分

    再回去看看擴容的方法吧,里面有這么一行代碼:((TreeNode<K,V>)e).split(this, newTab, j, oldCap);,它就是拆分紅黑樹的。擴容的時候所有節點都需要重新計算位置,所以肯定要拆分紅黑樹。

    擴容后,所有節點(包括數組,鏈表節點,紅黑樹節點)都要重新計算下標位置,上面說到鏈表轉化為紅黑樹時,通過兩個額外的引用 nextprev 保留了原鏈表的節點順序。這樣拆分紅黑樹重新計算下標時,就可以直接按照鏈表的方式拆分了,一定程度上是提升了效率的。

    上面說了紅黑樹拆分的大致邏輯,下面看一下源碼中怎么拆分的:

    // 紅黑樹轉鏈表閾值
    static final int UNTREEIFY_THRESHOLD = 6;
    
    final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
        TreeNode<K,V> b = this;
        // Relink into lo and hi lists, preserving order
        TreeNode<K,V> loHead = null, loTail = null;
        TreeNode<K,V> hiHead = null, hiTail = null;
        int lc = 0, hc = 0;
        // 紅黑樹節點仍然保留了 next 引用,故仍可以按鏈表方式遍歷紅黑樹。
        // 下面的循環是對紅黑樹節點進行分組,與上面類似
        for (TreeNode<K,V> e = b, next; e != null; e = next) {
            next = (TreeNode<K,V>)e.next;
            e.next = null;
            if ((e.hash & bit) == 0) {
                if ((e.prev = loTail) == null)
                    loHead = e;
                else
                    loTail.next = e;
                loTail = e;
                ++lc;
            }
            else {
                if ((e.prev = hiTail) == null)
                    hiHead = e;
                else
                    hiTail.next = e;
                hiTail = e;
                ++hc;
            }
        }
    
        if (loHead != null) {
            // 如果 loHead 不為空,且鏈表長度小于等于 6,則將紅黑樹轉成鏈表
            if (lc <= UNTREEIFY_THRESHOLD)
                tab[index] = loHead.untreeify(map);
            else {
                tab[index] = loHead;
                // hiHead == null 時,表明擴容后
                // 所有節點仍在原位置,樹結構不變,無需重新樹化
                if (hiHead != null) // (else is already treeified)
                    loHead.treeify(tab);
            }
        }
        
        // 與上面類似
        if (hiHead != null) {
            if (hc <= UNTREEIFY_THRESHOLD)
                tab[index + bit] = hiHead.untreeify(map);
            else {
                tab[index + bit] = hiHead;
                if (loHead != null)
                    hiHead.treeify(tab);
            }
        }
    }
    

    重新映射紅黑樹的邏輯和重新映射鏈表的邏輯基本一致。只是重新映射后,會將紅黑樹拆分成兩條由 TreeNode 組成的鏈表。如果鏈表長度小于 UNTREEIFY_THRESHOLD,則將鏈表轉換成普通鏈表。否則根據條件重新將 TreeNode 鏈表樹化。舉個例子說明一下,假設擴容后,重新映射上圖的紅黑樹,映射結果如下:

    3.5.2 紅黑樹鏈化

    在上面的 split 方法中,當鏈表長度小于等于 6 時,就會調用 tab[index] = loHead.untreeify(map); 將紅黑樹轉化為鏈表。

    上面說了,紅黑樹中仍然保留了原鏈表節點順序。這樣想將紅黑樹轉化為鏈表就很簡單了,只需要將TreeNode 鏈表轉化為 Node 鏈表就可以了。

    final Node<K,V> untreeify(HashMap<K,V> map) {
        Node<K,V> hd = null, tl = null;
        // 遍歷 TreeNode 鏈表,并用 Node 替換
        for (Node<K,V> q = this; q != null; q = q.next) {
            // 替換節點類型
            Node<K,V> p = map.replacementNode(q, null);
            if (tl == null)
                hd = p;
            else
                tl.next = p;
            tl = p;
        }
        return hd;
    }
    
    Node<K,V> replacementNode(Node<K,V> p, Node<K,V> next) {
        return new Node<>(p.hash, p.key, p.value, next);
    }
    

    3.6 查找(get 方法)

    到這里,最難啃的骨頭基本上啃完了。

    先說一下思想:先定位鍵值對所在的桶的下標位置(就是在數組的哪個位置),然后去查找鏈表或紅黑樹。

    下面就看一下 HashMap 的查找方法,上源碼:

    public V get(Object key) {
        Node<K,V> e;
        return (e = getNode(hash(key), key)) == null ? null : e.value;
    }
    

    計算哈希值的方法就不說了吧,和插入(put)數據時是一致的。如果 key 是 null,下標位置就是 0,就直接返回它的值。否則就調用 getNode 方法了。

    看看getNode 方法:

    final Node<K,V> getNode(int hash, Object key) {
        Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
        // 1. 定位鍵值對所在桶的位置
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (first = tab[(n - 1) & hash]) != null) {
            // 如果下標位置的第一個節點就是要查找的節點,就直接返回
            if (first.hash == hash && // always check first node
                ((k = first.key) == key || (key != null && key.equals(k))))
                return first;
            if ((e = first.next) != null) {
                // 2. 如果 first 是 TreeNode 類型,則調用黑紅樹查找方法
                if (first instanceof TreeNode)
                    return ((TreeNode<K,V>)first).getTreeNode(hash, key);
                // 2. 對鏈表進行查找
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        return e;
                } while ((e = e.next) != null);
            }
        }
        return null;
    }
    

    上面的注釋比較清楚了,紅黑樹的查找自己看看源碼了解一下吧,這里就不贅述了。

    3.7 遍歷

    遍歷操作也是一個高頻操作,我們一般使用的遍歷方式有以下幾種:

    // 遍歷方式 1
    for(Object key : map.keySet()) {
        // do something
    }
    
    // 遍歷方式 2
    for(HashMap.Entry entry : map.entrySet()) {
        // do something
    }
    
    // 遍歷方式 3
    Set keys = map.keySet();
    Iterator ite = keys.iterator();
    while (ite.hasNext()) {
        Object key = ite.next();
        // do something
    }
    

    上面的幾種遍歷方式,可以看出來遍歷Map集合時,都是對 HashMap 的 key 集合或 Entry 集合進行遍歷。

    看一下遍歷相關的源碼吧:

    public Set<K> keySet() {
        Set<K> ks = keySet;
        if (ks == null) {
            ks = new KeySet();
            keySet = ks;
        }
        return ks;
    }
    
    // 鍵集合
    final class KeySet extends AbstractSet<K> {
        public final int size()                 { return size; }
        public final void clear()               { HashMap.this.clear(); }
        public final Iterator<K> iterator()     { return new KeyIterator(); }
        public final boolean contains(Object o) { return containsKey(o); }
        public final boolean remove(Object key) {
            return removeNode(hash(key), key, null, false, true) != null;
        }
        public final Spliterator<K> spliterator() {
            return new KeySpliterator<>(HashMap.this, 0, -1, 0, 0);
        }
        public final void forEach(Consumer<? super K> action) {
            Node<K,V>[] tab;
            if (action == null)
                throw new NullPointerException();
            if (size > 0 && (tab = table) != null) {
                int mc = modCount;
                for (int i = 0; i < tab.length; ++i) {
                    for (Node<K,V> e = tab[i]; e != null; e = e.next)
                        action.accept(e.key);
                }
                if (modCount != mc)
                    throw new ConcurrentModificationException();
            }
        }
    }
    
    // 鍵迭代器
    final class KeyIterator extends HashIterator
        implements Iterator<K> {
        public final K next() { return nextNode().key; }
    }
    
    abstract class HashIterator {
        Node<K,V> next;        // next entry to return
        Node<K,V> current;     // current entry
        int expectedModCount;  // for fast-fail
        int index;             // current slot
    
        HashIterator() {
            expectedModCount = modCount;
            Node<K,V>[] t = table;
            current = next = null;
            index = 0;
            if (t != null && size > 0) { // advance to first entry
                // 尋找第一個包含鏈表節點引用的桶
                do {} while (index < t.length && (next = t[index++]) == null);
            }
        }
    
        public final boolean hasNext() {
            return next != null;
        }
    
        final Node<K,V> nextNode() {
            Node<K,V>[] t;
            Node<K,V> e = next;
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
            if (e == null)
                throw new NoSuchElementException();
            if ((next = (current = e).next) == null && (t = table) != null) {
                // 尋找下一個包含鏈表節點引用的桶
                do {} while (index < t.length && (next = t[index++]) == null);
            }
            return e;
        }
    
        public final void remove() {
            Node<K,V> p = current;
            if (p == null)
                throw new IllegalStateException();
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
            current = null;
            K key = p.key;
            removeNode(hash(key), key, null, false, false);
            expectedModCount = modCount;
        }
    }
    

    不知道細心的你有沒有發現一個問題,多次遍歷一個 HashMap 集合時,遍歷出來的順序是一樣的,然而遍歷出來的這個順序又和插入順序不一樣。那我們就拿這個圖看一下吧:

    不管插入順序是怎樣,最后存到HashMap中的結構就是上圖這樣的,相信這篇文章看到這里,也不用再解釋為什么了吧。

    然而在遍歷時,會先從table數組的 0 下標開始往后遍歷。找到包含鏈表節點引用的桶,對應圖中就是 12 號桶,隨后由遍歷該桶所指向的鏈表。遍歷完 12 號桶后,會繼續尋找下一個不為空的桶,對應圖中的 28 號桶。之后流程和上面類似,直至遍歷完最后一個桶。

    遍歷的方法就到這里了,再思考一個問題,遍歷的過程中并沒有看到遍歷紅黑樹的代碼,那紅黑樹怎么遍歷?如果你還不知道,就再回到上面看一下鏈表是怎么轉為紅黑樹的吧(紅黑樹保留了 原始的鏈表結構)!

    3.8 刪除

    刪除操作的三個步驟:

    • 確定元素在table數組的下標位置
    • 遍歷鏈表并找到鍵值對應的節點
    • 刪除節點

    上源碼:

    public V remove(Object key) {
        Node<K,V> e;
        return (e = removeNode(hash(key), key, null, false, true)) == null ?
            null : e.value;
    }
    
    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 &&
            // 1. 定位桶位置
            (p = tab[index = (n - 1) & hash]) != null) {
            // 這個 node 就是記錄要刪除的那個節點
            Node<K,V> node = null, e; K k; V v;
            // 如果鍵的值與鏈表第一個節點相等,也就是說第一個就是要刪除的節點,則將 node 指向該節點
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                node = p;
            else if ((e = p.next) != null) {
                // 如果是 TreeNode 類型,調用紅黑樹的查找邏輯定位待刪除節點,將待刪除的節點賦值給node
                if (p instanceof TreeNode)
                    node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
                else {
                    // 2. 遍歷鏈表,找到待刪除節點,并將待刪除的節點賦值給 node
                    do {
                        if (e.hash == hash &&
                            ((k = e.key) == key ||
                             (key != null && key.equals(k)))) {
                            node = e;
                            break;
                        }
                        p = e;
                    } while ((e = e.next) != null);
                }
            }
            // 3. 刪除節點,并修復鏈表或紅黑樹
            if (node != null && (!matchValue || (v = node.value) == value ||
                                 (value != null && value.equals(v)))) {
                // 如果是紅黑樹的結構,就調用刪除紅黑樹節點的方法
                if (node instanceof TreeNode)
                    ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
                else if (node == p)
                    tab[index] = node.next;
                else
                    p.next = node.next;
                ++modCount;
                --size;
                afterNodeRemoval(node);
                return node;
            }
        }
        return null;
    }
    

    紅黑樹中的節點怎么刪除的就不要再看了,傷腦筋,哈哈?。?!

    在這里插入圖片描述

    posted @ 2022-03-07 20:22  下半夜的風  閱讀(23)  評論(0編輯  收藏  舉報
    国产在线码观看超清无码视频,人妻精品动漫H无码,十大看黄台高清视频,国产在线无码视频一区二区三区,国产男女乱婬真视频免费,免费看女人的隐私超爽,狠狠色狠狠色综合久久蜜芽