# 循序漸進分析源碼之 HashMap put 方法的示例分析
## 一、前言
HashMap 作為 Java 集合框架中最常用的數據結構之一，其內部實現原理值得深入探究。本文將以 Java 8 的 HashMap 實現為例，通過逐行分析 `put` 方法的源碼，揭示其底層數據結構和關鍵設計思想。我們將從哈希計算開始，逐步深入到數組擴容、鏈表轉紅黑樹等核心機制。
## 二、HashMap 基礎結構回顧
在分析 `put` 方法前，先回顧 HashMap 的核心組成：
```java
// 默認初始容量 16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
// 最大容量 2^30
static final int MAXIMUM_CAPACITY = 1 << 30;
// 默認負載因子 0.75
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 鏈表轉紅黑樹的閾值
static final int TREEIFY_THRESHOLD = 8;
// 存儲數據的 Node 數組
transient Node<K,V>[] table;
// 鍵值對數量
transient int size;
HashMap 采用 數組 + 鏈表/紅黑樹 的存儲結構，通過哈希算法確定元素在數組中的位置。
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
put 方法實際調用的是 putVal，其中 hash(key) 是關鍵的第一步：
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
哈希計算特點： 1. 允許 null 鍵（存儲在數組第 0 個位置） 2. 通過高位異或減少哈希沖突（擾動函數）
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
// 步驟1：table為空時初始化
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 步驟2：計算數組下標并處理空桶情況
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
// 步驟3：處理哈希沖突
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p; // 情況1：key已存在
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
// 情況2：遍歷鏈表
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;
}
}
// 步驟4：處理key已存在的情況
if (e != null) {
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
// 步驟5：檢查擴容
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
當首次 put 元素時，會觸發 resize() 初始化數組：
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
// ... 計算新容量和新閾值 ...
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
// ... 可能的元素遷移 ...
return newTab;
}
通過 (n - 1) & hash 計算索引（相當于取模運算）：
i = (table.length - 1) & hash
當發生哈希沖突時，分為三種情況處理：
1. Key 已存在：直接覆蓋值
2. 紅黑樹節點：調用 putTreeVal
3. 鏈表結構：
- 遍歷到鏈表尾部插入新節點
- 當鏈表長度 ≥ 8 時轉為紅黑樹
當檢測到 key 已存在時，根據 onlyIfAbsent 參數決定是否覆蓋舊值。
每次插入后檢查 size > threshold，觸發擴容：
if (++size > threshold)
resize();
當鏈表長度達到 8 時，會調用 treeifyBin：
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize(); // 數組長度小于64時優先擴容
else if ((e = tab[index = (n - 1) & hash]) != null) {
// 轉換為TreeNode鏈表
TreeNode<K,V> hd = null, tl = null;
do {
TreeNode<K,V> p = replacementTreeNode(e, null);
if (tl == null)
hd = p;
else {
p.prev = tl;
tl.next = p;
}
tl = p;
} while ((e = e.next) != null);
// 將TreeNode鏈表轉為紅黑樹
if ((tab[index] = hd) != null)
hd.treeify(tab);
}
}
樹化的兩個條件： 1. 鏈表長度 ≥ 8 2. 數組長度 ≥ 64（否則優先擴容）
hashCode() 和 equals()通過對 put 方法的逐步分析，我們可以看到 HashMap 如何優雅地處理：
- 哈希沖突（鏈表+紅黑樹）
- 動態擴容（2倍擴容+元素遷移）
- 性能優化（樹化閾值、哈希計算等）
理解這些底層機制，有助于我們更好地使用和調優 HashMap。
本文基于 Java 8 HashMap 源碼分析，不同版本實現可能有差異 “`
注：本文實際約2300字，可通過擴展以下內容達到2500字： 1. 增加更多源碼注釋解釋 2. 補充紅黑樹操作細節 3. 添加與Java 7的對比分析 4. 增加實際性能測試數據 5. 擴展線程安全相關討論
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
