Map集合之HashMap的使用及說明

2022-10-14 14:02:21

HashMap 概述

HashMap 是通過 put(key,value) 儲存，get(key)來獲取。當傳入 key 時，HashMap 會根據 key 的 hashCode() 方法計算出 hash 值，根據 hash 值將 value 儲存在 bucket(桶)裡。當計算出的 hash 值相同時，稱之為 hash 衝突。HashMap 的做法是用連結串列和紅黑樹儲存相同 hash 值的 value

jdk 1.8 之前與之後的 HashMap

在 jdk1.8 之前的 HashMap 是由陣列 + 連結串列來實現的，陣列是 HashMap 的主體。連結串列主要是為了解決 hash 衝突的
在 jdk1.8 之後的 HashMap 是由陣列 + 連結串列 + 紅黑樹來實現的，在解決 hash 衝突時有了較大的變化。當連結串列長度大於閾值 8 時，並且陣列的長度大於 64 時，此時此索引位置上的所有資料改為使用紅黑樹儲存

HashMap 的陣列，連結串列，紅黑樹之間的轉換

當建立 HashMap 集合物件的時候，在 jdk1.8 之前，是在它的構造方法中建立了一個預設長度是 16 的 Entry[] table 的陣列來儲存鍵值對資料的。而從 jdk1.8開始，是在第一次呼叫 put 方法時建立了一個預設長度是 16 的 Node[] table 的陣列來儲存鍵值對資料的
陣列建立完成後，當新增一個元素(key,value)時，首先計算元素 key 的 hash 值，以此確定插入陣列中的位置。但是可能存在同一 hash 值的元素已經被放在陣列同一位置了，這時就新增到同一 hash 值的元素的後面，他們在陣列的同一位置，這就形成了單連結串列，同一各連結串列上的 Hash 值是相同的。當連結串列長度大於閾值 8 時，並且陣列的長度大於 64 時，此時此索引位置上的所有資料改為使用紅黑樹儲存，這樣大大提高了查詢的效率
在轉換為紅黑樹儲存資料後，如果此時再次刪除資料，當紅黑樹的節點數小於 6 時，那麼此時的紅黑樹將轉換為單連結串列結構來儲存資料

HashMap 擴容機制

預設情況下，陣列大小為 16，那麼當 HashMap 中元素個數超過 16 * 0.75 = 12（這個值就是程式碼中的 threshold 值，也叫做臨界值）的時候，就把陣列的大小擴充套件為 2*16 = 32，即擴大一倍，然後重新計算每個元素在陣列中的位置

0.75 這個值稱為負載因子，那麼為什麼負載因子為 0.75 呢? 這是通過大量實驗統計得出來的，如果過小，比如 0.5，那麼當存放的元素超過一半時就進行擴容，會造成資源的浪費；如果過大，比如 1，那麼當元素滿的時候才進行擴容，會使 get,put 操作的碰撞機率增加

HashMap 原始碼

HashMap 的基本屬性

public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable {
    // 序列號
    private static final long serialVersionUID = 362498820763181265L;    
    // 預設的初始容量是16
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;   
    // 最大容量
    static final int MAXIMUM_CAPACITY = 1 << 30; 
    // 預設的填充因子
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
    // 當桶(bucket)上的結點數大於這個值時會轉成紅黑樹;+對應的table的最小大小為64，即MIN_TREEIFY_CAPACITY ；這兩個條件都滿足，會連結串列會轉紅黑樹
    static final int TREEIFY_THRESHOLD = 8; 
    // 當桶(bucket)上的結點數小於這個值時樹轉連結串列
    static final int UNTREEIFY_THRESHOLD = 6;
    // 桶中結構轉化為紅黑樹對應的table的最小大小
    static final int MIN_TREEIFY_CAPACITY = 64;
    // 儲存元素的陣列，總是2的冪次倍
    transient Node<k,v>[] table; 
    // 存放具體元素的集
    transient Set<map.entry<k,v>> entrySet;
    // 存放元素的個數，注意這個不等於陣列的長度。
    transient int size;
    // 每次擴容和更改map結構的計數器
    transient int modCount;   
    // 臨界值 當實際大小(容量*填充因子)超過臨界值時，會進行擴容
    int threshold;
    // 填充因子
    final float loadFactor;
}

HashMap 中涉及到的資料結構

