一：HashMap的整體實現
HashMap是由Hash表來實現的，數組+鏈表（1.8加入紅黑樹）的方式實現的，通過key的hash值與數組長度取餘來獲取應插入數組的下標，如果產生Hash衝突，在原下標位置轉為鏈表，當鏈表長度到達8並且數組長度大於等於64則轉為紅黑樹。
通過以上描述我們提以下問題：
1、什麼是Hash表
我們知道數組的特點是：尋址容易，插入和刪除困難。
鏈表的特點是：尋址困難，插入和刪除容易。
那麼我們能不能綜合兩者的特性，做出一種尋址容易，插入刪除也容易的數據結構？答案是肯定的，這就是我們要提起的哈希表，哈希表有多種不同的實現方法，HashMap中最常用的一種方法——拉鍊法，我們可以理解為“鏈表的數組”，如圖：
2、JDK1.8為什麼引入紅黑樹？
Hash算法設計的再合理，也免不了會出現拉鍊過長的情況，一旦出現拉鍊過長，則會嚴重影響HashMap的性能。於是，在JDK1.8版本中，對數據結構做了進一步的優化，引入了紅黑樹。而當鏈表長度太長（默認超過8）時，鏈表就轉換為紅黑樹，利用紅黑樹快速增刪改查的特點提高HashMap的性能，其中會用到紅黑樹的插入、刪除、查找等算法。
3、用什麼方式解決Hash衝突？
解決Hash衝突方法有：開放地址法（線性探測再散列，二次探測再散列，偽隨機探測再散列）、再哈希法、鏈地址法、建立公共溢出區。
HashMap使用鏈地址法來解決Hash衝突。
二：字段信息
table是Hash表的數組結構，初始默認大小為16，裡面存儲Node信息
Node是HashMap的一個內部類，實現了Map.Entry接口，本質是就是一個映射(鍵值對)。
Load factor為負載因子(默認值是0.75)，threshold是HashMap所能容納的最大數據量的Node(鍵值對)個數。threshold = length * Load factor。也就是說，在數組定義好長度之後，負載因子越大，所能容納的鍵值對個數越多。
threshold就是在此Load factor和length(數組長度)對應下允許的最大元素數目，超過這個數目就重新resize(擴容)，擴容後的HashMap容量是之前容量的兩倍。默認的負載因子0.75是對空間和時間效率的一個平衡選擇，建議不要修改，除非在時間和空間比較特殊的情況下，如果內存空間很多而又對時間效率要求很高，可以降低負載因子Load factor的值；相反，如果內存空間緊張而對時間效率要求不高，可以增加負載因子loadFactor的值，這個值可以大於1。
size是HashMap中實際存在的鍵值對數量，而modCount字段主要用來記錄HashMap內部結構發生變化的次數，主要用於迭代的快速失敗。強調一點，內部結構發生變化指的是結構發生變化，例如put新鍵值對，但是某個key對應的value值被覆蓋不屬於結構變化。
三：確定哈希桶數組索引位置
不管增加、刪除、查找鍵值對，定位到哈希桶數組的位置都是很關鍵的第一步。前面說過HashMap的數據結構是數組和鏈表的結合，所以我們當然希望這個HashMap裡面的元素位置儘量分佈均勻些，儘量使得每個位置上的元素數量只有一個，那麼當我們用hash算法求得這個位置的時候，馬上就可以知道對應位置的元素就是我們要的，不用遍歷鏈表，大大優化了查詢的效率。HashMap定位數組索引位置，直接決定了hash方法的離散性能。先看看源碼的實現
這裡的Hash算法本質上就是三步：取key的hashCode值、高位運算、取模運算。
那麼問題來了
1、為什麼要異或呢？為什麼要移位呢？而且移位16？
2、為什麼使用 & 與運算代替模運算？
3、HashMap怎麼保證數組的容量為2的冪次方的？
我們來看源碼：
四：put方法
1. 判斷鍵值對數組table[i]是否為空或為null，否則執行resize()進行擴容。
2. 根據鍵值key計算hash值得到插入的數組索引i，如果table[i]==null，直接新建節點添加，轉向步驟6，如果table[i]不為空，轉向步驟3。
3. 判斷table[i]的首個元素是否和key一樣，如果相同直接覆蓋value，否則轉向步驟4，這裡的相同指的是hashCode以及equals。
4. 判斷table[i] 是否為treeNode，即table[i] 是否是紅黑樹，如果是紅黑樹，則直接在樹中插入鍵值對，否則轉向步驟5。
5. 遍歷table[i]，判斷鏈表長度是否大於8，大於8的話把鏈表轉換為紅黑樹，在紅黑樹中執行插入操作，否則進行鏈表的插入操作；遍歷過程中若發現key已經存在直接覆蓋value即可。
6. 插入成功後，判斷實際存在的鍵值對數量size是否超多了最大容量threshold，如果超過，進行擴容。
五：擴容機制
擴容(resize)就是重新計算容量，向HashMap對象裡不停的添加元素，而HashMap對象內部的數組無法裝載更多的元素時，對象就需要擴大數組的長度，以便能裝入更多的元素。當然Java裡的數組是無法自動擴容的，方法是使用一個新的數組代替已有的容量小的數組，就像我們用一個小桶裝水，如果想裝更多的水，就得換大水桶。
我們分析下resize的源碼，鑑於JDK1.8融入了紅黑樹，較複雜，為了便於理解我們仍然使用JDK1.7的代碼，好理解一些
這裡就是使用一個容量更大的數組來代替已有的容量小的數組，transfer()方法將原有Entry數組的元素拷貝到新的Entry數組裡。
newTable[i]的引用賦給了e.next，也就是使用了單鏈表的頭插入方式，同一位置上新元素總會被放在鏈表的頭部位置；這樣先放在一個索引上的元素終會被放到Entry鏈的尾部(如果發生了hash衝突的話），這一點和Jdk1.8有區別，下文詳解。在舊數組中同一條Entry鏈上的元素，通過重新計算索引位置後，有可能被放到了新數組的不同位置上。
下面舉個例子說明下擴容過程。假設了我們的hash算法就是簡單的用key mod 一下表的大小（也就是數組的長度）。其中的哈希桶數組table的size=2， 所以key = 3、7、5，put順序依次為 5、7、3。在mod 2以後都衝突在table[1]這裡了。這裡假設負載因子 loadFactor=1，即當鍵值對的實際大小size 大於 table的實際大小時進行擴容。接下來的三個步驟是哈希桶數組 resize成4，然後所有的Node重新rehash的過程。
下面我們講解下JDK1.8做了哪些優化。經過觀測可以發現，我們使用的是2次冪的擴展(指長度擴為原來2倍)，所以，元素的位置要麼是在原位置，要麼是在原位置再移動2次冪的位置。看下圖可以明白這句話的意思，n為table的長度，圖（a）表示擴容前的key1和key2兩種key確定索引位置的示例，圖（b）表示擴容後key1和key2兩種key確定索引位置的示例，其中hash1是key1對應的哈希與高位運算結果。
元素在重新計算hash之後，因為n變為2倍，那麼n-1的mask範圍在高位多1bit(紅色)，因此新的index就會發生這樣的變化：
因此，我們在擴充HashMap的時候，不需要像JDK1.7的實現那樣重新計算hash，只需要看看原來的hash值新增的那個bit是1還是0就好了，是0的話索引沒變，是1的話索引變成“原索引+oldCap”，可以看看下圖為16擴充為32的resize示意圖：
這個設計確實非常的巧妙，既省去了重新計算hash值的時間，而且同時，由於新增的1bit是0還是1可以認為是隨機的，因此resize的過程，均勻的把之前的衝突的節點分散到新的bucket了。這一塊就是JDK1.8新增的優化點。有一點注意區別，JDK1.7中rehash的時候，舊鏈表遷移新鏈表的時候，如果在新表的數組索引位置相同，則鏈表元素會倒置，但是從上圖可以看出，JDK1.8不會倒置。
JDK1.8的resize源碼，如下:
