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

HashMap夺命连环问为何容量必须是2的幂头插法死循环到底怎么产生的摘要HashMap 是面试中的“常客”从底层数据结构到并发陷阱总能衍生出一系列进阶问题。本文聚焦两个最经典的“夺命连环问”为什么 HashMap 的容量必须设计为 2 的幂以及 JDK 7 中头插法导致死循环的底层逻辑。结合源码、图解与流程图一次性讲透这些核心难点。1. 数据结构总览数组链表红黑树JDK 8 中的 HashMap 采用数组 链表 红黑树的复合结构。数组存储桶(bucket)的基座每个位置称为一个“槽位(slot)”。链表解决哈希冲突当多个 Key 映射到同一槽位时以链表形式串联。红黑树当链表长度 ≥ 8 且数组长度 ≥ 64 时链表会树化为红黑树将查找复杂度从 O(n) 降为 O(log n)。transient NodeK,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高位全 0n 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 10n - 1 9 0000 0000 0000 1001与操作时中间两位永远是 0导致某些槽位永远无法被命中如 0010、0110 等碰撞概率大幅增加。2.3 扩容时的精妙之处扩容时元素需要迁移到新数组。因为容量扩大为 2 倍新槽位只可能落在两个位置原位 indexhash oldCap 0的元素。原位 oldCaphash oldCap ! 0的元素。这样避免了重新计算 hash只需判断新增的那一位比特是 0 还是 1高效完成迁移。2.4 容量计算tableSizeForHashMap 的构造方法允许传入任意初始容量内部通过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 的幂。流程图如下输入cap 13n cap - 1 12n | n 1n | n 2n | n 4n | n 8n | n 16n 1 16返回16---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 (EntryK,V e : table) { while(null ! e) { EntryK,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 - BA 指向 B两个线程 T1 和 T2 同时触发扩容。初始状态原链表: A - B - nullT1 执行到EntryK,V next e.next;后挂起此时T1: e A, next BT2 完整执行完扩容迁移后新链表变为头插导致倒序T2 新链表: B - A - nullT1 被唤醒继续执行第一次循环e A,next BA 插入 T1 的新桶A.next nullT1 的新桶此时为空→ 新桶: Ae next BT1 执行第二次循环e B,next B.next此时 B 是 T2 新链表中的节点T2 中B.next A所以next AB 插入 T1 的新桶头插B.next A→ 新桶: B - Ae next AT1 执行第三次循环e A,next A.next此时 A 在 T1 的新桶中A.next null所以next nullA 插入 T1 的新桶头插A.next B→ 新桶: A - B - A - ...此时形成环形链表A ↔ B环形链表形成AB3.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 使用尾插法并且将迁移算法彻底重构尾插法新元素始终插在链表尾部原始顺序被保留避免了倒序带来的循环引用。高低位链表扩容时不再逐个节点迁移而是根据(e.hash oldCap)将一条链表拆成“原位”和“原位oldCap”两条链表一次性迁移。// JDK 8 扩容迁移核心逻辑简化版 NodeK,V loHead null, loTail null; // 低位链 NodeK,V hiHead null, hiTail null; // 高位链 NodeK,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. 总结容量为 2 的幂是为了用(n-1) hash替代取模实现高效且均匀的散列同时扩容时能快速拆分高低位链表。JDK 7 头插法死循环根源在于并发扩容时transfer方法中的头插操作导致链表倒序多线程交叉执行可能形成 A↔B 的环形引用。后续遍历时触发while(e!null)死循环。JDK 8 的改进以尾插法保持链表顺序配合高低位拆分迁移从根本上杜绝了环形链表的产生。但 HashMap 本身仍不是线程安全的并发场景务必使用ConcurrentHashMap。