HashMap底層原理與擴容機制

一，HashMap的基本資料結構

HashMap繼承了Map抽象類，實作了Map，Cloneable，Serializable接口。

• 1.7 數組 + 連結清單
• 1.8 數組 + （連結清單 | 紅黑樹）

HashMap類中的元素是Node類，翻譯過來就是節點，是定義在HashMap中的一個内部類。（IT楓鬥者怎麼樣）

Node的基本屬性

• hash：key的哈希值
• key：節點的key，類型和定義HashMap時的key相同
• value：節點的value，類型和定義HashMap時的value相同
• next：該節點的下一節點

二， 為什麼要進行樹化？樹化的規則？

樹化意義

hash 表的查找，更新的時間複雜度是 O(1)，而紅黑樹的查找，更新的時間複雜度是 O(log_2⁡n )，TreeNode 占用空間也比普通 Node 的大，如非必要，盡量還是使用連結清單。（IT楓鬥者怎麼樣）

但是紅黑樹用來避免 DoS 攻擊，防止連結清單超長時性能下降O（n），樹化應當是偶然情況，是保底政策。

樹化規則

HashMap裡面定義了一個常量TREEIFY_THRESHOLD = 8，當連結清單長度超過樹化門檻值 8 時，先嘗試調用resize()方法進行擴容來減少連結清單長度，如果數組容量已經 >=64（MIN_TREEIFY_CAPACITY），才會進行樹化，Node節點轉為TreeNode節點（TreeNode也是HashMap中定義的内部類）。

TreeNode除了Node的基本屬性，還儲存了父節點parent， 左孩子left，右孩子right，還有紅黑樹用到的red屬性。（IT楓鬥者怎麼樣）

Note：

hash 值如果足夠随機，則在 hash 表内按泊松分布，在擴容因子（factor） 0.75 的情況下，長度超過 8 的連結清單出現機率是千萬分之6，樹化門檻值選擇 8 就是為了讓樹化幾率足夠小。

如果數組擴容還不到64，連結清單長度未減少，連結清單長度是有可能超過8的。（IT楓鬥者怎麼樣）

三，HashMap的索引是如何計算的？

• 首先，計算對象的 hashCode()，得到原始hash值
• 再進行調用 HashMap 的 hash() 方法進行二次哈希，得到二次hash值
• 最後 & (capacity – 1) 得到索引（使用二次hash值和數組容量 - 1進行位與運算）

四，數組容量為何是 2 的 n 次幂？

• 計算索引時效率更高：如果是 2 的 n 次幂可以使用位與運算代替取模
• 擴容時重新計算索引效率更高：hash（原始hash） & oldCap（原始容量） == 0 的元素留在原來位置 ，否則新位置 = 舊位置 + oldCap（原始容量）

五，為什麼要進行二次 hash？

• 二次 hash() 是為了綜合高位資料，讓哈希分布更為均勻
• 二次 hash 是為了配合 容量是 2 的 n 次幂 這一設計前提，如果 hash 表的容量不是 2 的 n 次幂，則不必二次 hash
• 容量是 2 的 n 次幂 這一設計計算索引效率更好，但 hash 的散列性就不好，需要二次 hash 來作為補償，沒有采用這一設計的典型例子是 Hashtable

六，HashMap的Put流程

1. HashMap 是懶惰建立數組的，首次使用才建立數組
2. 計算索引（桶下标）
3. 如果桶（bucket）下标還沒人占用，建立 Node 占位傳回
4. 如果桶下标已經有人占用
5. a、已經是 TreeNode 走紅黑樹的添加或更新邏輯
6. b、是普通 Node，走連結清單的添加或更新邏輯，如果連結清單長度超過樹化門檻值，走樹化邏輯
7. 傳回前檢查容量是否超過門檻值，一旦超過進行擴容。（IT楓鬥者怎麼樣）

七，HashMap如何進行擴容。

什麼時候觸發擴容？