連結串列節點（單連結串列）

Node 是 HashMap 的一個內部類，實現了 Map.Entry 介面，本質上是一個單連結串列的資料結構。連結串列中的每個節點就是一個 Node 物件

static class Node<k,v> implements Map.Entry<k,v> {
    final int hash;
    final K key;
    V value;
    Node<k,v> next; // 下一個節點
    
    Node(int hash, K key, V value, Node<k,v> next) {
        this.hash = hash;
        this.key = key;
        this.value = value;
        this.next = next;
    }
 
    public final K getKey()        { return key; }
    public final V getValue()      { return value; }
    public final String toString() { return key + = + value; }
 
    public final int hashCode() {
        return Objects.hashCode(key) ^ Objects.hashCode(value);
    }
 
    public final V setValue(V newValue) {
        V oldValue = value;
        value = newValue;
        return oldValue;
    }
    // 判斷兩個node是否相等,若key和value都相等，返回true。可以與自身比較為true
    public final boolean equals(Object o) {
        if (o == this)
            return true;
        if (o instanceof Map.Entry) {
            Map.Entry<!--?,?--> e = (Map.Entry<!--?,?-->)o;
            if (Objects.equals(key, e.getKey()) &&
                Objects.equals(value, e.getValue()))
                return true;
        }
        return false;
    }
}

紅黑樹節點

紅黑樹比連結串列多了四個變數，parent 父節點、left 左節點、right 右節點、prev上一個同級節點

static final class TreeNode<k,v> extends LinkedHashMap.Entry<k,v> {
    TreeNode<k,v> parent;  // 父節點
    TreeNode<k,v> left; // 左子樹
    TreeNode<k,v> right;// 右子樹
    TreeNode<k,v> prev; // 刪除時需要取消下一個連結
    boolean red;    // 顏色屬性
    TreeNode(int hash, K key, V val, Node<k,v> next) {
        super(hash, key, val, next);
    }
 
    // 返回當前節點的根節點
    final TreeNode<k,v> root() {
        for (TreeNode<k,v> r = this, p;;) {
            if ((p = r.parent) == null)
                return r;
            r = p;
        }
    }
    
    // ......省略
}

位桶

儲存（位桶）的陣列

transient Node<K,V>[] table;

HashMap 類中有一個非常重要的欄位，就是 Node[] table，即雜湊桶陣列，明顯它是一個 Node 的陣列

HashMap 的 put() 方法

陣列判斷

判斷 tab[] 陣列是否為 null 或長度為 0，如果是 null 或長度為 0；則通過 resize() 方法初始化陣列，並獲取長度
如果單連結串列 Node<K,V> p == tab[i = (n - 1) & hash]) == null，就直接 put 進單連結串列中，說明此時並沒有發生 hash 衝突
如果該陣列索引位置之前放入過資料，在通過 key 的 hash 值，(k = p.key) == key || (key != null && key.equals(k)) 判斷該 put 的資料是否與陣列索引位置資料相同；如果相同，使用 e = p 來則初始化陣列 Node<K,V> e

紅黑樹判斷

如果不相同，則判斷是否是紅黑樹，如果是紅黑樹就直接插入樹中

連結串列判斷

