HashMap 是 Java 中最常用的數據結構之一，用于存儲鍵值對。其 put() 方法是向哈希表中插入或更新鍵值對的核心操作。本文將詳細解析 put() 方法的執行過程，涵蓋哈希值計算、桶定位、沖突處理和擴容等步驟。

---

一、put() 方法的執行過程

put() 方法通過一系列步驟實現鍵值對的高效存儲和更新。以下是詳細的執行流程：

1. 計算鍵的哈希值

• 步驟：HashMap 首先調用鍵的 hashCode() 方法獲取其哈希碼。
• 擾動處理：為了減少哈希沖突，HashMap 對哈希碼進行擾動處理，具體通過 (h = key.hashCode()) ^ (h >>> 16)，將高 16 位與低 16 位進行異或操作，增加哈希值的隨機性。
• 特殊情況：如果鍵為 null，哈希值固定為 0（HashMap 允許一個 null 鍵）。

2. 確定桶位置

• 計算索引：使用哈希值通過公式 index = hash & (table.length - 1) 計算鍵值對在數組（桶）中的索引位置。
• table 初始化：table 是 HashMap 內部用于存儲節點的數組。如果 table 未初始化（即 table == null 或 table.length == 0），會調用 resize() 方法初始化數組。

3. 處理桶中的情況

根據目標桶（table[index]）的狀態，put() 方法會執行不同的邏輯：

情況 1：桶為空

• 如果桶中沒有節點，直接創建一個新的 Node（包含鍵、值、哈希值等信息）并放入該桶。

情況 2：桶中已有節點

• 3.2.1 檢查第一個節點

  • 如果桶中第一個節點的鍵與插入的鍵相同（通過哈希值比較和 equals() 方法確認），直接更新該節點的值。

• 3.2.2 處理紅黑樹

  • 如果桶中節點數量較多（超過 TREEIFY_THRESHOLD，默認為 8），且桶已轉為紅黑樹結構，調用紅黑樹的插入方法（putTreeVal）處理插入或更新。

• 3.2.3 處理鏈表

  • 如果桶中是鏈表結構，遍歷鏈表：
    • 如果找到鍵相同的節點，更新其值。
    • 如果沒有找到相同鍵，將新節點添加到鏈表末尾。
  • 插入后，如果鏈表長度大于等于8且數組長度達到64時，調用 treeifyBin() 將鏈表轉換為紅黑樹。

情況 3：桶中鍵為 null

• 如果插入的鍵為 null，存儲到索引為 0 的桶中（HashMap 只允許一個 null 鍵）。

4. 更新大小和檢查擴容

• 更新 size：插入新鍵值對后，HashMap 的 size（鍵值對數量）加 1。
• 檢查擴容：如果 size 超過閾值（threshold = table.length * loadFactor，默認負載因子為 0.75），觸發 resize() 方法進行擴容。
• 擴容：將數組的容量擴大為原來的2倍。

5. 返回舊值

• 如果插入的鍵已存在，put() 方法返回該鍵對應的舊值。
• 如果是新插入的鍵值對，返回 null。

---

二、核心代碼分析

以下是 put() 方法的核心邏輯：

public V put(K key, V value) {return putVal(hash(key), key, value, false, true);
}// 計算哈希值
static final int hash(Object key) {int h;return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}// putVal 核心實現
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 未初始化，調用 resize()if ((tab = table) == null || (n = tab.length) == 0)n = (tab = resize()).length;// 計算索引，檢查桶是否為空if ((p = tab[i = (n - 1) & hash]) == null)tab[i] = newNode(hash, key, value, null); // 直接插入新節點else {Node<K,V> e; K k;// 檢查第一個節點是否匹配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); // 插入到鏈表末尾// 檢查是否需要轉為紅黑樹if (binCount >= TREEIFY_THRESHOLD - 1)treeifyBin(tab, hash);break;}// 找到相同鍵if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))break;p = e;}}// 如果找到已有鍵，更新值if (e != null) {V oldValue = e.value;if (!onlyIfAbsent || oldValue == null)e.value = value;afterNodeAccess(e);return oldValue;}}// 增加 size，檢查是否需要擴容if (++size > threshold)resize();afterNodeInsertion(evict);return null;
}