目錄
一、HashMap基礎結構
二、put操作流程分析
put操作關鍵步驟總結
三、get操作流程分析
get操作關鍵步驟總結
四、延伸
1.hash()方法
2. 擴容
resize()方法的主要邏輯：
Java 8中對擴容的優化：
3. 轉向紅黑樹的條件
HashMap作為Java集合框架中最重要且最常用的數據結構之一，其內部實現機制值得深入探究。本文將從源碼角度分析HashMap的get和put操作流程，基于Java 8的實現進行講解。
一、HashMap基礎結構
在講解get和put之前，我們先了解HashMap的核心結構：
// HashMap的主要成員變量
transient Node<K,V>[] table; // 存儲元素的數組
transient int size; // 實際存儲的鍵值對數量
int threshold; // 擴容閾值 (capacity * loadFactor)
final float loadFactor; // 負載因子(默認0.75)HashMap采用"數組+鏈表+紅黑樹"的混合存儲結構：
數組(table)是主體
當哈希沖突時，使用鏈表法解決
當鏈表長度超過8且數組長度≥64時，鏈表轉為紅黑樹
二、put操作流程分析
put操作是HashMap的核心功能之一，其中主要方法為：
public V put(K key, V value) {return putVal(hash(key), key, value, false, true);
}核心邏輯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;// 步驟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 {Node<K,V> e; K k;// 步驟3：節點key已存在，直接覆蓋valueif (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))e = p;// 步驟4：判斷是否為樹節點else if (p instanceof TreeNode)e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);// 步驟5：鏈表處理else {for (int binCount = 0; ; ++binCount) {if ((e = p.next) == null) {p.next = newNode(hash, key, value, null);// 鏈表長度≥8轉為紅黑樹if (binCount >= TREEIFY_THRESHOLD - 1)treeifyBin(tab, hash);break;}// key已存在則跳出循環if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))break;p = e;}}// 步驟6：寫入valueif (e != null) { // existing mapping for keyV oldValue = e.value;if (!onlyIfAbsent || oldValue == null)e.value = value;afterNodeAccess(e);return oldValue;}}// 步驟7：超過閾值則擴容++modCount;if (++size > threshold)resize();afterNodeInsertion(evict);return null;
}put操作關鍵步驟總結
-
計算哈希值：通過hash()方法計算key的哈希值
-
初始化檢查：如果table為空，則調用resize()初始化
-
定位桶位置：通過
(n-1) & hash計算數組下標（等價于hash % n，但效率更高--位運算比取模快） -
處理沖突：
-
如果該位置為空，直接插入新節點
-
如果key已存在，則覆蓋value
-
如果是樹節點，調用紅黑樹的插入方法
-
如果是鏈表，遍歷鏈表并在尾部插入
-
-
樹化檢查：鏈表長度≥8時可能轉為紅黑樹
-
擴容檢查：size超過threshold則擴容
三、get操作流程分析
首先來看get的實現方法：
public V get(Object key) {Node<K,V> e;return (e = getNode(hash(key), key)) == null ? null : e.value;
}其核心實現getNode方法解析：
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且對應位置有節點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) {// 步驟4：如果是樹節點if (first instanceof TreeNode)return ((TreeNode<K,V>)first).getTreeNode(hash, key);// 步驟5：遍歷鏈表do {if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))return e;} while ((e = e.next) != null);}}return null;
}get操作關鍵步驟總結
-
計算哈希值：與put相同的hash()方法
-
定位桶位置：同樣的
(n-1) & hash計算方式 -
檢查首節點：先比較hash，再比較key
-
處理沖突：
-
如果是樹節點，調用紅黑樹的查找方法
-
如果是鏈表，遍歷查找
-
-
返回結果：找到返回value，未找到返回null
四、延伸
1.hash()方法
static final int hash(Object key) {int h;return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}可以看見代碼中將高16位與低16位異或，這么做可以實現：
減少哈希沖突
充分利用高位的哈希信息
使哈希分布更加均勻
2. 擴容
resize()方法的主要邏輯：
計算新容量和新閾值
創建新數組
將舊數組元素重新分配到新數組（rehash）
Java 8中對擴容的優化：
無需重新計算hash，通過
(e.hash & oldCap) == 0判斷位置元素要么在原位置，要么在原位置+oldCap的位置
3. 轉向紅黑樹的條件
鏈表轉為紅黑樹的兩個條件：
-
鏈表長度 ≥ TREEIFY_THRESHOLD(8)
-
數組長度 ≥ MIN_TREEIFY_CAPACITY(64)
【注】上面表示默認情況下是鏈表長度-8，且數組長度-64
否則會優先進行擴容而不是轉向紅黑樹。
)
)