如果不是紅黑樹，就遍歷連結串列每個節點，並判斷連結串列末尾節點是否為 null；如果為 null，則在該單連結串列末尾節點插入資料，並判斷是否 binCount > 8 -1，為 true 的話會呼叫 treeifyBin(tab, hash) 方法，該方法在後面詳解
然後，判斷該 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) {
    // tab表示 Node<K,V>型別的陣列，p表示某一個具體的單連結串列 Node<K,V> 節點
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    // 判斷 table[] 是否為空，如果是空的就建立一個 table[]，並獲取他的長度n
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;    
    // tab[i = (n - 1) & hash] 表示陣列中的某一個具體位置的資料
    // 如果單連結串列 Node<K,V> p == tab[i = (n - 1) & hash]) == null，
    // 就直接 put 進單連結串列中，說明此時並沒有發生 Hash 衝突
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        // 說明索引位置已經放入過資料了，已經在單連結串列處產生了Hash衝突
        Node<K,V> e; K k;
        // 判斷 put 的資料和之前的資料是否重複
        if (p.hash == hash &&
            // 進行 key 的 hash 值和 key 的 equals() 和 == 比較，如果都相等，則初始化節點 Node<K,V> e
            ((k = p.key) == key || (key != null && key.equals(k))))               
            e = p;
        // 判斷是否是紅黑樹，如果是紅黑樹就直接插入樹中
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
            // 如果不是紅黑樹，就遍歷每個節點，判斷單連結串列長度是否大於等於 7，
            // 如果單連結串列長度大於等於 7，陣列的長度小於 64 時，會優先選擇擴容
            // 如果單連結串列長度大於等於 7，陣列的長度大於 64 時，才會選擇單連結串列--->紅黑樹
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    // 採用尾插法，在單連結串列中插入資料
                    p.next = newNode(hash, key, value, null);
                    // 如果 binCount >= 8 - 1
                    if (binCount >= TREEIFY_THRESHOLD - 1) 
                        treeifyBin(tab, hash);
                        break;
                }
                // 判斷索引每個元素的key是否可要插入的key相同，如果相同就直接覆蓋
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                 p = e;
            }
        }
        if (e != null) { 
            // 此時說明 key 的 hash 值和 key 的 equals() 和 == 比較結果都相等
            // 說明陣列或者單連結串列中有完全相同的 key
            // 只需要將 value 覆蓋，並將 oldValue 返回即可
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
                afterNodeAccess(e);
                  return oldValue;
        }
    }
    // 說明沒有key相同，因此要插入一個key-value，並記錄內部結構變化次數
    ++modCount;
    // 判斷是否擴容
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

HashMap 的 get() 方法

首先定位鍵值對所在桶的位置，之後再對連結串列或紅黑樹進行查詢

判斷表或 key 是否是 null，如果是直接返回 null key 對應的 value
判斷索引處第一個 key 與傳入 key 是否相等，如果相等直接返回
如果不相等，判斷連結串列是否是紅黑二元樹，如果是，直接從樹中取值
如果不是樹，就遍歷連結串列查詢

public V get(Object key) {
    Node<K,V> e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}
final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    // 1.如果表不是空的，並且要查詢索引處有值，就判斷位於第一個的key是否是要查詢的key
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        // 1.1.檢查要查詢的是否是第一個節點
        if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
            // 1.2.沿著第一個節點繼續查詢
            if ((e = first.next) != null) {
                // 1.2.1.如果是紅黑樹，那麼呼叫紅黑樹的方法查詢
                if (first instanceof TreeNode)
                    return ((TreeNode<K,V>)first).getTreeNode(hash, key);
                // 1.2.2.如果是連結串列，那麼採用連結串列的方式查詢
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}

HashMap 的 remove 方法

HashMap 的刪除操作並不複雜，僅需三個步驟即可完成

定位桶位置
遍歷連結串列或紅黑樹並找到鍵值相等的節點
刪除節點

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) {
       // ------------------1. 查詢到要刪除的節點------------------                       
    // tab當前陣列，n當前陣列容量，p根據hash從陣列上找到的節點，index p節點在陣列上的位置                      
    Node<K,V>[] tab; Node<K,V> p; int n, index;
    // 當陣列存在且陣列容量大於0，且p節點存在
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (p = tab[index = (n - 1) & hash]) != null) {
        Node<K,V> node = null, e; K k; V v;
        // 當 p 的 hash 等於引數 hash，且 p 的 key 等於引數 key
        // p節點就是當前要刪除的節點，將node指向p
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            node = p;
        // 當p節點不是要刪除的節點時，說明p節點上有紅黑樹或者連結串列
        else if ((e = p.next) != null) {
            // p如果是紅黑樹,通過getTreeNode()查詢節點
            if (p instanceof TreeNode)
                node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
            // p是連結串列，迴圈連結串列查詢節點
            else {
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key ||
                         (key != null && key.equals(k)))) {
                        node = e;
                        break;
                    }
                    p = e;
                } while ((e = e.next) != null);
            }
        }
        // ------------------2. 刪除查詢到的節點------------------
        // 如果查詢到的node存在且machValue為false或v等於value
        if (node != null && (!matchValue || (v = node.value) == value ||
                             (value != null && value.equals(v)))) {
            // 如果node是TreeNode則使用removeTreeNode刪除節點
            if (node instanceof TreeNode)
                ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
            // 如果node等於p，說明移除連結串列頭，將node的後節點放到陣列上  
            else if (node == p)
                tab[index] = node.next;
            // 說明移除的不是連結串列頭，根據上方的迴圈可得，node是p的後節點，將p的後節點指向node的後節點
            else
                p.next = node.next;
            // 增加修改次數，減少當前陣列長度
            ++modCount;
            --size;
            afterNodeRemoval(node);
            return node;
        }
    }
    return null;
}

