1、說說HashMap的結構
在JDK7時，采用數組+連結清單結構
在JDK8時，采用數組+連結清單+紅黑樹的結構，在一定條件下，連結清單會轉化為紅黑樹。
2、數組和連結清單的用處是什麼
數組用來随機查找，能夠根據hash值快速定位到Node的位置。
連結清單是用來解決hash沖突的，多個元素定位到同一個Node時，用連結清單将它們順序串起來。
3、為什麼要轉紅黑樹
單連結清單的查詢時間複雜度為O(n)，是以當連結清單元素越來越多時，查詢效率底下，是以在連結清單長度達到一個某一個值的情況下，連結清單會轉化為紅黑樹，查詢複雜度為O(logn)。
但是當連結清單元素少的時候，維護樹的代價必然高于連結清單，是以不能一開始就直接使用紅黑樹。
4、什麼條件下，連結清單會轉化為紅黑樹，紅黑樹又會退化成連結清單
在某條連結清單的長度達到8時，先添加第9個元素，然後判斷數組長度是否達到64。如果達到64，則進行連結清單轉紅黑樹的操作。否則，僅僅隻做擴容。（數組較小時，hash碰撞會比較頻繁，導緻連結清單長度過長。此時就應該先進行擴容，而不是立馬樹化。優先擴容可以避免一些不必要的樹化）
當樹中的元素經過一些删除操作變成6後，将會導緻樹退化成連結清單。中間有個過渡值7，可以防止頻繁的樹化與退化。
5、計算key的hash方法是怎麼樣的
hash方法的源碼如下：
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
} 首先需要了解>>>的含義，即無符号右移，高位補0。例如：
0111 1110 0000 1111 1011 0001 0101 1010
右移16位得到
0000 0000 0000 0000 0111 1110 0000 1111 為什麼要使用這個運算呢，直接傳回key的哈希值不好嗎？
一般來說，任意一個對象的哈希值比較大，随便執行個體化一個對象，得到它的hash值
轉換成2進制後，得到
0011 1001 1010 0000 0101 0100 1010 0101 而HashMap的長度一般就在[1，2^16]左右，取length=16為例，那麼直接使用key的哈希值&(length-1)後，得到
0011 1001 1010 0000 0101 0100 1010 0101
&
0000 0000 0000 0000 0000 0000 0000 1111
---------------------------------------
0000 0000 0000 0000 0000 0000 0000 0101 可見，運算後的結果對哈希值的高位無效，即如果兩個不同對象的哈希值僅僅在高位上不一樣的話，依然會存在哈希沖突的情況。是以，我們現在打算讓運算後的結果對哈希值的高位以及低位都有效。
而對哈希值再次運算後，即使用key.hashCode()^ (h >>> 16)運算後，将哈希值的低16位異或了高16位，讓高位與低位都影響到了對之後位置的選擇上。
那為什麼使用^異或呢，使用|以及&不好嗎？
^能保證兩個數都能影響到最終的結果，而|中隻要一個為1，不管對方是多少，結果都為1，&也是同樣的道理，有0則0。
差別兩個細微對象的不同，就要深挖其細微之處。是以要在最大程度上避免哈希沖突，就越要使用到所有已知的特征，不能認為細微就沒用。
6、為什麼數組長度總是2的次幂
主要有兩點原因：
提升計算效率，更快算出元素的位置
對于機器而言，位運算永遠比取餘運算快得多，在length為2的整數次方的情況下，hash(key)%length能被替換成高效的hash(key)&（length-1）,兩者的結果是相等的。
減少哈希碰撞，使得元素分布均勻
如果數組長度是2的整數次方時，也就是一個偶數，length-1就是一個奇數，奇數的二進制最後一位是1，是以不管hash(key)是多少，hash(key)&(length-1)的二進制最後一位可能是0，也可能是1，取決于hash(key)。即如果hash(key)是奇數的話，則映射到數組上第奇數個位置上。
如果length是一個奇數的話，length-1就是一個偶數，偶數的二進制最後一位是0，則不管hash(key)是奇數還是偶數，該元素都會被映射到數組上第偶數個位置上，奇數位置上沒有任何元素！
是以，數組長度是一個2的整數次方時，哈希碰撞的機率起碼能下降一半，而且所有元素也能均勻地分布在數組上。
具體原因可以移步到我的另外一篇文章為什麼長度總是2的整數次方
7、在什麼條件下進行擴容
首先，預設負載因子為0.75，預設容量為16，是以門檻值=負載因子*容量=12
在JDK8中，插入第11個元素時，沒達到門檻值，不進行擴容。
插入第12個元素時，也不觸發擴容。
插入第13個元素時，插入成功後，再進行擴容，擴容為原來的2倍長度。（尾插法）
而在JDK7中，準備插入第13個元素前，先進行擴容，再進行插入。（頭插法）
8、擴容後元素的遷移機制
JDK7中，擴容後，需要重新計算所有元素的hash值，當然也有可能不計算。因為連結清單元素在遷移過程中，采用頭插法，是以遷移完成後，新舊連結清單會出現倒置現象。
JDK8中，擴容後，不需要重新計算hash值，得益于hash尋址算法的優化。遷移過程中，采用尾插法，新舊連結清單不會倒置。
舉個例子：首先JDK8中的尋址算法為：
其中hash是key.hashCode()高16位與低16位異或的結果，n為數組長度，即使用(n-1)與hash進行按位與得到元素的位置。
擴容前：n=16
則key1與key2由于hash沖突，會形成一個連結清單。
擴容後：n=32
數組長度變為原來的2倍，在計算上的表現，就是多出來一個高位參與按位與。
key1位置不變，而key2的hash值倒數第五位是1，是以按位與計算下來得到10101，而10101=10000+0101=原數組長度+原位置。
是以，不需要進行rehash。擴容後，隻要判斷hash值多出來的1bit是0還是1，0的話，則索引不變。1的話，新索引=原數組長度+舊索引。
看得出來，利用數組長度是2次方以及尋址算法的特點，擴容後不需要重新計算(n-1)&hash，而且讓之前沖突的元素，由高位的不同重新散列到了其他位置上。
9、put過程是怎麼樣的
順着源碼走總是枯燥的，使用一張直覺易懂的圖來講解put過程再合适不過
後續繼續更新
（1）為什麼JDK7采用頭插法，而JDK8改成了尾插法
（2）談談對紅黑樹的認識