HashMap底層實現原理
時間：2024-02-21 來源：華清遠見
hello，大家好。今天跟大家說說HashMap的底層原理以及它的擴容機制。
1、HashMap的底層實現原理
1.1HashMap的基本數據結構
HashMap繼承了AbstractMap抽象類，實現了Map、Cloneable、Serializable接口。
JDK1.7及以前，HashMap是由數組 + 鏈表構成的
JDK1.8 以后，HashMap是由數組 + (鏈表 | 紅黑樹)構成的
HashMap類中的元素是Node類，翻譯過來就是節點，是定義在HashMap中的一個內部類。
Node的基本屬性如下：
Hash--key的哈希值
Key--節點的key，類型和定義HashMap時的key相同
Value--節點的value，類型和定義HashMap時的value相同
Next--該節點的下一節點
HashMap使用拉鏈法管理其中的每個節點：定義了一個數組，這個數組記錄了每個鏈表的第一個節點，可以通過不斷的調用Node.next.next.next...，遍歷整個鏈表。如果HashMap初始化的時候沒有指定容量，那么初始化 table的時候會使用默認DEFAULT_INITIAL_ CAPACITY參數，也就是16，作為 table初始化時的長度。如果HashMap初始化的時候指定了容量，HashMap 會把這個容量修改為2的倍數，然后創建對應長度的table。
1.2為什么要進行樹化？樹化的規則？
樹化意義：
hash表的查找，更新的時間復雜度是 O(1)，而紅黑樹的查找，更新的時間復雜度是 O(log2n)，TreeNode 占用空間也比普通 Node 的大，如非必要，盡量還是使用鏈表。
但是紅黑樹用來避免 DoS 攻擊，防止鏈表超長時性能下降O(n)，樹化應當是偶然情況，是保底策略。
樹化規則：
HashMap里面定義了一個常量TREEIFY_THRESHOLD = 8，當鏈表長度超過樹化閾值 8 時，先嘗試調用resize()方法進行擴容來減少鏈表長度，如果數組容量已經 >=64(MIN_TREEIFY_CAPACITY)，才會進行樹化，Node節點轉為TreeNode節點(TreeNode也是HashMap中定義的內部類)。TreeNode除了Node的基本屬性，還保存了父節點parent，左孩子left，右孩子right，還有紅黑樹用到的red屬性。
Note：
hash值如果足夠隨機，則在 hash表內按泊松分布，在擴容因子(factor)0.75 的情況下，長度超過 8 的鏈表出現概率是千萬分之6，樹化閾值選擇 8 就是為了讓樹化幾率足夠小。如果數組擴容還不到64，鏈表長度未減少，鏈表長度是有可能超過8的。
1.3HashMap的一些原理問題
HashMap的索引是如何計算的：
首先，計算對象的 hashCode()，得到原始hash值
再進行調用 HashMap 的 hash() 方法進行二次哈希，得到二次hash值
最后 & (capacity – 1) 得到索引(使用二次hash值和數組容量 - 1進行位與運算)
為什么要進行二次 hash：
二次 hash是為了綜合高位數據，讓哈希分布更為均勻
二次 hash是為了配合容量是2的n次冪這一設計前提，如果 hash 表的容量不是2的n次冪，則不必二次 hash
容量是2的n次冪這一設計，計算索引效率更好，但 hash 的散列性就不好，需要二次 hash 來作為補償，沒有采用這一設計的典型例子是 Hashtable
數組容量為何是 2 的 n 次冪：
計算索引時效率更高：如果是 2 的 n 次冪可以使用位與運算代替取模
擴容時重新計算索引效率更高：hash(原始hash) & oldCap(原始容量)== 0 的元素留在原來位置 ，否則新位置 = 舊位置 + oldCap(原始容量)
1.4HashMap的Put流程
HashMap 是懶惰創建數組的，首次使用才創建數組
計算索引(桶下標)
如果桶(bucket)下標還沒人占用，創建 Node 占位返回
如果桶下標已經有人占用
a、已經是 TreeNode 走紅黑樹的添加或更新邏輯
b、是普通 Node，走鏈表的添加或更新邏輯，如果鏈表長度超過樹化閾值，走樹化邏輯
返回前檢查容量是否超過閾值，一旦超過進行擴容
2、HashMap的擴容原理
2.1HashMap擴容的概念
hashMap擴容就是重新計算容量，向hashMap不停的添加元素，當hashMap無法裝載新的元素，對象將需要擴大數組容量，以便裝入更多的元素。
2.2什么時候觸發擴容？
HashMap默認的負載因子(loadFactor)大小為0.75
HashMap的擴容閾值threshold = capacity* loadFactor
一般情況下，當元素數量超過閾值時便會觸發擴容。每次擴容的容量都是之前容量的2倍。
HashMap的容量是有上限的，必須小于1<<30，即1073741824。如果容量超出了這個數，則不再增長，且閾值會被設置為Integer.MAX_VALUE(即永遠不會超出閾值了)。
2.3HashMap擴容的實現
HashMap的擴展原理是HashMap用一個新的數組替換原來的數組。重新計算原數組的所有數據并插入這個新數組，然后指向新數組。如果陣列在容量擴展前已達到最大值，閾值將直接設置為最大整數返回。
在JDK1.7的擴容機制相對簡單，有以下特質：
空參數的構造函數：以默認容量、默認負載因子、默認閾值初始化數組。內部數組是空數組。
有參構造函數：根據參數確定容量、負載因子、閾值等。
第一次put時會初始化數組，其容量變為不小于指定容量的2的冪數。然后根據負載因子確定閾值。
如果不是第一次擴容，則 新容量=舊容量*2 新閾值=新容量*負載因子
JDK1.8HashMap的容量變化通常存在以下幾種情況：
空參數的構造函數：實例化的HashMap默認內部數組是null，即沒有實例化。第一次調用put方法時，則會開始第一次初始化擴容，長度為16。
有參構造函數：用于指定容量。會根據指定的正整數找到不小于指定容量的2的冪數，將這個數設置賦值給閾值(threshold)。第一次調用put方法時，會將閾值賦值給容量，然后讓 閾值=容量X負載因子(因此并不是我們手動指定了容量就一定不會觸發擴容，超過閾值后一樣會擴容！！)
如果不是第一次擴容，則容量變為原來的2倍，閾值也變為原來的2倍。
