HashMap的扩容机制，是Java面试里出现频率几乎最高的题，也是线上定位Map相关性能瓶颈时绕不开的底层逻辑。大多数人都能背出"当元素数量超过阈值就扩容到两倍"，但问到"为什么是2倍而不是1.5倍"、"扩容时节点到底怎么迁移"、"树化链表扩容后要不要还原"，很多人就含糊了。这篇文章不打算复述源码注释，而是从数据结构、位运算、工程权衡三个层面把扩容机制彻底讲透，同时附上我在实际项目里排查resize相关性能问题的一些经验，适合正在准备面试的开发者，也适合想要真正理解HashMap运行原理进而优化自身代码的人。
1. 扩容到底在扩什么：HashMap的结构前提与触发条件
1.1 数组加链表加红黑树的基本盘
HashMap的底层结构，本质上是一个Node数组，每个数组槽位对应一个桶。当多个键通过哈希函数映射到同一个桶时，就用链表把它们串起来。链表长度一长，查询效率会从常数级退化到线性级，所以在JDK 8之后，当某个桶的链表长度达到8且数组容量不小于64时，链表会转成红黑树，把最坏时间复杂度从O(n)压到O(log n)。
这里要特别注意的是，红黑树只是桶内冲突过多时的兜底策略。HashMap的设计初衷仍然是用数组下标定位来达到接近O(1)的访问速度，而要让数组下标定位有意义，数组的物理长度必须与元素总规模匹配。如果数组太小，元素一多，哈希取模结果就会大量撞车，链表的优势荡然无存。如果数组太大，内存浪费又让人无法接受。所以HashMap引入了一个动态伸缩机制，也就是题目里说的扩容机制。
可以把容量理解为"仓库的货架数量"，元素就是货物。货架太少，货物只能层层堆叠，找起来费劲；货架太多，大部分都空着，白白占用空间。扩容要解决的问题，就是在"放得下"和"不浪费"之间找到动态平衡点。HashMap没有在创建时一次分配巨大数组，而是一边放一边观察，快挤不下了就翻倍加货架。
1.2 什么时候触发扩容：阈值、负载因子、插入位置
触发扩容的条件，很多开发者以为是"数组长度不够了再扩"，这个理解并不准确。HashMap真正盯着的指标是size，也就是已经存了多少个键值对，而不是当前插入的下标是否越界。它有一个threshold字段，当size超过threshold时，才会触发resize。
threshold的计算公式是capacity乘以loadFactor。默认的负载因子是0.75，默认初始容量是16，那么第一次扩容前threshold就是16乘以0.75等于12。也就是说，HashMap实际存储的键值对数量达到12个时，数组还没装满，但已经决定要扩展到32。这里其实暗示了一个设计哲学：不要等到桶彻底填满才做调整，冲突的概率会随着占用率上升而加速恶化，必须留出缓冲。
还有一个容易忽略的细节：HashMap并非只有put时才判断扩容。在put一个键值对时，如果对应桶为空，也就是新插入的是这个桶的第一个节点，那么size会加1，然后才比较size和threshold。如果桶已经有节点，是追加到链表或树中，size同样加1，但原有桶的数量不变。所以判断的是"存的键值对总数"而不是"已经被占用的桶数"。
1.3 size、capacity、threshold三者关系
把这三者的关系理清，扩容机制就懂了一大半。capacity是数组长度，也就是桶的数量，它决定了哈希取模的范围。size是当前实际存储的键值对数量，它决定了HashMap的内存占用和查询性能。threshold是size的报警线，等于capacity乘以loadFactor，超过它就必须让数组翻倍。
很多人会混淆threshold和capacity。简单记一句话：capacity是"最多能开多少个桶"，threshold是"存到多少个元素就该换更大的桶阵"。扩容后，capacity变为原来的两倍，threshold也会同步变为原来的两倍，因为threshold始终跟随capacity和loadFactor的乘积。所以扩容不是无底洞，它会带着整个"容量体系"一起升级。
这里还涉及一个重要的初始化参数问题：如果通过构造函数指定initialCapacity，HashMap并不会直接把数组长度设成这个值，而是会通过tableSizeFor把它调整为大于等于该值的最小2的幂。比如指定17，实际容量会是32。这个细节很多人知道，但未必清楚为什么一定要2的幂，后面第3章会专门展开。
2. resize全流程拆解：桶数组翻倍、元素重新分布的内在逻辑
2.1 从16到32：旧数组到新数组的迁移
当resize被触发时，HashMap会创建一个新的Node数组，长度是旧数组的两倍，然后把旧数组所有桶里的节点重新安放到新数组。这个过程叫迁移。简单理解就是搬家，但不是整批货物原样挪过去，而是要把每个货物按照新门牌号重新入库。
迁移过程是从旧数组的索引0开始，一直遍历到最后一个桶。每个桶可能是空桶、链表桶或者红黑树桶。空桶直接跳过，链表桶拆成两个链表，红黑树桶则拆成两个子树并判断是否需要还原成链表。这种处理方式和索引规律有直接关系，理解了索引规律，迁移逻辑就自然清楚了。
在JDK 7及以前，迁移时每个节点需要重新计算hash，再对新容量取模得到新位置，而且使用头插法，并发扩容时容易形成循环链表。JDK 8之后重构了这套逻辑，不再逐个节点重新计算下标，而是利用旧数组长度是2的幂这个特性，通过看hash的一个比特位来决定节点去哪个新位置。这样一来，迁移效率大幅提升，也消除了头插法导致的死循环风险。
2.2 为什么"拆成两个链表"是核心优化
旧数组扩容时，每个桶里的节点根据hash值在新数组中只有两个去向。假设旧容量oldCap是16，新容量newCap是32，对于某个hash值h，它在旧数组中的索引是h & 15，在新数组中的索引是h & 31。对比这两个式子可以发现，新索引要么等于旧索引，要么等于旧索引加16，也就是加上旧容量。
具体判断方法就是看h的二进制位中，对应旧容量最高位的那一位是0还是1。oldCap等于16，它的二进制是10000，那么要看的位就是bit 4。如果h的第4位是0，则h & 31与h & 15结果相同，节点留在原索引。如果h的第4位是1，则h & 31比h & 15多出16，节点移动到oldIndex + oldCap的位置。
因为这个规律对同一个桶里的所有节点都成立，所以迁移时不需要为了每个节点单独计算取模。只需要遍历旧链表，把所有节点的hash与oldCap做按位与，结果是0的串成一个low链表，结果非0的串成一个high链表，然后把low链表的头节点放到新数组的oldIndex槽位，把high链表的头节点放到新数组的oldIndex + oldCap槽位。这个操作极其轻量，两个链表的节点顺序通过尾插法保持，不会产生JDK 7的链表反转问题。
2.3 树化节点的处理
如果桶里已经是一棵红黑树，迁移逻辑稍微复杂一点。红黑树的节点同时保留了next指针，也就是说它本质上仍然是一条链表，只是额外增加了树结构。迁移时，HashMap会像拆链表一样把树节点按hash位拆成low和high两个链表，这两个链表的长度如果都不超过6，就直接还原成普通链表放回新数组。如果还原后链表长度超过6，HashMap会把它们各自动态调整成一棵新的红黑树，用new TreeNode生成树结构。
这里有个容易混淆的阈值：链表树化的阈值是8，树退化为链表的阈值是6。为什么不是同一个数？因为如果都用8，一个链表长度在7到8之间反复变化时，每次插入删除都可能触发树化和退化，开销极大。用两个不同的阈值制造一个"滞回区间"，可以让结构在树和链表之间切换时不会那么频繁。迁移后的链表长度是否超过6，用的就是这个逻辑。
还有一个细节值得留意：树化条件除了链表长度达到8，还要求数组容量不小于64。如果数组还很小，即使链表达到8，也不会树化，而是优先扩容。原因是容量小时，链表长可能只是巧合的hash集中，扩容后元素会被分散到更多桶里，链表自然就变短了。只有在容量已经足够大、仍然存在长链表时，才说明确实有严重的哈希冲突，需要红黑树来兜底。
3. 2倍扩容的真正原因：位运算、扰动函数与数学原理
3.1 为什么要保证容量是2的幂
HashMap底层用hash & (capacity - 1)来替代hash % capacity取模。这个替换成立的前提，就是capacity必须是2的幂。只有capacity等于2的幂时，capacity - 1的二进制才是低位全1的掩码，按位与才能等价于取模。
举个例子，capacity为16时，capacity - 1等于15，二进制是1111。任何数h与1111按位与，只保留低4位，结果范围是0到15，正好是取模16的结果。如果capacity是17，capacity - 1等于16，二进制是10000，h与16按位与的结果只会是0或16，达不到0到16均匀分布的效果，大量槽位会永远空着，哈希分布完全失效。
所以HashMap在初始化时无论如何都会把数组长度矫正为2的幂，目的不是为了让"取模运算凑合用"，而是为了彻底改变计算索引的方式。用位运算替代除法，能省下不少CPU开销。这在高频put下非常明显，而且索引计算的规律变得极其简单，为第2章那种一次拆分两个链表的二进制迁移奠定了数学基础。
3.2 (n-1)&hash等价于取模的数学推导
不妨用严谨但容易理解的方式来推导。hash对n取模，数学上就是求hash除以n的余数。当n等于2的k次方时，n的二进制表示为1后面跟k个0，n - 1的二进制表示为k个1。一个整数hash与n - 1按位与，等价于把hash右移k位后的高位全部清零，只留下低k位。低k位的数值范围是0到2^k - 1，也就是0到n - 1，这恰好是取模n的所有可能结果。
因为按位与的结果完全取决于hash的低k位，所以如果两个不同对象的hash低k位相同，它们就会落到同一个桶。这就是哈希碰撞的本质来源。HashMap提供了扰动函数来尽量打散高位对低位的干扰，让低k位不至于太过雷同。这里的关键是，不管扰动函数怎么设计，只要n保持2的幂，索引计算就能稳定采用位运算。
3.3 翻倍扩容如何让元素均匀散列
如果扩容时不是翻倍，比如从16扩到24，那么"旧索引加16"这种规律就不成立。节点必须逐个重新取模，迁移成本高不说，更要命的是每个节点无法根据一个二进制位快速分组。而翻倍扩容时，旧容量的二进制是10000，新容量是100000，倒数第二个高位恰好多了一位参与索引计算。这样一来，原来被掩码遮住的第4位，现在也被纳入索引范围，等于多了一个维度来区分不同节点。
这正是"均匀散列"的另一个含义。扩容翻倍后，相当于让hash值多贡献了一个二进制位来决定桶位置。如果hash值本身随机性足够好，那么每个旧桶里的节点大约有一半会留在原索引，另一半会均匀分散到新增的高位索引区。这可以让整体负载重新平均下来，而不是所有元素堆在某个区域。反过来说，如果hash值分布不够随机，比如key的hash总是低k位雷同，那扩容后仍然可能集中在部分桶里，这也是后面要讨论的hash分布劣化问题的根源。
3.4 为什么不是1.5倍或3倍
很多人纠结"为什么必须是2倍"，一个角度是规律性带来的性能收益，另一个角度是空间与时间平衡。如果用1.5倍扩容，容量不满足2的幂，索引计算必须改用取模，迁移时无法用位运算分组，int index = h & (newCap - 1)这个快速公式直接失效，每次都要调用%取模操作。对于一次涉及上百万节点的大扩容来说，这个开销差异非常明显。
如果用3倍甚至更大倍数扩容，数组长度增长过快，会导致大量桶空置，内存浪费严重。而且扩容的次数变少，原本可以通过渐进式调整来分散的成本会集中爆发。HashMap的容量增长路线是16、32、64、128这样缓慢爬坡，每次只翻一倍，既能让索引计算保持位运算，也能保证大多数桶在一段时间内还是有较高的占用率，不会瞬时浪费太多空间。
从数学角度看，2的幂还带着另一个便利：任何2的幂都满足"取模即按位与"的条件，同时旧容量到新容量只增加一个二进制位，这个单比特位的变化使得"旧索引或旧索引加旧容量"的二分类判定成立。这可以说是整套算法的核心支点。如果改了倍数，等于要重写一整条迁移链路，而且性能反而更差。
4. 负载因子0.75的由来与扩容参数权衡
4.1 0.75是怎么来的
负载因子默认0.75是一个工程上的折中值，不是拍脑袋定的。从概率角度看，在随机哈希函数下，桶中元素数量服从泊松分布。通过泊松公式计算，当负载因子为0.75时，桶中链表长度达到8的概率非常低，大约是千万分之六的量级。这个概率意味着，正常情况下不会出现链表长度达到8的情况，树化仅仅是为了防御极端哈希碰撞。
如果把负载因子调大到1，意味着数组允许装满才开始扩容，空间利用率变高了，但碰撞概率同时上升，链表会普遍更长，查询效率下降。如果把负载因子调小到0.5，碰撞概率确实更低，但数组有一半的槽位是空的，内存浪费翻倍。0.75是查询成本和空间成本之间的平衡点，这在工程实践中被广泛验证过，也写进了JDK的注释和源码注释里。
4.2 自定义负载因子与初始容量的坑
实际项目里，很多团队为了"省事"直接new HashMap()，但数据量预估是100万。这样会导致容量从16开始一路扩容，log2(100万/16)大约是16次，每次resize都要搬移几十万甚至上百万节点，这不仅耗时，还可能在并发场景下引发CPU飙升。更好的做法是初始化时直接new HashMap<>(expectedSize / 0.75f + 1)，把expectedSize算进threshold中去。
为什么不能直接new HashMap<>(expectedSize)？因为构造函数里传入的initialCapacity会被tableSizeFor调整成2的幂，然后threshold在第一次put时才被计算为capacity * loadFactor。如果预期放100个元素，直接传100，容量会变128，threshold是96，放进100个元素时刚好会多触发一次扩容。正确做法是传入100 / 0.75 + 1等于134，容量调到256，threshold为192，一次性容纳100个元素还有充分余量。
另外，负载因子虽然可以自定义，但不建议轻率改动。如果把负载因子设成1以上，比如1.0，虽然数组空间利用率达到百分百，但链表长度会普遍偏长，一旦遇到hash冲突集中，查询性能可能急剧下降。把负载因子设成0.5又会让内存近乎翻倍。在绝大多数场景里，保持0.75默认值，通过合理预估初始容量来控制扩容次数，才是最优解。
5. 常见问题与排查技巧实录
5.1 扩容死循环与JDK版本差异
如果还在使用JDK 7或更早版本，并发put导致扩容时可能出现死循环，这是头插法加并发迁移造成的经典问题。多线程同时触发resize时，两个线程可能在同一时刻对同一个链表进行头插迁移，导致链表指针反向连接，最终形成一个环形结构。环形链表一旦形成，之后任何get操作都可能陷入无限循环，CPU直接打满。
JDK 8以降，迁移时采用了尾插法并保留了原有的next链路，同时通过hash位把节点拆成两个链表，没有再破坏链表结构，所以并发扩容不会再产生环形链表。但必须强调，JDK 8的HashMap仍然不是线程安全的容器，并发put可能导致数据覆盖、size统计不准确等问题。如果多个线程同时修改同一个HashMap，没有任何同步措施，结果不可预期。正确做法是使用ConcurrentHashMap，它在底层通过分段锁或CAS配合synchronized来保证并发安全，扩容时也会把桶迁移做成更细粒度的操作。
5.2 扩容导致hash分布劣化
有一种情况非常隐蔽，就是扩容本身可能让哈希分布变得更差。原因是扰动函数对hash的高位做了异或和右移处理，但如果key的hash值本身低16位有规律，比如某些业务ID在低16位总是一样的，那么扩容前和扩容后，这些ID依然会落到固定的几个桶。这时候即使容量翻了倍，新增桶可能长时间闲置，而个别桶却频繁碰撞，形成"扩容了但没完全扩"的假象。
遇到这类问题时，先不要急着调负载因子，而是要检查key对象的hashCode实现。比如一个自定义对象，hashCode返回的是某个固定常数乘以下标的低16位，就会导致这种分布劣化。我曾经在某个日志分析系统里排查过类似问题，最终发现是业务方把UUID截断成了16位作为key，截断后的字符串hash大量落在同一个区间。把key换成完整UUID后，分布立刻恢复均匀。这类问题的定位思路是统计各个桶的节点数，看看是否存在明显偏斜。
5.3 预扩容：避免频繁resize的实践
在实际项目中，如果一个Map在运行前就已经知道大概的数据量，比如从数据库加载一批配置、做一次全量台账初始化，一定要在创建时指定合适的初始容量。这个初始容量要根据负载因子反推，而不是直接填预估条数。举个例子，预估要放10000条数据，直接new HashMap<>(10000)，容量被调整到16384，threshold为12288，存10000条不会触发扩容，这样是够的。但如果预算是11000条，直接传11000后容量调整到16384，threshold还是12288，存到12288时就会触发一次额外的resize，换成11000 / 0.75 + 1等于14667，容量变成32768，threshold为24576，余量就充裕了。
这里还有一个细节，频繁扩容不仅浪费时间迁移节点，还会影响GC。扩容时创建更大的数组意味着原本的Node数组和节点对象成为垃圾对象，如果扩容发生得很频繁，新生代垃圾数量就会暴增，触发更多的Minor GC。在某些高吞吐服务里，这种GC压力甚至会盖过业务本身的资源消耗。所以预扩容不仅仅是优化一次put流程，更是在优化整个JVM的垃圾回收节奏。
5.4 实战排查：结合运行指标判断扩容是否频繁
线上遇到CPU或GC异常时，如果怀疑和HashMap扩容有关，可以通过jstat观察JVM内存中HashMap相关对象的内存变化，也可以直接在看板里监控Map的size增长曲线和容量增长曲线。但更快的办法是在代码里临时给HashMap子类加上一个计数器，重写resize方法，统计resize次数。这种调试手段虽然听起来土，但定位问题非常有效。
有一次我接手一个告警服务，发现某个接口的TP99在发布后缓慢爬升，起初以为是下游变慢，后来在火焰图里看到大量时间耗在HashMap.resize的数组复制上。追查代码发现调用方每次请求都会重新new一个HashMap，而且还根据请求参数动态设置initialCapacity，参数很大时频繁触发扩容。优化方案是先预估最大条目数并一次性初始化，同时把临时Map替换成可复用的对象池。改造后接口P99直接下降了两个数量级。
从经验角度看，resize本身并不慢，慢的是它反复触发、反复迁移大量节点。在业务代码里，如果能严格控制Map的初始容量和生命周期，就可以把resize次数控制在个位数甚至零次。这是最直接有效的性能优化手段，也最能体现对扩容机制的深入理解。
我个人在实际排查问题时的体会是：HashMap扩容机制牵涉的不仅是"数组变两倍"这一个操作，而是一整套围绕2的幂设计的哈希路由体系。理解了桶索引的位运算本质，才能真正明白为什么负载因子取0.75、为什么链表要树化、为什么并发场景得绕开HashMap。最后再分享一个实用习惯：每次新建Map时都先估算数据规模，用expectedSize除以0.75再加1来设置初始容量。这个习惯成本极低，却能在一开始就避免掉绝大多数resize带来的性能损耗。
