HashMap 作为 Java 最核心的集合类其扩容机制是保证高效存取的关键也是面试中最容易被深挖的考点。本文将结合两张思维导图从通用流程、版本差异、源码细节、面试陷阱四个维度彻底拆解 HashMap 扩容的底层逻辑让你不仅知其然更知其所以然。一、扩容的本质与核心目标1.1 什么是扩容扩容是 HashMap 为了应对元素增多、哈希冲突加剧而执行的动态调整机制底层数组哈希桶容量不足时创建一个2 倍大小的新数组将旧数组中所有元素重新计算位置迁移到新数组中最终目的减少哈希冲突避免链表 / 红黑树过长维持 O (1) 级别的平均存取效率1.2 为什么必须扩容如果不扩容随着元素不断插入哈希桶被占满大量 key 会挂载到同一个链表 / 红黑树下查找效率从 O (1) 急剧退化到 O (n)链表或 O (log n)红黑树极端情况下HashMap 会退化成 “链表集合”性能极差二、通用扩容流程JDK 1.7/1.8 共用核心步骤2.1 触发条件什么时候才会扩容扩容不是自动触发需要满足以下两类条件条件一元素数量超过阈值1.7/1.8 通用// 阈值计算公式 threshold capacity * loadFactor; // 触发条件 if (size threshold) { resize(); // 执行扩容 }capacity当前哈希桶数组的长度默认初始 16loadFactor加载因子默认 0.75示例初始容量 16阈值 16 * 0.75 12 → 当第 13 个元素插入时触发扩容 加载因子 0.75 是空间与时间的平衡太小会频繁扩容浪费内存太大则冲突加剧、查询变慢。条件二链表树化前置扩容仅 JDK 1.8// 树化判断逻辑JDK 1.8 if (binCount TREEIFY_THRESHOLD - 1) // binCount 是当前链表长度 treeifyBin(tab, hash); // treeifyBin 方法内部判断 if (tab null || (n tab.length) MIN_TREEIFY_CAPACITY) // MIN_TREEIFY_CAPACITY 64 resize(); // 优先扩容而非树化当某个链表长度 ≥ 8但数组长度 64 时优先扩容而非转为红黑树原因小容量数组下树化会浪费内存且扩容后链表长度大概率会缩短更高效2.2 扩容第一步创建新数组无论哪个版本扩容时都会创建2 倍容量的新数组// JDK 1.8 resize() 核心代码 oldCap table.length; newCap oldCap 1; // 等价于 oldCap * 2位运算更高效 newThr oldThr 1; // 阈值也同步翻倍新容量必须是2 的幂次方这是 HashMap 设计的核心约束约束原因下标计算用位运算hash (capacity - 1)替代取模速度更快扩容时可通过高位判断快速定位新下标无需重新计算哈希2.3 扩容核心元素迁移JDK 1.8 详细流程元素迁移是扩容最复杂的环节JDK 1.8 做了极致优化我们先看 1.8 的完整迁移流程迁移前准备新下标计算规则JDK 1.8 不再重新计算哈希而是通过位运算直接推导新下标// 旧下标hash (oldCap - 1) // 新下标判断hash oldCap if ((hash oldCap) 0) { newIndex oldIndex; // 低位链表位置不变 } else { newIndex oldIndex oldCap; // 高位链表位置偏移旧容量 }原理旧容量是 2^n二进制只有 1 位是 1如 16 → 10000hash oldCap结果只有 0 或 oldCap刚好把元素分成两类结果为 0 → 新下标 旧下标low组结果为 oldCap → 新下标 旧下标 oldCaphigh组迁移四部曲JDK 1.8 独有遍历旧数组若当前桶位置为null直接跳过无需迁移若不为空进入后续迁移逻辑单个节点迁移桶中只有一个节点时直接计算hash (newCap - 1)得到新下标放入新数组链表迁移按hash oldCap拆分为low和high两条链表用尾插法保持原链表顺序分别迁移到新数组的oldIndex和oldIndex oldCap位置优势无需重新哈希整体迁移效率极高且不会倒置链表红黑树迁移同样按hash oldCap拆分为low树和high树拆分后判断子树节点数节点数 ≤ 6 → 调用untreeify()退化为链表节省内存节点数 6 → 保持红黑树结构继续高效查找退化阈值设为 6避免在 7、8 节点时频繁在链表和红黑树间切换保证性能稳定三、JDK 1.7 与 1.8 扩容方式核心差异对比3.1 插入方式不同版本插入方式底层影响JDK 1.7头插法扩容后链表会倒置多线程下易形成环形链表导致死循环JDK 1.8尾插法扩容后链表保持原顺序彻底避免了环形链表问题并发更安全 头插法缺陷多线程扩容时两个线程可能交替修改链表指针形成A → B → A的环形引用get()时遍历永远无法结束CPU 飙升至 100%。3.2 元素迁移方式不同版本迁移逻辑效率与特点JDK 1.7重新计算每个节点的下标逐个插入新数组效率极低需遍历每个节点重新哈希计算链表倒置时间复杂度 O (n)JDK 1.8拆分链表 / 红黑树整体迁移极致优化通过位运算拆分无需重新哈希链表 / 树整体迁移时间复杂度接近 O (n)且顺序不变3.3 并发安全性差异JDK 1.7头插法 链表倒置 → 多线程扩容必现环形链表死循环死循环会导致get()操作无限循环服务雪崩JDK 1.8尾插法 顺序保持 → 彻底解决环形链表问题但仍非线程安全多线程put()仍可能覆盖数据、丢失元素并发场景需用ConcurrentHashMap3.4 红黑树支持差异版本红黑树支持扩容时的结构变化JDK 1.7无红黑树全靠链表无树化 / 退化逻辑冲突严重时性能直接退化到 O (n)JDK 1.8链表 ≥8 且数组 ≥64 时树化扩容时红黑树会被拆分节点数 ≤6 时退化为链表平衡空间与性能四、源码级细节深挖JDK 1.84.1 新下标位运算原理示例假设旧容量oldCap 16二进制10000新容量newCap 32二进制100000旧下标hash 1501111→ 只取低 4 位新下标hash 31011111→ 取低 5 位差异仅在第 5 位16的位置若hash第 5 位为 0 →hash 16 0→ 新下标 旧下标若hash第 5 位为 1 →hash 16 16→ 新下标 旧下标 16这就是 JDK 1.8 能高效迁移的核心数学基础。4.2 红黑树退化的底层考量红黑树节点TreeNode内存占用是普通链表节点Node的2 倍以上节点数少时链表遍历速度反而更快且更省内存阈值设为 6避免在 7、8 节点时频繁切换结构减少性能抖动源码中UNTREEIFY_THRESHOLD 6TREEIFY_THRESHOLD 8中间留 7 作为缓冲4.3 JDK 1.7 死循环复现原理// JDK 1.7 迁移代码简化版 void transfer(Entry[] newTable) { Entry[] src table; int newCapacity newTable.length; for (int j 0; j src.length; j) { EntryK,V e src[j]; if (e ! null) { do { EntryK,V next e.next; int i indexFor(e.hash, newCapacity); // 重新计算下标 e.next newTable[i]; // 头插法e.next 指向新桶头节点 newTable[i] e; // 新桶头节点更新为 e e next; } while (e ! null); } } }多线程下线程 1 和线程 2 同时处理同一链表线程 1 执行到e.next newTable[i]时被挂起线程 2 完成迁移链表倒置为B → A线程 1 恢复执行继续处理A将A.next指向B形成A → B → A环形引用最终get(A)时会无限循环遍历环形链表导致 CPU 100%五、面试高频考点与陷阱5.1 高频面试题HashMap 扩容为什么是 2 倍而不是 1.5 倍或 3 倍保持容量为 2 的幂方便位运算计算下标扩容时可快速拆分元素2 倍扩容能保证元素均匀分布减少哈希冲突位运算 1比乘法* 2更快底层优化更友好JDK 1.8 扩容时红黑树为什么会退化红黑树内存开销大节点数少时链表性能更优退化是空间与效率的平衡避免小节点数下的内存浪费JDK 1.7 扩容死循环的根本原因是什么头插法导致链表倒置多线程下指针交叉引用形成环形链表为什么加载因子默认是 0.75泊松分布统计0.75 时哈希冲突概率最低空间与时间效率最优太小会频繁扩容太大则冲突加剧、查询变慢5.2 常见误区❌ 误区JDK 1.8 是线程安全的✅ 纠正JDK 1.8 只是解决了死循环问题多线程put()仍会覆盖数据、丢失元素并发场景必须用ConcurrentHashMap❌ 误区链表长度 ≥8 就一定会转红黑树✅ 纠正必须同时满足数组长度 ≥64否则优先扩容❌ 误区扩容时会重新计算所有元素的哈希值✅ 纠正JDK 1.8 不会重新哈希仅通过位运算判断高位效率极高六、总结HashMap 扩容是其设计精妙的体现JDK 1.8 的优化是里程碑式的核心优化位运算拆分迁移、尾插法避免死循环、红黑树提升极端冲突性能本质通过动态扩容和结构优化让 HashMap 在绝大多数场景下保持 O (1) 存取效率同时兼顾空间与性能核心价值理解扩容流程不仅能写出更高效的代码更能在面试中从容应对各类底层原理问题
深入 HashMap 扩容全流程：从触发条件到源码实现，1.7 与 1.8 版本逐点拆解
HashMap 作为 Java 最核心的集合类其扩容机制是保证高效存取的关键也是面试中最容易被深挖的考点。本文将结合两张思维导图从通用流程、版本差异、源码细节、面试陷阱四个维度彻底拆解 HashMap 扩容的底层逻辑让你不仅知其然更知其所以然。一、扩容的本质与核心目标1.1 什么是扩容扩容是 HashMap 为了应对元素增多、哈希冲突加剧而执行的动态调整机制底层数组哈希桶容量不足时创建一个2 倍大小的新数组将旧数组中所有元素重新计算位置迁移到新数组中最终目的减少哈希冲突避免链表 / 红黑树过长维持 O (1) 级别的平均存取效率1.2 为什么必须扩容如果不扩容随着元素不断插入哈希桶被占满大量 key 会挂载到同一个链表 / 红黑树下查找效率从 O (1) 急剧退化到 O (n)链表或 O (log n)红黑树极端情况下HashMap 会退化成 “链表集合”性能极差二、通用扩容流程JDK 1.7/1.8 共用核心步骤2.1 触发条件什么时候才会扩容扩容不是自动触发需要满足以下两类条件条件一元素数量超过阈值1.7/1.8 通用// 阈值计算公式 threshold capacity * loadFactor; // 触发条件 if (size threshold) { resize(); // 执行扩容 }capacity当前哈希桶数组的长度默认初始 16loadFactor加载因子默认 0.75示例初始容量 16阈值 16 * 0.75 12 → 当第 13 个元素插入时触发扩容 加载因子 0.75 是空间与时间的平衡太小会频繁扩容浪费内存太大则冲突加剧、查询变慢。条件二链表树化前置扩容仅 JDK 1.8// 树化判断逻辑JDK 1.8 if (binCount TREEIFY_THRESHOLD - 1) // binCount 是当前链表长度 treeifyBin(tab, hash); // treeifyBin 方法内部判断 if (tab null || (n tab.length) MIN_TREEIFY_CAPACITY) // MIN_TREEIFY_CAPACITY 64 resize(); // 优先扩容而非树化当某个链表长度 ≥ 8但数组长度 64 时优先扩容而非转为红黑树原因小容量数组下树化会浪费内存且扩容后链表长度大概率会缩短更高效2.2 扩容第一步创建新数组无论哪个版本扩容时都会创建2 倍容量的新数组// JDK 1.8 resize() 核心代码 oldCap table.length; newCap oldCap 1; // 等价于 oldCap * 2位运算更高效 newThr oldThr 1; // 阈值也同步翻倍新容量必须是2 的幂次方这是 HashMap 设计的核心约束约束原因下标计算用位运算hash (capacity - 1)替代取模速度更快扩容时可通过高位判断快速定位新下标无需重新计算哈希2.3 扩容核心元素迁移JDK 1.8 详细流程元素迁移是扩容最复杂的环节JDK 1.8 做了极致优化我们先看 1.8 的完整迁移流程迁移前准备新下标计算规则JDK 1.8 不再重新计算哈希而是通过位运算直接推导新下标// 旧下标hash (oldCap - 1) // 新下标判断hash oldCap if ((hash oldCap) 0) { newIndex oldIndex; // 低位链表位置不变 } else { newIndex oldIndex oldCap; // 高位链表位置偏移旧容量 }原理旧容量是 2^n二进制只有 1 位是 1如 16 → 10000hash oldCap结果只有 0 或 oldCap刚好把元素分成两类结果为 0 → 新下标 旧下标low组结果为 oldCap → 新下标 旧下标 oldCaphigh组迁移四部曲JDK 1.8 独有遍历旧数组若当前桶位置为null直接跳过无需迁移若不为空进入后续迁移逻辑单个节点迁移桶中只有一个节点时直接计算hash (newCap - 1)得到新下标放入新数组链表迁移按hash oldCap拆分为low和high两条链表用尾插法保持原链表顺序分别迁移到新数组的oldIndex和oldIndex oldCap位置优势无需重新哈希整体迁移效率极高且不会倒置链表红黑树迁移同样按hash oldCap拆分为low树和high树拆分后判断子树节点数节点数 ≤ 6 → 调用untreeify()退化为链表节省内存节点数 6 → 保持红黑树结构继续高效查找退化阈值设为 6避免在 7、8 节点时频繁在链表和红黑树间切换保证性能稳定三、JDK 1.7 与 1.8 扩容方式核心差异对比3.1 插入方式不同版本插入方式底层影响JDK 1.7头插法扩容后链表会倒置多线程下易形成环形链表导致死循环JDK 1.8尾插法扩容后链表保持原顺序彻底避免了环形链表问题并发更安全 头插法缺陷多线程扩容时两个线程可能交替修改链表指针形成A → B → A的环形引用get()时遍历永远无法结束CPU 飙升至 100%。3.2 元素迁移方式不同版本迁移逻辑效率与特点JDK 1.7重新计算每个节点的下标逐个插入新数组效率极低需遍历每个节点重新哈希计算链表倒置时间复杂度 O (n)JDK 1.8拆分链表 / 红黑树整体迁移极致优化通过位运算拆分无需重新哈希链表 / 树整体迁移时间复杂度接近 O (n)且顺序不变3.3 并发安全性差异JDK 1.7头插法 链表倒置 → 多线程扩容必现环形链表死循环死循环会导致get()操作无限循环服务雪崩JDK 1.8尾插法 顺序保持 → 彻底解决环形链表问题但仍非线程安全多线程put()仍可能覆盖数据、丢失元素并发场景需用ConcurrentHashMap3.4 红黑树支持差异版本红黑树支持扩容时的结构变化JDK 1.7无红黑树全靠链表无树化 / 退化逻辑冲突严重时性能直接退化到 O (n)JDK 1.8链表 ≥8 且数组 ≥64 时树化扩容时红黑树会被拆分节点数 ≤6 时退化为链表平衡空间与性能四、源码级细节深挖JDK 1.84.1 新下标位运算原理示例假设旧容量oldCap 16二进制10000新容量newCap 32二进制100000旧下标hash 1501111→ 只取低 4 位新下标hash 31011111→ 取低 5 位差异仅在第 5 位16的位置若hash第 5 位为 0 →hash 16 0→ 新下标 旧下标若hash第 5 位为 1 →hash 16 16→ 新下标 旧下标 16这就是 JDK 1.8 能高效迁移的核心数学基础。4.2 红黑树退化的底层考量红黑树节点TreeNode内存占用是普通链表节点Node的2 倍以上节点数少时链表遍历速度反而更快且更省内存阈值设为 6避免在 7、8 节点时频繁切换结构减少性能抖动源码中UNTREEIFY_THRESHOLD 6TREEIFY_THRESHOLD 8中间留 7 作为缓冲4.3 JDK 1.7 死循环复现原理// JDK 1.7 迁移代码简化版 void transfer(Entry[] newTable) { Entry[] src table; int newCapacity newTable.length; for (int j 0; j src.length; j) { EntryK,V e src[j]; if (e ! null) { do { EntryK,V next e.next; int i indexFor(e.hash, newCapacity); // 重新计算下标 e.next newTable[i]; // 头插法e.next 指向新桶头节点 newTable[i] e; // 新桶头节点更新为 e e next; } while (e ! null); } } }多线程下线程 1 和线程 2 同时处理同一链表线程 1 执行到e.next newTable[i]时被挂起线程 2 完成迁移链表倒置为B → A线程 1 恢复执行继续处理A将A.next指向B形成A → B → A环形引用最终get(A)时会无限循环遍历环形链表导致 CPU 100%五、面试高频考点与陷阱5.1 高频面试题HashMap 扩容为什么是 2 倍而不是 1.5 倍或 3 倍保持容量为 2 的幂方便位运算计算下标扩容时可快速拆分元素2 倍扩容能保证元素均匀分布减少哈希冲突位运算 1比乘法* 2更快底层优化更友好JDK 1.8 扩容时红黑树为什么会退化红黑树内存开销大节点数少时链表性能更优退化是空间与效率的平衡避免小节点数下的内存浪费JDK 1.7 扩容死循环的根本原因是什么头插法导致链表倒置多线程下指针交叉引用形成环形链表为什么加载因子默认是 0.75泊松分布统计0.75 时哈希冲突概率最低空间与时间效率最优太小会频繁扩容太大则冲突加剧、查询变慢5.2 常见误区❌ 误区JDK 1.8 是线程安全的✅ 纠正JDK 1.8 只是解决了死循环问题多线程put()仍会覆盖数据、丢失元素并发场景必须用ConcurrentHashMap❌ 误区链表长度 ≥8 就一定会转红黑树✅ 纠正必须同时满足数组长度 ≥64否则优先扩容❌ 误区扩容时会重新计算所有元素的哈希值✅ 纠正JDK 1.8 不会重新哈希仅通过位运算判断高位效率极高六、总结HashMap 扩容是其设计精妙的体现JDK 1.8 的优化是里程碑式的核心优化位运算拆分迁移、尾插法避免死循环、红黑树提升极端冲突性能本质通过动态扩容和结构优化让 HashMap 在绝大多数场景下保持 O (1) 存取效率同时兼顾空间与性能核心价值理解扩容流程不仅能写出更高效的代码更能在面试中从容应对各类底层原理问题
