企业官网建设流程全解析

HashMap夺命连环问：为何容量必须是2的幂？头插法死循环到底怎么产生的？

摘要：HashMap 是面试中的“常客”，从底层数据结构到并发陷阱，总能衍生出一系列进阶问题。本文聚焦两个最经典的“夺命连环问”：为什么 HashMap 的容量必须设计为 2 的幂，以及 JDK 7 中头插法导致死循环的底层逻辑。结合源码、图解与流程图，一次性讲透这些核心难点。

1. 数据结构总览：数组+链表+红黑树

JDK 8 中的 HashMap 采用数组 + 链表 + 红黑树的复合结构。

• 数组：存储桶(bucket)的基座，每个位置称为一个“槽位(slot)”。
• 链表：解决哈希冲突，当多个 Key 映射到同一槽位时，以链表形式串联。
• 红黑树：当链表长度 ≥ 8 且数组长度 ≥ 64 时，链表会树化为红黑树，将查找复杂度从 O(n) 降为 O(log n)。

transient Node<K,V>[] table; // 桶数组 transient int size; // 实际键值对数量 int threshold; // 扩容阈值 = capacity * loadFactor final float loadFactor; // 负载因子，默认0.75

---

2. 核心问题一：为何容量必须是2的幂？

2.1 哈希寻址算法

HashMap 中定位桶位置的核心代码如下：

// 计算key的hash值 (h = key.hashCode()) ^ (h >>> 16) int hash = hash(key); // 定位桶下标 int index = (n - 1) & hash;

其中n是数组长度。这里用(n - 1) & hash代替hash % n，位运算效率远高于取模。

2.2 2的幂带来的“低位掩码”效果

当n = 2^k时，n - 1的二进制是低 k 位全 1，高位全 0：

n = 16 (2^4) => n - 1 = 15 => 0000 0000 0000 1111 n = 32 (2^5) => n - 1 = 31 => 0000 0000 0001 1111

此时(n - 1) & hash的效果就是取 hash 值的低 k 位。这等价于一个均匀的取模操作，且每一位都参与运算，散列均匀。

如果容量不是 2 的幂，比如n = 10：

n - 1 = 9 => 0000 0000 0000 1001

与操作时中间两位永远是 0，导致某些槽位永远无法被命中（如 0010、0110 等），碰撞概率大幅增加。

2.3 扩容时的精妙之处

扩容时，元素需要迁移到新数组。因为容量扩大为 2 倍，新槽位只可能落在两个位置：

• 原位 index：hash & oldCap == 0的元素。
• 原位 + oldCap：hash & oldCap != 0的元素。

这样避免了重新计算 hash，只需判断新增的那一位比特是 0 还是 1，高效完成迁移。

2.4 容量计算：tableSizeFor

HashMap 的构造方法允许传入任意初始容量，内部通过tableSizeFor方法强制转为 2 的幂：

static final int tableSizeFor(int cap) { int n = cap - 1; n |= n >>> 1; n |= n >>> 2; n |= n >>> 4; n |= n >>> 8; n |= n >>> 16; return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1; }

通过 5 次右移和位或，将最高位的 1 之后所有位全部填满 1，最后加 1 得到刚好大于等于cap的 2 的幂。流程图如下：

---

3. 核心问题二：JDK 7 头插法死循环到底怎么产生的？

3.1 JDK 7 与 JDK 8 的核心区别

| 特性 | JDK 7 | JDK 8 |

|------|-------|-------|

| 数据结构 | 数组 + 链表 | 数组 + 链表 + 红黑树 |

| 插入方式 |头插法（新元素插在链表头部） |尾插法（新元素插在链表尾部） |

| 扩容元素迁移顺序 | 原链表倒序| 原链表保持顺序|

| 并发扩容 | 可能形成环形链表导致死循环 | 不会形成环，但仍有数据丢失风险 |

3.2 JDK 7 扩容核心代码

