下面代碼分析時基於 jdk1.8 的
HashMap 是什麼？
說先我們看一下HashMap的基本用法：
<code>Map<string> map = new HashMap<>();
\t\tmap.put("hello", "world");
\t\tSystem.out.println(map);/<string>/<code>
我們從put操作開始分析。源碼如下：
點進入 putVal 方法：
如果你直接看上面的代碼，可能會懵掉。
下面我們可以換一個思路來思考作者是怎麼實現HashMap的？？
HashMap是幹什麼的？
我們從上面用法上可以看出，HashMap 是用來存儲 key -value數據的。
HashMap 是用什麼數據結構來存儲的？
我們可以回憶一下 ArrayList 和 LinkedList 的數據結構。
我們從ArrayList 的add 方法看起：
從上面可以看出 ArrayList 使用的是 數組實現。
下面看下 LinkedList add 方法：
Node 節點定義如下：
LinkedList 節點定義
所以 LinkedList 使用的是雙向鏈表。
HashMap 數據結構 = 數組 + 單向鏈表，如下圖
HashMap 的數據結構
我們通過看源碼來驗證上面數據結構：
內部類 Node定義
上圖的是HashMap中的Node 節點定義，是一個單向鏈表。
上圖定義Node數組 來放Node節點。
HashMap其他定義
1.Node 數組的定義長度為
默認Node數組大小
默認為16.
2.負載 因子 DEFAULT_LOAD_FACTOR 什麼意思呢？
負載因子
默認負載因子為0.75 ，當存儲的元素越來越多，Node數組存儲的空間越來越少，該怎麼辦呢？
只有擴容，那麼該怎麼擴容？什麼時候擴容呢？
我們知道HashMap默認大小為16，負載因子為0.75
則當容量 > 12時，進行擴容。
3.當鏈表的長度大於一定長度怎麼辦？
當鏈表的長度很長時，會有什麼缺點呢？
如果查詢到的節點是最後一個節點時，則需要遍歷此節點上的所有鏈表中的元素。所以比較耗時。
JDK8 中，當鏈表長度大於一定長度時，就會轉成 紅黑樹。
當 單向鏈表的長度 > 8 時，就會轉成 紅黑樹
- 當向Map中put一個元素時，如何知道放在數據中的哪個位置呢？
從上面的數據結構可以看出，先把元素存儲在數組中，如果有重疊，則放在鏈表中。
當put一個key，首先通過獲取 key.hashCode把key生成一個hashCode,然後再經過一些列算法生成0-15之間的數值(因為Map的默認值為16）。
那麼怎樣設計一個算法，把key計算成一個0-15 之間的數據呢?
1.先通過Object的hashCode方法，獲取key的hashCode值
2.然後控制這個值在0-15 之間，可以對16進行取模
put源碼分析
首先我們看下put方法的流程：
流程如下：
1、計算key的hash值
調用Object的hashCode，得到hashCode值，然後 第16位 和 高16位 做異或，得到最終hash值。
2、得到Node節點在數組中的位置
計算邏輯為 (n-1) & hash
為什麼是 n - 1 呢？默認值為16, 15 的二進制為 01111
比如 上面得到的hash值為 ：
00000000011111000001110110101
& 01111
--------------------------------------------------------------
0101
如果為n - 1 ,則 hash值的倒數第5位無論為1或者0，和 15的與後，最終的值都在0-15之間。
上面代碼邏輯如下：
1、第一個if: 如果table還沒有初始化，則先進行初始化。
2、第二個if : 如果根據key的hash值，獲取到在數組中的位置，如果為 null,則直接new 一個Node節點，直接放進去。
下面看else代碼：
1、第一個if : 如果原來的位置有節點，且key相同，則直接覆蓋原值即可。
2、else if : 判斷節點是否為 紅黑樹，如果是，則調用紅黑樹添加邏輯。
3、else: 則為鏈表，調用鏈表的處理邏輯
(1) 如果 (e = p.next) == null ，則 直接創建Node節點，如果大於紅黑樹閥值，則轉紅黑樹，然後插入。
(2) if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k)))) break;
如果插入的key 已經存在，則直接跳出，執行下面邏輯。
執行上面的前提是在Map存在此key，則直接替換舊值即可。
最後再次要判斷是否需要擴容？？
resize 方法
上面的最初oldCap中為16，(newCap = oldCap << 1 ） 則擴容為當前容量的2倍。
比如：當前oldCap = 16, 16的二進制為 1000，左移一位為：10000，= 32
容量變的同時，threshold 也要變，32 * 0.75 = 24；
下面的操作就是對節點進行重新分配：
有以下幾種情況：
1、有節點，但是下面為空
2、有節點，下面不為空，但是為紅黑樹
3、有節點，下面不為空，但是為鏈表
e.hash & oldCap 是什麼意思呢？
e.hash & oldCap 的結果只有兩個值，要麼為0，要麼為1。
rehash的時候，是根據 e.hash & oldCap 是否為0，來拆分low 和 high 兩個鏈表的。
然後newTab[j] = low,newTab[j+oldCap]= high;
所以resize 後的位置，要麼在newTab[i],要麼在newTab[i + oldTab]
閱讀更多 碼農的一天 的文章
