現在的面試當中凡是那些大廠，基本上都會問到一些關于HashMap的問題了，而且這個集合在開發中也經常會使用到。于是花費了大量的時間去研究分析寫了這篇文章。本文是基于jdk1.8來分析的。篇幅較長，但是都是循序漸進的。耐心讀完相信你會有所收獲。
這篇文章，希望能解決以下問題。
（1）HashMap的底層資料結構是什麼？
（2）HashMap中增删改查操作的底部實作原理是什麼？
（3）HashMap是如何實作擴容的？
（4）HashMap是如何解決hash沖突的？
（7）HashMap為什麼是非線程安全的？
下面我們就帶着這些問題，揭開HashMap的面紗。
HashMap最早是在jdk1.2中開始出現的，一直到jdk1.7一直沒有太大的變化。但是到了jdk1.8突然進行了一個很大的改動。其中一個最顯著的改動就是：
之前jdk1.7的存儲結構是數組+連結清單，到了jdk1.8變成了數組+連結清單+紅黑樹。
另外，HashMap是非線程安全的，也就是說在多個線程同時對HashMap中的某個元素進行增删改操作的時候，是不能保證資料的一緻性的。
下面我們就開始一步一步的分析。
為了進行一個對比分析，我們先給出一個jdk1.7的存儲結構圖
從上圖我們可以看到，在jdk1.7中，首先是把元素放在一個個數組裡面，後來存放的資料元素越來越多，于是就出現了連結清單，對于數組中的每一個元素，都可以有一條連結清單來存儲元素。這就是有名的“拉鍊式”存儲方法。
就這樣用了幾年，後來存儲的元素越來越多，連結清單也越來越長，在查找一個元素時候效率不僅沒有提高（連結清單不适合查找，适合增删），反倒是下降了不少，于是就對這條連結清單進行了一個改進。如何改進呢？就是把這條連結清單變成一個适合查找的樹形結構，沒錯就是紅黑樹。于是HashMap的存儲資料結構就變成了下面的這種。
我們會發現優化的部分就是把連結清單結構變成了紅黑樹。原來jdk1.7的優點是增删效率高，于是在jdk1.8的時候，不僅僅增删效率高，而且查找效率也提升了。
注意：不是說變成了紅黑樹效率就一定提高了，隻有在連結清單的長度不小于8，而且數組的長度不小于64的時候才會将連結清單轉化為紅黑樹，
問題一：什麼是紅黑樹呢？
紅黑樹是一個自平衡的二叉查找樹，也就是說紅黑樹的查找效率是非常的高，查找效率會從連結清單的o(n)降低為o(logn)。如果之前沒有了解過紅黑樹的話，也沒關系，你就記住紅黑樹的查找效率很高就OK了。
問題二：為什麼不一下子把整個連結清單變為紅黑樹呢？
這個問題的意思是這樣的，就是說我們為什麼非要等到連結清單的長度大于等于8的時候，才轉變成紅黑樹？在這裡可以從兩方面來解釋
（1）構造紅黑樹要比構造連結清單複雜，在連結清單的節點不多的時候，從整體的性能看來， 數組+連結清單+紅黑樹的結構可能不一定比數組+連結清單的結構性能高。就好比殺雞焉用牛刀的意思。
（2）HashMap頻繁的擴容，會造成底部紅黑樹不斷的進行拆分和重組，這是非常耗時的。是以，也就是連結清單長度比較長的時候轉變成紅黑樹才會顯著提高效率。
OK，到這裡相信我們對hashMap的底層資料結構有了一個認識。現在帶着上面的結構圖，看一下如何存儲一個元素。
我們在存儲一個元素的時候，大多是使用下面的這種方式。
在這裡HashMap，第一個參數是鍵，第二個參數是值，合起來叫做鍵值對。存儲的時候隻需要調用put方法即可。那底層的實作原理是怎麼樣的呢？這裡還是先給出一個流程圖
上面這個流程，不知道你能否看到，紅色字迹的是三個判斷框，也是轉折點，我們使用文字來梳理一下這個流程：
（1）第一步：調用put方法傳入鍵值對
（2）第二步：使用hash算法計算hash值
（3）第三步：根據hash值确定存放的位置，判斷是否和其他鍵值對位置發生了沖突
（4）第四步：若沒有發生沖突，直接存放在數組中即可
（5）第五步：若發生了沖突，還要判斷此時的資料結構是什麼？
（6）第六步：若此時的資料結構是紅黑樹，那就直接插入紅黑樹中
（7）第七步：若此時的資料結構是連結清單，判斷插入之後是否大于等于8
（8）第八步：插入之後大于8了，就要先調整為紅黑樹，在插入
（9）第九步：插入之後不大于8，那麼就直接插入到連結清單尾部即可。
上面就是插入資料的整個流程，光看流程還不行，我們還需要深入到源碼中去看看底部是如何按照這個流程寫代碼的。
滑鼠聚焦在put方法上面，按一下F3，我們就能進入put的源碼。來看一下：
也就是說，put方法其實調用的是putVal方法。putVal方法有5個參數：
（1）第一個參數hash：調用了hash方法計算hash值
（2）第二個參數key：就是我們傳入的key值，也就是例子中的張三
（3）第三個參數value：就是我們傳入的value值，也就是例子中的20
（4）第四個參數onlyIfAbsent：也就是當鍵相同時，不修改已存在的值
（5）第五個參數evict ：如果為false，那麼數組就處于建立模式中，是以一般為true。
知道了這5個參數的含義，我們就進入到這個putVal方法中。
乍一看，這代碼完全沒有讀下去的欲望，第一次看的時候真實惡心到想吐，但是結合上一開始畫的流程圖再來分析，相信就會好很多。我們把代碼進行拆分（整體分了四大部分）：
（1）Node[] tab中tab表示的就是數組。Nodep中p表示的就是目前插入的節點
（2）第一部分：
這一部分表示的意思是如果數組是空的，那麼就通過resize方法來建立一個新的數組。在這裡resize方法先不說明，在下一小節擴容的時候會提到。
（3）第二部分：
i表示在數組中插入的位置，計算的方式為(n - 1) & hash。在這裡需要判斷插入的位置是否是沖突的，如果不沖突就直接newNode，插入到數組中即可，這就和流程圖中第一個判斷框對應了。
如果插入的hash值沖突了，那就轉到第三部分，處理沖突
（4）第三部分：
我們會看到，處理沖突還真是麻煩，好在我們對這一部分又進行了劃分
a）第三部分第一小節：
在這裡判斷table[i]中的元素是否與插入的key一樣，若相同那就直接使用插入的值p替換掉舊的值e。
b）第三部分第二小節：
判斷插入的資料結構是紅黑樹還是連結清單，在這裡表示如果是紅黑樹，那就直接putTreeVal到紅黑樹中。這就和流程圖裡面的第二個判斷框對應了。
c）第三部分第三小節：
如果資料結構是連結清單，首先要周遊table數組是否存在，如果不存在直接newNode(hash, key, value, null)。如果存在了直接使用新的value替換掉舊的。
注意一點：不存在并且在連結清單末尾插入元素的時候，會判斷binCount >= TREEIFY_THRESHOLD - 1。也就是判斷目前連結清單的長度是否大于門檻值8，如果大于那就會把目前連結清單轉變成紅黑樹，方法是treeifyBin。這也就和流程圖中第三個判斷框對應了。
（5）第四部分：
插入成功之後，還要判斷一下實際存在的鍵值對數量size是否大于門檻值threshold。如果大于那就開始擴容了。
為什麼擴容呢？很明顯就是目前容量不夠，也就是put了太多的元素。為此我們還是先給出一個流程圖，再來進行分析。
這個擴容就比較簡單了，HaspMap擴容就是就是先計算 新的hash表容量和新的容量閥值，然後初始化一個新的hash表，将舊的鍵值對重新映射在新的hash表裡。如果在舊的hash表裡涉及到紅黑樹，那麼在映射到新的hash表中還涉及到紅黑樹的拆分。整個流程也符合我們正常擴容一個容量的過程，我們根據流程圖結合代碼來分析：
這代碼量同樣讓人惡心，不過我們還是分段來分析：
（1）第一部分：
根據代碼也能看明白：首先如果超過了數組的最大容量，那麼就直接将門檻值設定為整數最大值，然後如果沒有超過，那就擴容為原來的2倍，這裡要注意是oldThr << 1，移位操作來實作的。
（2）第二部分：
首先第一個else if表示如果門檻值已經初始化過了，那就直接使用舊的門檻值。然後第二個else表示如果沒有初始化，那就初始化一個新的數組容量和新的門檻值。
（3）第三部分
第三部分同樣也很複雜，就是把舊資料複制到新數組裡面。這裡面需要注意的有下面幾種情況：
A：擴容後，若hash值新增參與運算的位=0，那麼元素在擴容後的位置=原始位置
B：擴容後，若hash值新增參與運算的位=1，那麼元素在擴容後的位置=原始位置+擴容後的舊位置。
hash值新增參與運算的位是什麼呢？我們把hash值轉變成二進制數字，新增參與運算的位就是倒數第五位。
這裡面有一個非常好的設計理念，擴容後長度為原hash表的2倍，于是把hash表分為兩半，分為低位和高位，如果能把原連結清單的鍵值對， 一半放在低位，一半放在高位，而且是通過e.hash & oldCap == 0來判斷，這個判斷有什麼優點呢？
舉個例子：n = 16，二進制為10000，第5位為1，e.hash & oldCap 是否等于0就取決于e.hash第5 位是0還是1，這就相當于有50%的機率放在新hash表低位，50%的機率放在新hash表高位。
OK，到這一步基本上就算是把擴容這一部分講完了，還有一個問題沒有解決，也就是說存儲的原理講明白了，存儲的元素多了如何擴容也明白了，擴容之後出現了位址沖突怎麼辦呢？
解決位址沖突的前提是計算的hash值出現了重複，我們就先來看看HashMap中，是如何計算hash值的。
代碼是超級簡單，hash值其實就是通過hashcode與16異或計算的來的，為什麼要使用異或運算呢？畫一張圖你就明白了：
也就是說，通過異或運算能夠是的計算出來的hash比較均勻，不容易出現沖突。但是偏偏出現了沖突現象，這時候該如何去解決呢？
在資料結構中，我們處理hash沖突常使用的方法有：開發定址法、再哈希法、鍊位址法、建立公共溢出區。而hashMap中處理hash沖突的方法就是鍊位址法。
這種方法的基本思想是将所有哈希位址為i的元素構成一個稱為同義詞鍊的單連結清單，并将單連結清單的頭指針存在哈希表的第i個單元中，因而查找、插入和删除主要在同義詞鍊中進行。鍊位址法适用于經常進行插入和删除的情況。
相信大家都能看明白，出現位址沖突的時候，一個接一個排成一條鍊就OK了。正好與HashMap底層的資料結構相呼應。
上面可能出現的問題，我們都已經說明了，關于他的構造方法卻姗姗來遲。下面我們好好說一下他的構造方法：
他的構造方法一共有四個：
第一個：
第二個：
第三個：
第四個：
這四個構造方法很明顯第四個最麻煩，我們就來分析一下第四個構造方法，其他三個自然而然也就明白了。上面出現了兩個新的名詞：loadFactor和initialCapacity。我們一個一個來分析：
（1）initialCapacity初始容量
官方要求我們要輸入一個2的N次幂的值，比如說2、4、8、16等等這些，但是我們忽然一個不小心，輸入了一個20怎麼辦？沒關系，虛拟機會根據你輸入的值，找一個離20最近的2的N次幂的值，比如說16離他最近，就取16為初始容量。
（2）loadFactor負載因子
負載因子，預設值是0.75。負載因子表示一個散清單的空間的使用程度，有這樣一個公式：initailCapacity*loadFactor=HashMap的容量。
是以負載因子越大則散清單的裝填程度越高，也就是能容納更多的元素，元素多了，連結清單大了，是以此時索引效率就會降低。反之，負載因子越小則連結清單中的資料量就越稀疏，此時會對空間造成爛費，但是此時索引效率高。
為什麼預設值會是0.75呢？我們截取一段jdk文檔：
英語不好的人看的我真是一臉懵逼，不過好在大概意思還能明白。看第三行Poisson_distribution這不就是泊淞分布嘛。而且最關鍵的就是
當桶中元素到達8個的時候，機率已經變得非常小，也就是說用0.75作為加載因子，每個碰撞位置的連結清單長度超過８個是幾乎不可能的。當桶中元素到達8個的時候，機率已經變得非常小，也就是說用0.75作為加載因子，每個碰撞位置的連結清單長度超過８個是幾乎不可能的。
想要解決這個問題，答案很簡單，因為源碼裡面方法全部都是非線程安全的呀，你根本找不到synchronized這樣的關鍵字。保證不了線程安全。于是出現了ConcurrentHashMap。
寫到這裡終于算是把一些核心的内容寫完了。當然HashMap裡面涉及到的面試題這些很多，不能能面面俱到。如有遺漏問題，會在今後補充。歡迎批評指正。