void transfer(Entry[] newTable, boolean rehash) { int newCapacity = newTable.length; for (Entry<K,V> e : table) { while(null != e) { Entry<K,V> next = e.next; // 1. 记录下一个节点 if (rehash) { e.hash = null == e.key ? 0 : hash(e.key); } int i = indexFor(e.hash, newCapacity); // 2. 计算新槽位 e.next = newTable[i]; // 3. 当前节点指向新桶的头部 newTable[i] = e; // 4. 新桶头部指向当前节点（头插） e = next; // 5. 处理下一个节点 } } }

关键操作是第 3、4 行：总是将新元素插到链表的头部。单线程下没有问题，但多线程并发扩容时，可能形成环形链表。

3.3 环形链表产生过程图解

假设原数组有两个元素 A -> B（A 指向 B），两个线程 T1 和 T2 同时触发扩容。

初始状态：

原链表: A -> B -> null

T1 执行到Entry<K,V> next = e.next;后挂起，此时：

T1: e = A, next = B

T2 完整执行完扩容，迁移后新链表变为（头插导致倒序）：

T2 新链表: B -> A -> null

T1 被唤醒，继续执行第一次循环：

• e = A,next = B
• A 插入 T1 的新桶：A.next = null（T1 的新桶此时为空）→ 新桶: A
• e = next = B

T1 执行第二次循环：

• e = B,next = B.next
• 此时 B 是 T2 新链表中的节点，T2 中B.next = A，所以next = A
• B 插入 T1 的新桶（头插）：B.next = A→ 新桶: B -> A
• e = next = A

T1 执行第三次循环：

• e = A,next = A.next（此时 A 在 T1 的新桶中，A.next = null，所以next = null）
• A 插入 T1 的新桶（头插）：A.next = B→ 新桶: A -> B -> A -> ...
• 此时形成环形链表：A ↔ B

3.4 死循环触发

当调用get(key)查找一个不在此环中的键时，会遍历链表进入while(e != null)死循环，CPU 瞬间飙升到 100%。

// get 方法中的遍历逻辑 do { if (e.hash == hash && key.equals(e.key)) return e.value; } while ((e = e.next) != null); // 环形链表中，e.next 永远不为 null

---

4. JDK 8 如何解决这个问题？

JDK 8 使用尾插法并且将迁移算法彻底重构：

1. 尾插法：新元素始终插在链表尾部，原始顺序被保留，避免了倒序带来的循环引用。
2. 高低位链表：扩容时不再逐个节点迁移，而是根据(e.hash & oldCap)将一条链表拆成“原位”和“原位+oldCap”两条链表，一次性迁移。

// JDK 8 扩容迁移核心逻辑（简化版） Node<K,V> loHead = null, loTail = null; // 低位链 Node<K,V> hiHead = null, hiTail = null; // 高位链 Node<K,V> next; do { next = e.next; if ((e.hash & oldCap) == 0) { // 保持在原位 if (loTail == null) loHead = e; else loTail.next = e; loTail = e; } else { // 迁移到原位 + oldCap if (hiTail == null) hiHead = e; else hiTail.next = e; hiTail = e; } } while ((e = next) != null); // 将两条链放到新数组对应位置 if (loTail != null) { loTail.next = null; newTab[j] = loHead; } if (hiTail != null) { hiTail.next = null; newTab[j + oldCap] = hiHead; }

这样既不会形成环形链表，又提高了迁移效率。

---

5. 总结

1. 容量为 2 的幂，是为了用(n-1) & hash替代取模，实现高效且均匀的散列；同时扩容时能快速拆分高低位链表。
2. JDK 7 头插法死循环，根源在于并发扩容时，transfer方法中的头插操作导致链表倒序，多线程交叉执行可能形成 A↔B 的环形引用。后续遍历时触发while(e!=null)死循环。
3. JDK 8 的改进，以尾插法保持链表顺序，配合高低位拆分迁移，从根本上杜绝了环形链表的产生。但 HashMap 本身仍不是线程安全的，并发场景务必使用ConcurrentHashMap。