關于 HashMap

HashMap 是什么？

HashMap 是基于哈希表的數據結構，用于存儲鍵值對（key-value）

特點：鍵唯一，值可以重復，允許一個 null 鍵，多個 null 值

核心點：將鍵的哈希值映射到數組索引位置，利用數組+鏈表（Java1.8 之后為數組+鏈表+紅黑樹）來處理哈希沖突

哈希沖突是什么？怎么解決？

哈希沖突：當兩個不同的數經過哈希函數計算后得到了同一個結果，即他們會被映射到哈希表的同一個位置時，即稱為發生了哈希沖突。

常用的解決方法

拉鏈法

使用鏈表或者其他數據結構來存儲哈希沖突的鍵值對，將它們鏈接在同一個哈希桶中。

把所有同義詞存儲在一個鏈表中

假設現在有一個哈希函數為H(key)=key%13

當發生哈希沖突的時候，會將新的鍵值對添加到鏈表中，當需要查找該值的時候，會先通過哈希函數找到桶，然后遍歷鏈表找到該值

開放定址法

在哈希表中尋找另一個位置（哈希桶）存放哈希鍵值對，而不是存放在鏈表中

常見的策略有：線性探測、平方探測、雙重三列、偽隨機序列

公式：
$$
H_i=(H(key)+d_i) % m
$$
參數介紹：

• H_i：發生第 i 次沖突的散列地址
• H(key)：初始散列地址
• d_i：偏移量
• m：散列表的長度

線性探測：

• 逐一檢查下一個哈希桶（H(key)++），直到找到一個空桶為止
• 在線性探測d_i 相當于一個等差數列，d_i= 0,1,2,3,4….,m-1

平方探測：

利用平方探測公式逐漸增加偏移量檢查下一個哈希桶，直到找到一個空桶為止，公式為：
$$
d_i=i^2,-(i2)
$$
例如
$$
d_i= 0^2, 1^2, -1^2, 2^2, -2^2,….,k2, -k^2; k <= m/2
$$

雙散列表：

公式：
$$
H_i=(hash1(key) + i*hash2(key)) % m
$$

$$
hash1(key)=key% m
$$

$$
hash2(Key)=PRIME - (key%PRIME)
$$

• 當第一個哈希函數發生沖突的時候，就會使用第二個哈希函數來尋找空的哈希桶，如此反復，直到找到空的哈希桶

• 偏移量
  $$
  d_i=i*hash2(key)
  $$

哈希擴容

HashMap中的擴容是基于負載因子（load factor）決定的，散列表的平均查找長度依賴于負載因子a ，而不是n或者m

$$
負載因子 a = \frac{表中記錄數n}{散列長度m}
$$
負載因子a默認是0.75，也就是當表中記錄n（已存儲元素數量）超過散列長度的 75%，散列表就會發生擴容

當發生擴容的時候，HashMap的容量會擴大為當前的 2 倍。擴容時，HashMap需要將所有元素重新分配到新的哈希桶，這個過程為rehashing

HashMap 的紅黑樹優化

首先看hashmap中的一個常量值：

TREEIFY_THRESHOLD

使用樹而不是列表來表示一個桶的桶計數閾值。當向一個至少包含此數量節點的桶中添加元素時，這些桶會被轉換為樹。該值必須大于2，且至少應為8，以便與樹刪除操作中的假設相一致，即收縮后應重新轉換為普通桶。

UNTREEIFY_THRESHOLD

在調整大小操作期間將（拆分）桶標記為非樹狀化的桶計數閾值。該值應小于TREEIFY_THRESHOLD，且最多為6，以便與移除操作下的收縮檢測相協調。

MIN_TREEIFY_CAPACITY

可以實施樹化操作的最低表容量。否則，如果桶中節點過多，則會對表進行重新調整大小。應至少設置為4 * TREEIFY_THRESHOLD，以避免在重新調整大小和樹化閾值之間產生沖突。

源碼：

static final int TREEIFY_THRESHOLD = 8;

static final int UNTREEIFY_THRESHOLD = 6;

static final int MIN_TREEIFY_CAPACITY = 64;

轉換為紅黑樹的時機

當HashMap的鏈表長度 >= 8 且數組的長度>=64的時候會樹化，即鏈表轉換成紅黑樹

在源碼的putVal(...)函數中的樹化判定條件

TREEIFY_THRESHOLD的默認閾值，因為負載因子是0.75，而 8 * 0.75 = 6，也就是當表中記錄數超過6并且散列表的長度為 8 的時候就會發生樹化

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();
    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);
        if ((tab[index] = hd) != null)
            hd.treeify(tab);
    }
}

轉換為鏈表的時機

當哈希表的長度為 6 的時候，就會退化為鏈表

在源碼中的split(...)函數中的紅黑樹退化為鏈表的判定條件

untreeify()為轉鏈表化函數

end…

參考文章：

說說Java中HashMap的原理？

一篇博客讓你認識哈希沖突和解決方法