Java HashMap
說明
此文檔所介紹的HashMap是基于JDK1.8之後的。此文受到網上很多其他Java生态愛好者文章的影響，寫此文的目的是系統的概括下HashMap，并把一些優秀文章的脈絡連接配接起來起到目錄作用。在此感謝優秀文章作者的啟發，由于自身實力有限，若有纰漏之處還請評論指導。
原理(參考[1][3])
HashMap類似于HashTable，本質都是存儲的鍵值對，也就是key、value，key用作存儲初始索引，通過對其進行一系列運算把value映射存儲到底層資料結構中。其存儲的資料結構(JDK 1.8之後)如下：
資料結構(引用[1])
如上圖所示，每個數組是有存儲的是一個連結清單或者紅黑樹(視情況而定)
* 數組
* 連結清單
* 紅黑樹
存儲過程
對key進行hash運算，得到key的hash值。
把key的hash值和hashMap的(length-1)進行&運算，得到index，index即為資料的索引下标，例如0，1，2，3。
根據索引下标，把該Entry存到對應的資料結構中。
計算索引下标，也就是keyHash&(length-1)時，不同的keyHash會産生同樣的索引下标，也就是說一個數組元素可能會存儲多個資料;
是以每個數組元素存儲的是一個連結清單，當連結清單的長度超過TREEIFY_ THRESHOLD：8時，把連結清單改為紅黑樹。
graph LR;
key-->|進行Hash運算|key的hash值;
key的hash值-->|和hashMap的length-1進行&運算|數組下标index;
數組下标index-->|根據index存儲該Entry也就是key, value|該index的數組元素資料結構被更新:連結清單或者紅黑樹插入該Entry;
HashMap的門檻值(參考[1])
DEFAULT INITIAL CAPACITY:
數組的初始容量，也就是預設會數組初始長度為16，長度不能太大或者太小。如果太小，很容易觸發擴容，如果太大，
周遊HashMap會比較慢。值: 1<<4; //16
MAXIMUM CAPACITY:
HashMap最大容量，一.般情況下隻要記憶體夠用，HashMap不會出現問題。值: 1<<30 (整數最大值的一半)
DEFAULT LOAD FACTOR:
預設的負載因子。是以初始情況下，當鍵值對的數量大于16 * 0.75 = 12時，就會觸發擴容。值: 0.75f。
TREEIFY_ THRESHOLD:
如果哈希函數不合理，即使擴容也無法數組元素中連結清單的長度，是以Java 的處理方案是當連結清單太長
時，轉換成紅黑樹。這個值表示當某個數組元素中，連結清單長度大于8時，有可能會轉化成樹。值: 8
UNTREEIFY _THRESHOLD:
在HashMap擴容時，如果發現連結清單長度小于6，則會由樹重新退化為連結清單。值: 6
MIN_ TREEIFY_ CAPACITY:
在轉變成樹之前，還會有一次判斷，隻有鍵值對數量大于64才會發生轉換。這是為了避免在HashMap建立初期，多
個鍵值對恰好被放入了同一個連結清單中而導緻不必要的轉化。值: 64
擴容(參考[2])
* 當元素超過數組長度的75%就會發生擴容，既長度增加一倍。
* 預設的數組長度```DEFAULT _INITIAL_ CAPACITY```=16，預設的負載因子```DEFAULT LOAD FACTOR```=0.75；當鍵值對數量超過16 * 0.75 = 12時，就會觸發擴容導緻數組長度變為16 * 2 = 32。
注意：擴容後，每個鍵值對資料存儲的索引下标需要重新計算。通過公式：keyHash&(newLength-1)。結果會變成：newIndex = oldIndex + 擴容增加的長度。
性能(參考[4])
影響性能的因素
存儲長度(數組長度)：需要為2的整數次幂，此文[5]已經詳細解釋，就不重複造輪子。
擴容頻率->負載因子：選擇一個合适的負載因子，如果負載因子太小會導緻擴容太頻繁，進而導緻性能損失。
實踐案例
文章[4]已經為我們很好地舉了一個提高性能的實踐案例。
”比如說，我們有1000個元素new HashMap(1000), 但是理論上來講new HashMap(1024)更合适，不過上面annegu已經說過，即使是1000，hashmap也自動會将其設定為1024。 但是new HashMap(1024)還不是更合适的，因為0.75*1000 < 1000, 也就是說為了讓0.75 * size > 1000, 我們必須這樣new HashMap(2048)才最合适，既考慮了&的問題，也避免了resize的問題。“
參考文章
[1]https://blog.csdn.net/weixin_45290108/article/details/100056621
[2]https://blog.csdn.net/wohaqiyi/article/details/81448176
[3]https://blog.csdn.net/woshimaxiao1/article/details/83661464
[4]https://blog.csdn.net/cnq2328/article/details/60783708
[5]https://blog.csdn.net/wohaqiyi/article/details/81161735