JDK7 HashMap环的产生原理是什么

# JDK7 HashMap环的产生原理是什么

## 引言
在Java开发中，`HashMap`是最常用的数据结构之一。JDK7中的`HashMap`在多线程环境下存在一个著名的线程安全问题——**死循环环问题**。本文将深入剖析这一问题的产生原理，从数据结构、扩容机制到并发场景下的具体表现，逐步揭示环形成的本质原因。

---

## 一、HashMap基础结构回顾
JDK7的`HashMap`采用**数组+链表**的实现方式：
```java
transient Entry<K,V>[] table; // 存储元素的数组
static class Entry<K,V> {
    final K key;
    V value;
    Entry<K,V> next; // 链表指针
}

• 通过哈希函数计算键的存放位置
• 哈希冲突时采用链地址法解决（链表结构）

二、触发环的核心场景：扩容（Rehashing）

当元素数量超过容量×负载因子时触发扩容：

void resize(int newCapacity) {
    Entry[] oldTable = table;
    int oldCapacity = oldTable.length;
    // 创建新数组并迁移数据（rehash）
    Entry[] newTable = new Entry[newCapacity];
    transfer(newTable); // 关键方法
    table = newTable;
}

三、环产生的具体过程

关键方法分析：transfer()

void transfer(Entry[] newTable) {
    for (Entry<K,V> e : table) { // 遍历旧数组
        while(null != e) {
            Entry<K,V> next = e.next; // 记录下一个节点
            int i = indexFor(e.hash, newTable.length); // 新位置计算
            e.next = newTable[i]; // 头插法
            newTable[i] = e;
            e = next; // 处理下一个节点
        }
    }
}

多线程下的危险操作

当两个线程同时执行transfer()时：

1. 初始状态
   假设旧表某桶的链表：A → B → null
   线程1执行到Entry<K,V> next = e.next;后挂起

2. 线程2完成扩容
   新表中链表变为：B → A → null（头插法导致逆序）

3. 线程1恢复执行

   • e = A, next = B（线程1的临时变量）
   • 将A插入新桶：A → null
   • e = B（从next获取）
   • 处理B时：B.next = A（因线程2修改了引用）
   • 最终形成：B → A → B… 的闭环

四、环产生的必要条件

1. 并发扩容：多个线程同时触发resize()
2. 头插法：JDK7采用头插法迁移节点（JDK8改为尾插法）
3. 链表结构：哈希冲突形成的链表结构

五、问题复现与验证

通过以下代码可复现问题：

final HashMap<Integer, Integer> map = new HashMap<>(2);
// 线程1
new Thread(() -> {
    for (int i = 0; i < 10000; i++) {
        map.put(i, i);
    }
}).start();
// 线程2
new Thread(() -> {
    for (int i = 10000; i < 20000; i++) {
        map.put(i, i);
    }
}).start();

使用jstack可观察到CPU占用率飙升，死循环特征。

六、JDK8的改进

JDK8针对此问题做出优化： 1. 改用尾插法维护链表顺序 2. 引入红黑树结构（当链表长度>8时转换） 3. 优化哈希算法减少冲突

但注意：JDK8的HashMap仍是非线程安全的，并发修改可能丢数据，推荐使用ConcurrentHashMap。

七、总结

JDK7 HashMap环问题的本质是并发环境下头插法导致的链表逆序操作引发引用闭环。理解这一原理有助于： - 深刻认识线程安全的重要性 - 合理选择并发容器 - 在面试中展现底层知识深度

关键启示：在多线程环境下必须使用ConcurrentHashMap或同步机制。

（示意图：展示链表从A→B变为B→A→B的过程） “`

注：实际使用时请替换示意图链接。如需进一步扩展，可以增加： 1. 哈希碰撞攻击的防御措施 2. 其他JDK7/8的HashMap差异 3. 使用调试工具观察内存状态的方法