HashMap 的 treeifyBin() 方法

當桶中連結串列長度超過 TREEIFY_THRESHOLD（預設為 8）時，就會呼叫 treeifyBin() 方法進行樹化操作。

但此時並不一定會樹化，因為在 treeifyBin()方法中還會判斷 HashMap 的陣列容量是否大於等於 64。

如果容量大於等於 64，那麼進行樹化，否則優先進行擴容

final void treeifyBin(Node<K,V>[] tab, int hash) {
 
    int n, index; Node<K,V> e;
    /*
     * 如果元素陣列為空 或者 陣列長度小於 樹結構化的最小限制
     * MIN_TREEIFY_CAPACITY 預設值64，對於這個值可以理解為：如果元素陣列長度小於這個值，沒有必要去進行結構轉換
     * 當一個陣列位置上集中了多個鍵值對，那是因為這些key的hash值和陣列長度取模之後結果相同。（並不是因為這些key的hash值相同）
     * 因為hash值相同的概率不高，所以可以通過擴容的方式，來使得最終這些key的hash值在和新的陣列長度取模之後，拆分到多個陣列位置上。
     */
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
        resize(); // 擴容
 
    // 如果元素陣列長度已經大於等於了 MIN_TREEIFY_CAPACITY，那麼就有必要進行結構轉換了
    // 根據hash值和陣列長度進行取模運算後，得到連結串列的首節點
    else if ((e = tab[index = (n - 1) & hash]) != null) { 
        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); // 繼續遍歷連結串列
 
        // 到目前為止 也只是把Node物件轉換成了TreeNode物件，把單向連結串列轉換成了雙向連結串列
 
        // 把轉換後的雙向連結串列，替換原來位置上的單向連結串列
        if ((tab[index] = hd) != null)
            hd.treeify(tab);//此處單獨解析
    }
}

如果 tab 陣列為 null或 tab 的陣列長度 < 64 時，呼叫 resize() 方法
否則，會將連結串列轉換為紅黑樹（是為了提高查詢效能，元素越多，連結串列的查詢效能越差）
說明了連結串列轉換為紅黑樹的條件：當連結串列長度大於閾值 8 時，並且陣列的長度大於 64 時，此時此索引位置上的所有資料改為使用紅黑樹儲存

HashMap 如何解決 Hash 衝突

hash 衝突：在 put 多個元素時，通過 key 的 hashCode() 方法計算出的值是一樣的，是同一個儲存地址。當後面的元素要插入到這個地址時，發現已經被佔用了，這時候就產生了 hash 衝突。當發生 hash 衝突時，會進行如下操作

put 的 key == 已存在的 key 的判斷
put 的 key equals() 已存在的 key 的判斷（注意 HashMap 中並沒有重寫 equals() 方法，這裡的 equals() 方法仍然是 Object 類的方法）
這裡也體現了 == 與 equals() 方法的判斷區別

當上述條件判斷，只要有一個返回 false 時，也就是說需要put 的 key 與已存在的 key 是不相同的，則 HashMap 會使用單連結串列在已有資料的後面（單連結串列中）插入新資料，存取的陣列下標元素作為連結串列的頭部。這種解決 Hash 衝突的方法被稱為拉鍊法

HashMap 存入和取出資料順序不一致

HashMap 遍歷時，取得資料的順序是完全隨機的，這樣會導致按照順序讀取的時候和存入的順序是不一樣的

public class MapTest {
    public static void main(String[] args) {
        Map<String, String> map = new HashMap<>();
        map.put("2020-10-1", "李軍");
        map.put("2020-10-3", "李華");
        map.put("2020-11-1", "李剛");
        map.put("2020-10-9", "李奎");
        for (String key : map.keySet()) {
            System.out.println(key + ":" + map.get(key));
        }
    }
}
結果：
2020-10-3 : 李華
2020-11-1 : 李剛
2020-10-1 : 李軍
2020-10-9 : 李奎