一般情況下，當元素數量超過門檻值時便會觸發擴容。每次擴容的容量都是之前容量的2倍。

HashMap的容量是有上限的，必須小于1<<30，即1073741824。如果容量超出了這個數，則不再增長，且門檻值會被設定為Integer.MAX_VALUE（

即永遠不會超出門檻值了）。（IT楓鬥者怎麼樣）

這要分HashMap1.7和HashMap1.8情況

HashMap1.7

在JDK1.7的擴容機制相對簡單，有以下特質：

• 空參數的構造函數：以預設容量、預設負載因子、預設門檻值初始化數組。内部數組是空數組。
• 有參構造函數：根據參數确定容量、負載因子、門檻值等。
• 第一次put時會初始化數組，其容量變為不小于指定容量的2的幂數。然後根據負載因子确定門檻值。
• 如果不是第一次擴容，則 新容量=舊容量X2 新門檻值=新容量X負載因子。

HashMap 1.8

HashMap的容量變化通常存在以下幾種情況：

• 空參數的構造函數：執行個體化的HashMap預設内部數組是null，即沒有執行個體化。第一次調用put方法時，則會開始第一次初始化擴容，長度為16。
• 有參構造函數：用于指定容量。會根據指定的正整數找到不小于指定容量的2的幂數，将這個數設定指派給門檻值（threshold）。第一次調用put方法時，會将門檻值指派給容量，然後讓 門檻值=容量X負載因子（是以并不是我們手動指定了容量就一定不會觸發擴容，超過門檻值後一樣會擴容！！）（IT楓鬥者怎麼樣）
• 如果不是第一次擴容，則容量變為原來的2倍，門檻值也變為原來的2倍。

此外還有幾個細節需要注意：

• 首次put時，先會觸發擴容（算是初始化），然後存入資料，然後判斷是否需要擴容；
• 不是首次put，則不再初始化，直接存入資料，然後判斷是否需要擴容；

• 1.7 是大于門檻值（threshold = factor * capacity ）且沒有空位時才擴容，而 1.8 是大于門檻值就擴容
• 1.7是先擴容再插入資料，1.8是先插入資料再擴容
• 擴容是一個特别耗性能的操作，是以當程式員在使用HashMap的時候，估算map的大小，初始化的時候給一個大緻的數值，避免map進行頻繁的擴容
• HashMap的容量達到2的30次方，就不會再進行擴容了。（IT楓鬥者怎麼樣）

八，擴容因子（factor）為何預設是 0.75？

在空間占用與查詢時間之間取得較好的權衡

• 大于0.75，空間節省了，但連結清單就會比較長影響性能
• 小于0.75，沖突減少了，但擴容就會更頻繁，空間占用也更多

九，HashMap的key

1. HashMap 的 key 可以為 null，但 Map 的其他實作則不然
2. 作為 key 的對象，必須實作 hashCode 和 equals，并且 key 的内容不能修改（不可變）
3. key 的 hashCode 應該有良好的散列性。（IT楓鬥者怎麼樣）

十，總結HashMap1.7和1.8有什麼不同？

1. 資料結構

• 1.7 數組 + 連結清單
• 1.8 數組 + （連結清單 | 紅黑樹）

2. 初始化方式

• 1.7中resize()方法負責擴容，inflateTable()負責建立表；
• 1.8中resize()方法在表為空時，建立表；在表不為空時，擴容。（IT楓鬥者怎麼樣）

3. 擴容方式

擴容時機

1.7在插入資料之前擴容，而1.8插入資料成功之後擴容；

1.7 是大于門檻值（threshold = factor * capacity ）且沒有空位時才擴容，而 1.8 是大于門檻值就擴容。（IT楓鬥者怎麼樣）

插入方式

1.7 是頭插法，1.8是尾插法，是以1.7可能會出現并發死鍊現象，兩者在并發情況下都會出現資料錯亂

索引計算

1.8在擴容時計算索引做了優化。（IT楓鬥者怎麼樣）