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字，包含代码示例、流程分析和解决方案）