HashMap的put、get方法詳解（附源碼）

put方法

HashMap 只提供了 put 用于添加元素，putVal 方法只是給 put 方法調用的一個方法，并沒有提供給用戶使用。
對 putVal 方法添加元素的分析如下：如果定位到的數組位置沒有元素就直接插入。如果定位到的數組位置有元素就和要插入的 key 比較，如果 key 相同就直接覆蓋，如果 key 不相同，就判斷 p 是否是一個樹節點，如果是就調用e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value)將元素添加進入。如果不是就遍歷鏈表插入(插入的是鏈表尾部)。
在這里插入圖片描述
HashMap HashMap的put()方法用于向HashMap中添加鍵值對，當調用HashMap的put()方法時，會按照以下詳細流程執行（JDK8 1.8版本）：

第一步：根據要添加的鍵的哈希碼計算在數組中的位置（索引）。
第二步：檢查該位置是否為空（即沒有鍵值對存在）

如果為空，則直接在該位置創建一個新的Entry對象來存儲鍵值對。將要添加的鍵值對作為該Entry的鍵和值，并保存在數組的對應位置。將HashMap的修改次數（modCount）加1，以便在進行迭代時發現并發修改。

第三步：如果該位置已經存在其他鍵值對，檢查該位置的第一個鍵值對的哈希碼和鍵是否與要添加的鍵值對相同？

如果相同，則表示找到了相同的鍵，直接將新的值替換舊的值，完成更新操作。

第四步：如果第一個鍵值對的哈希碼和鍵不相同，則需要遍歷鏈表或紅黑樹來查找是否有相同的鍵：

如果鍵值對集合是鏈表結構，從鏈表的頭部開始逐個比較鍵的哈希碼和equals()方法，直到找到相同的鍵或達到鏈表末尾。

如果找到了相同的鍵，則使用新的值取代舊的值，即更新鍵對應的值。
如果沒有找到相同的鍵，則將新的鍵值對添加到鏈表的頭部。

如果鍵值對集合是紅黑樹結構，在紅黑樹中使用哈希碼和equals()方法進行查找。根據鍵的哈希碼，定位到紅黑樹中的某個節點，然后逐個比較鍵，直到找到相同的鍵或達到紅黑樹末尾。

如果找到了相同的鍵，則使用新的值取代舊的值，即更新鍵對應的值。
如果沒有找到相同的鍵，則將新的鍵值對添加到紅黑樹中。

第五步：檢查鏈表長度是否達到閾值（默認為8）：

如果鏈表長度超過閾值，且HashMap的數組長度大于等于64，則會將鏈表轉換為紅黑樹，以提高查詢效率。

第六步：檢查負載因子是否超過閾值（默認為0.75）：

如果鍵值對的數量（size）與數組的長度的比值大于閾值，則需要進行擴容操作。

第七步：擴容操作：

創建一個新的兩倍大小的數組。
將舊數組中的鍵值對重新計算哈希碼并分配到新數組中的位置。
更新HashMap的數組引用和閾值參數。

第八步：完成添加操作。
此外，HashMap是非線程安全的，如果在多線程環境下使用，需要采取額外的同步措施或使用線程安全的ConcurrentHashMap。

源碼如下：

public V put(K key, V value) {return putVal(hash(key), key, value, false, true);
}final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {Node<K,V>[] tab; Node<K,V> p; int n, i;// table未初始化或者長度為0，進行擴容if ((tab = table) == null || (n = tab.length) == 0)n = (tab = resize()).length;// (n - 1) & hash 確定元素存放在哪個桶中，桶為空，新生成結點放入桶中(此時，這個結點是放在數組中)if ((p = tab[i = (n - 1) & hash]) == null)tab[i] = newNode(hash, key, value, null);// 桶中已經存在元素（處理hash沖突）else {Node<K,V> e; K k;//快速判斷第一個節點table[i]的key是否與插入的key一樣，若相同就直接使用插入的值p替換掉舊的值e。if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))e = p;// 判斷插入的是否是紅黑樹節點else if (p instanceof TreeNode)// 放入樹中e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);// 不是紅黑樹節點則說明為鏈表結點else {// 在鏈表最末插入結點for (int binCount = 0; ; ++binCount) {// 到達鏈表的尾部if ((e = p.next) == null) {// 在尾部插入新結點p.next = newNode(hash, key, value, null);// 結點數量達到閾值(默認為 8 )，執行 treeifyBin 方法// 這個方法會根據 HashMap 數組來決定是否轉換為紅黑樹。// 只有當數組長度大于或者等于 64 的情況下，才會執行轉換紅黑樹操作，以減少搜索時間。否則，就是只是對數組擴容。if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1sttreeifyBin(tab, hash);// 跳出循環break;}// 判斷鏈表中結點的key值與插入的元素的key值是否相等if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))// 相等，跳出循環break;// 用于遍歷桶中的鏈表，與前面的e = p.next組合，可以遍歷鏈表p = e;}}// 表示在桶中找到key值、hash值與插入元素相等的結點if (e != null) {// 記錄e的valueV oldValue = e.value;// onlyIfAbsent為false或者舊值為nullif (!onlyIfAbsent || oldValue == null)//用新值替換舊值e.value = value;// 訪問后回調afterNodeAccess(e);// 返回舊值return oldValue;}}// 結構性修改++modCount;// 實際大小大于閾值則擴容if (++size > threshold)resize();// 插入后回調afterNodeInsertion(evict);return null;
}

