作為一個北漂野生的碼農，和尚入坑Java也有4年有餘，雖說頭禿了不少，奈何天資愚鈍，技術功力並未見增長，眼看身邊的師兄弟們都入了達摩院這樣的大廠，和尚不禁喟嘆：大和尚，生當如此！可是每次面試時，面試官不是問技術細節就是問底層原理，不是手撕演算法原始碼就是設計高併發系統，問的和尚面面相覷，不知所云。痛“腚”思痛，和尚決定，好好參禪打坐，認真領悟高深佛法，只望我佛慈悲能渡一渡我這蠢笨的和尚，也渡一渡芸芸眾生。
在Java基礎面試中必問的一個知識點就是HashMap，關於HashMap中可挖掘的點還是挺多的，如果學習的不夠深可能就會被面試官一通吊打。下面和尚我拋磚引玉，把自己對HashMap的一些瞭解分享給大家，如果說的有問題還希望大佬們予以指正，咱們共同進步。
首先我們先來認識一下HashMap，說起HashMap那也是集合類中的名門望族，話說在Collection集合中也是英才輩出，主要有三大家族就是List、Set和Map，其中List是元素有序，Set是元素唯一，Map是K-V鍵值對。而Map中最受人待見的便是HashMap，當然同時也是最受面試官待見的（面試官：你特麼說我不是人麼？和尚：不敢不敢，不過有的面試官面試的時候那是真的狗啊，不信你就看下面這幾個問題）。
一、HashMap的資料結構？為什麼採取這樣的資料結構？
二、jdk1。8對HashMap做了那些最佳化？
三、HashMapput一個元素的流程？
四、介紹一下HashMap的擴容過程
五、HashMap的初始容量是多少？負載因子是多少？以及為什麼？
六、HashMap能不能以物件為key？
七、HashMap為什麼要用紅黑樹？能簡單說一下紅黑樹麼？
八、HashMap是執行緒安全的麼？能說一下1。7多執行緒狀態形成連結串列環的原因麼？
九、能詳細說一下HashMap計算Hash值的過程麼？
看到上述問題，不知道各位看官是否還笑得出來，和尚已經是臉色慘白雙腳發抖了。沒法子，飯要一口一口地吃，問題也要一個一個地解。
先看第一個問題用啥資料結構，以及為什麼要用這種資料結構？回答這個問題首先要根據不同的版本來回答，因為在1。8之前和1。8及之後的版本是不同的。在1。8之前HashMap底層的資料結構是陣列+單鏈表，1。8版本及以後是陣列+單鏈表+紅黑樹。至於為什麼要這樣聽和尚給你娓娓道來：
首先得說一下HashMap的基本原理，說白了就是把鍵值對放到Map中，然後再透過key去獲取value值，那麼我們透過key獲得value的時候肯定是想越快獲取越好，所以，HashMap的底層的資料結構用的是陣列，因為這貨的隨機訪問的時間複雜度是O（1），但問題是陣列是透過下標索引來進行訪問元素的，如何將key與index關聯起來呢，jdk中是這樣實現的：
1、先獲取key的hashCode值，然後將hashCode值與它的高16為進行異或處理，具體操作的過程如下圖所示：
那麼問題來了，為什麼要這樣操作，這其實涉及到接下來的步驟：
2、求陣列的索引值，依據的公式就是index=hash&（n-1） 其中： index為陣列下標索引，n為陣列容量
我們都知道HashMap中陣列的容量是2的冪，至於為什麼是2的冪一會兒再說。在陣列容量是2的冪的基礎上，我們知道n-1的二進位制高位都是0，而低位都是1，這樣一來，hash值的高位必然是0，如果不進行步驟1的話，那就意味著hash的高位都全軍覆沒了，所以步驟1的目的就是為了讓hashCode值的高低位都參與到獲取特徵值的運算中來。
知道為什麼高低位要進行異或計算之後，我們再來說為什麼陣列的容量要是2的冪，假設容量不是2的冪，而是17，就會有如下結果：
我們可以清楚地看到，因為任何數與0的交集都是0，所以如果n-1的低位也出現0，那麼就可能產生相同的index，造成一個數組槽中的元素過多，影響效率，所以陣列容量是2的冪是為了讓hash值能儘可能在陣列上分佈的更加均勻。
看到這兒你或許覺得只用陣列就行了，為什麼要用單鏈表，甚至紅黑樹呢？其實上面存在一個問題就是hash碰撞，就是兩個不同的key計算出相同的hash值，這樣一來就不是簡單一對一的對映關係了，其實解決hash碰撞一般來說有兩種方式，一種是開放地址法，另外一種是單鏈表法，jdk使用的是單鏈表法，說白了就是將相同index中的元素用單鏈表串起來，在獲取到時候獲取到連結串列頭，然後再依次遍歷，這樣就解決了hash衝突。
單鏈表雖然可以解決hash衝突，但是也存在問題，就是如果連結串列過程，那訪問速度會下降，因為單鏈表的隨機訪問時間複雜度時O（n），那怎辦呢？別急，jdk1。8引入了紅黑樹，至於紅黑樹是什麼，和尚就不展開說了，有興趣的可以自己百度，紅黑樹和二叉查詢樹比較類似，查詢的時間複雜度為O（logn），比單鏈表要快。所以HashMap中單鏈表長度大於8的時候就要轉變紅黑樹。
以上就是和尚關於HashMap的資料結構的理解，如果有不對的地方歡迎大家在評論裡指正，下回咱們繼續解第二個問題。
