JDK7 HashMap環的產生原理是怎樣的

# JDK7 HashMap環的產生原理是怎樣的

## 引言
在Java開發中，`HashMap`是最常用的數據結構之一。JDK7中的`HashMap`在多線程環境下存在一個著名的線程安全問題——**死循環環問題**。本文將深入剖析這一現象的產生原理，從數據結構、擴容機制到多線程沖突場景進行完整解析。

---

## 一、HashMap基礎結構回顧
JDK7的`HashMap`采用**數組+鏈表**的實現方式：
```java
transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;

static class Entry<K,V> implements Map.Entry<K,V> {
    final K key;
    V value;
    Entry<K,V> next; // 鏈表結構
    int hash;
}

當發生哈希沖突時，新元素會以頭插法插入鏈表（JDK8改為尾插法）。

二、觸發環的核心場景：擴容（Rehash）

當元素數量超過閾值 = 容量 * 負載因子時觸發擴容： 1. 創建新數組（2倍原大?。?2. 遍歷舊數組，重新計算每個Entry的索引（rehash） 3. 頭插法將Entry遷移到新數組

關鍵代碼片段

void transfer(Entry[] newTable) {
    for (Entry<K,V> e : table) { // 遍歷舊數組
        while(null != e) {
            Entry<K,V> next = e.next; // 暫存next節點
            int i = indexFor(e.hash, newTable.length); // 計算新位置
            e.next = newTable[i]; // 頭插法
            newTable[i] = e;
            e = next; // 處理鏈表下一個節點
        }
    }
}

三、多線程下的環產生過程

假設兩個線程T1、T2同時觸發擴容，且存在鏈表 A → B → null：

初始狀態

舊數組：bucket[0] = A → B → null
新數組：newTable（空）

線程T1執行到Entry<K,V> next = e.next后掛起

T1變量快照：
e = A, next = B

線程T2完成完整擴容

由于頭插法，新數組變為：

newTable[0] = B → A → null

線程T1恢復執行

1. 處理節點A：

   
   e = A, next = B
   A.next = newTable[0] = B → A → ...  // 形成 A → B → A 的環!
   newTable[0] = A
   e = B
   

2. 處理節點B：

   
   e = B, next = A  // 從線程T2的結果中獲取
   B.next = newTable[0] = A → B → A...
   newTable[0] = B
   e = A
   

3. 進入無限循環…

四、問題本質分析

1. 頭插法反轉鏈表順序：導致節點引用關系變化
2. 非原子性操作：e和next的臨時變量在多線程間不同步
3. 內存可見性：線程T1看不到T2已修改的B.next引用

五、問題復現與驗證

可通過以下步驟驗證： 1. 創建初始HashMap 2. 啟動兩個線程同時觸發put操作 3. 使用JDK自帶的jstack工具觀察線程狀態

jstack <pid> | grep -A 20 "deadlock"

六、解決方案

1. 升級到JDK8+：改用尾插法+紅黑樹結構
2. 使用線程安全容器：

   
   Map<String,String> map = new ConcurrentHashMap<>();
   

3. 外部同步（不推薦）：

   
   Collections.synchronizedMap(new HashMap<>());
   

總結

JDK7 HashMap的環問題本質是多線程并發修改數據結構導致的鏈表引用混亂。理解這一原理有助于我們： 1. 避免在生產環境錯誤使用非線程安全容器 2. 深入理解Java內存模型（JMM） 3. 掌握數據結構并發修改的風險點

注：JDK8通過尾插法和擴容時保持鏈表順序解決了該問題，但多線程下仍建議使用ConcurrentHashMap。 “`

（全文約900字，包含代碼示例、流程分析和解決方案）