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