get方法

HashMap的get(Object key)方法用于根據指定的鍵（key）獲取其對應的值（value）。當調用此方法時，會執行與put()方法類似的定位邏輯來查找節點，但過程相對簡單，因為它不涉及修改操作。以下是詳細的執行流程（JDK 8 1.8版本）：

第一步：計算哈希值，定位數組索引

首先，get(key)方法會調用內部的getNode(hash(key), key)方法。
在getNode方法中，它會根據傳入的key計算出其哈希碼（hash value）。
然后，通過位運算 (n - 1) & hash（其中n是HashMap內部數組的長度）來精確計算出該key應該位于數組的哪個索引位置（即哪個桶）。

第二步：檢查桶內情況，優先檢查第一個節點。

定位到數組索引后，系統會檢查該位置是否存在節點。
如果該位置為null（即桶為空），則意味著Map中不存在這個key，getNode方法直接返回null。
如果該位置不為null，系統會進行一個快速判斷：檢查該桶中第一個節點的哈希值和key本身是否與要查找的key完全匹配（先比較hash，再用==或equals()比較key）。
如果第一個節點就匹配成功，則直接返回這個節點，查找結束。這是對無哈希沖突情況的優化。

第三步：處理哈希沖突，遍歷鏈表或紅黑樹。

如果第一個節點不匹配，并且該節點后面還存在其他節點（即first.next != null），則說明發生了哈希沖突，需要進一步在鏈表或紅黑樹中查找。
判斷數據結構：
- 如果為紅黑樹：通過 first instanceof TreeNode 判斷。如果是，則調用紅黑樹專屬的getTreeNode()方法，在樹中進行高效查找。
- 如果為鏈表：則從第二個節點開始，進入一個do-while循環，逐個向后遍歷鏈表中的每個節點。
遍歷查找：
- 在遍歷鏈表或查找紅黑樹的過程中，對每個節點都進行哈希值和key的比較。
- 如果在鏈表或紅黑樹中找到了完全匹配的節點，則立即返回該節點。
- 如果遍歷完整個鏈表或紅黑樹仍未找到匹配項，getNode方法將返回null。

第四步：返回最終結果。

get方法會接收getNode方法的返回值（一個Node對象或null）。
如果返回的節點對象不為null，get方法會提取并返回該節點的value值。
如果返回的節點為null，則get方法最終也返回null，表示在HashMap中未找到指定的key。

源碼如下：

// get方法是getNode方法的封裝，它處理了getNode返回null的情況
public V get(Object key) {Node<K,V> e;// 調用getNode獲取節點，如果節點為null，則返回null，否則返回節點的valuereturn (e = getNode(hash(key), key)) == null ? null : e.value;
}/*** 實現Map.get()和相關方法*/
final Node<K,V> getNode(int hash, Object key) {Node<K,V>[] tab; Node<K,V> first, e; int n; K k;// 1. 檢查table是否初始化，長度是否大于0，以及根據hash計算出的位置上是否有節點if ((tab = table) != null && (n = tab.length) > 0 &&(first = tab[(n - 1) & hash]) != null) {// 2. 檢查第一個節點，如果匹配，直接返回if (first.hash == hash && // always check first node((k = first.key) == key || (key != null && key.equals(k))))return first;// 3. 如果第一個節點不匹配，且存在后續節點if ((e = first.next) != null) {// 3.1 如果是紅黑樹，調用getTreeNode在樹中查找if (first instanceof TreeNode)return ((TreeNode<K,V>)first).getTreeNode(hash, key);// 3.2 如果是鏈表，遍歷鏈表查找do {if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))return e;} while ((e = e.next) != null);}}// 4. 如果table為空，或桶為空，或遍歷完沒找到，則返回nullreturn null;
}