老哥们今天想聊聊一个每次面试都会被问、但很多人其实只答对一半的问题HashMap底层为什么要用2倍扩容我见过太多人张口就答“为了避免hash碰撞”再追问一句“为什么是2倍而不是1.5倍或者3倍”就卡住了。实际上2倍扩容不是拍脑袋定的数字它牵扯到哈希桶下标计算的性能、数据迁移的成本、甚至并发环境下的安全问题。这篇文章会从put方法走到resize把扩容的触发条件、迁移过程、位运算原理拆开讲一遍顺便分享几个日常开发里避免频繁扩容的小技巧。1. 先从HashMap的基本结构说起数组链表红黑树1.1 哈希桶的设计与数据分布逻辑HashMap底层是一个“数组加链表”的结构如果你用的是JDK 8及以后的版本还要加上红黑树。平时大家说的“哈希桶”就是那个数组数组的每个元素叫桶桶里面可以放一个节点也可以挂一串链表或者一棵红黑树。为什么这么设计因为数组的随机访问快下标定到哪就能直接拿到哪的数据时间复杂度是O(1)。但数组的缺点是长度固定没法动态变小变大。哈希函数把任意key映射成一个int但这个int可能很大总不能拿它直接当数组下标所以需要“压缩”到数组长度范围内。压缩之后不同的key可能落到同一个桶里这就叫哈希碰撞。解决碰撞最简单的办法就是在桶里挂链表新来的冲突节点追加到链表尾部查询的时候遍历链表逐个比较。这里有个关键点链表查询的时间复杂度是O(n)如果大量key都撞到同一个桶里HashMap就退化成链表效率会很难看。所以JDK 8做了一个优化当链表长度超过阈值默认8并且HashMap的容量达到64时链表会转换成红黑树。红黑树的查询复杂度是O(log n)在极端碰撞情况下能把性能兜住。你可能会问为什么一个哈希表要搞得这么复杂直接按需扩容不就行了。扩容当然要做但扩容不是免费的每次扩容都要创建新数组把旧数据全部搬过去如果容量设计得不好扩容次数就会很多性能一样拉胯。所以HashMap在“数组链表红黑树”这个结构之上又加了一套容量增长策略也就是我们常说的加载因子和阈值。1.2 加载因子0.75和阈值公式HashMap有一个默认的加载因子值是0.75。这个数字不是随便写的它是时间和空间的一个折中。加载因子乘上当前容量得到的就是扩容阈值threshold。举个例子默认容量是16那么阈值为16 * 0.75 12。也就是说当HashMap里存的键值对数量超过12个时下一次put就会触发扩容。为什么是0.75而不是1如果加载因子是1意味着数组全部填满才扩容。好处是空间利用率高但坏处是哈希碰撞概率大幅上升链表会变得很长查询效率明显下降。如果加载因子是0.5碰撞概率低了但空间浪费严重桶没填满一半就开始扩容内存消耗变大。0.75这种接近0.75的比例在大多数场景下可以让哈希表的期望长度和碰撞概率都保持在一个不错的水准。用数学一点的话说在加载因子为0.75且哈希函数足够均匀的情况下桶中元素的个数服从泊松分布链表长度达到8的概率已经极小所以JDK用8作为链表转红黑树的阈值同时配合0.75的加载因子。日常开发中除非有特殊场景否则不建议修改加载因子。你把加载因子调大能用更少的内存换更慢的读写调小则是用更多内存换更快的读写。默认值适合绝大多数业务场景。2. 扩容机制的核心流程什么时候触发、怎么做2.1 put方法中的扩容判断与触发时机扩容这件事入口就在put方法里。每次你会往HashMap塞一个键值对方法内部会先计算key的hash值然后定位到具体的桶再进行插入或覆盖。但真正插入之前它得看一眼当前元素个数有没有达到阈值。我简化一下逻辑大致是这样的先判断table是否为空如果是就执行resize()初始化然后根据hash算下标如果那个下标位置是空的直接放一个新的Node。如果已经有数据了就检查key是否相同相同就覆盖value不同就往链表或红黑树里插入。等插入动作完成后会执行关键判断if (size threshold) resize();。这里的size是当前键值对的数量不是数组已经被占用的桶数。很多人把size误解成桶数量其实不对。比如你往同一个桶里挂了20个节点size是20但桶占用可能只有几个。HashMap扩容看的是整体键值对数量不是桶占用率。这个判断还有个细节如果你创建HashMap时指定了初始容量会在构造阶段提前计算好新阈值第一次put时不再走默认的初始化逻辑而是直接用你指定的容量创建数组。如果初始容量不是2的幂HashMap还会向上取整到最近的2的幂。所以你在代码里写new HashMap(19)实际容量会变成32。为什么要这么干后面会详细讲。触发扩容后resize()会做两件事一是把容量扩大到原来的2倍并重新计算阈值二是把旧数组里的所有数据重新哈希到新数组里。注意这里的“重新哈希”并不是重新计算每个key的hash值因为hash值只跟key有关和容量没关系。真正变化的是“数组下标”也就是元素在新数组中应该放到哪个桶。2.2 resize的完整流程从建新数组到数据搬家我们先理清楚resize的宏观流程。resize方法内部会先根据旧容量算新容量比如旧容量是16新容量就是32。然后更新阈值比如旧阈值12新阈值24。接着创建新数组长度为32。到这里旧数组里的数据还没有搬。数据搬家是resize的核心。它会遍历旧数组的每一个桶如果桶是空的跳过如果桶里只有一个节点直接把这个节点重新哈希到新数组如果桶里挂着链表需要把链表拆分成两个子链表分别放到新数组的不同位置如果桶里是一棵红黑树需要把红黑树拆分成两个子树并且判断拆分后的节点数是否小于等于6如果足够少还要把红黑树退化成链表。这里最绕的就是“链表拆分”。很多人以为扩容时要逐个节点重新算下标其实不是。JDK 8用了非常巧妙的位运算技巧把一个链表一分为二一个留在“原下标”位置一个挪到“原下标旧容量”的位置。为什么能这么做这是2的幂扩容最大的红利。等讲到2倍扩容的原因时我会把具体的拆分原理和代码都展开这里先让你有个直觉。搬完数据之后HashMap会把新数组赋值给内部的table字段resize就结束了。整个过程的时间复杂度是O(n)因为每个旧节点都要遍历一遍。虽然扩容本身是单次开销较高的操作但HashMap采用的是“均摊”思路把扩容成本摊到多次put上整体性能依然能接受。不过这也提醒我们如果能预估数据量最好提前指定容量让HashMap少扩容几次。3. 为什么是2倍位运算、迁移低成本和均匀分布3.1 2的幂让下标计算从取模变成位与要理解为什么扩容是2倍核心在于HashMap计算桶下标的方式。源码里其实没有直接写hash % capacity而是写成了(n - 1) hash其中n是数组长度也就是容量。这个表达式等价于hash % n但前提是n必须是2的幂。为什么因为当n2^k时n-1的二进制是低位全1比如16-115二进制是1111。hash与1111做位与运算结果就是hash的低4位这个结果正好是0到15之间的数等价于hash对16取模。但位与运算比取模快得多CPU只需要一个与指令就能搞定。HashMap作为高频使用的数据结构每次put和get都要算下标用位与代替取模能省下不少时间。如果容量不是2的幂比如17那么n-116二进制是10000hash与16做位与结果只能是0或者16下标分布会灾难性地集中。所以HashMap在初始化时要把容量调整到2的幂扩容时也要保持2的幂。那扩容倍数自然是2这样新容量始终是2的幂。你也可以选择扩容到原来的4倍、8倍但那样空间浪费太大而且迁移成本会成倍增加。2倍是在性能和空间之间找到的一个合理平衡点。3.2 2倍扩容下链表拆分的高低位规律如果扩容倍数不是2数据迁移时就只能对每个节点重新计算下标成本很高。但因为是2倍扩容迁移变得极其高效而且还能把链表拆成两半不再需要逐个重算。我们看具体例子。假设旧容量是16桶下标计算公式是(16-1) hash也就是hash 1111结果依赖hash的低4位。扩容后容量变成32新下标是(32-1) hash也就是hash 11111结果依赖hash的低5位。那么新旧下标之间有什么关系旧下标取hash的末4位新下标取hash的末5位。新下标其实就是“末4位”加上“第5位是0还是1”额外贡献的值。如果hash的第5位是0那么新下标低5位的结果和低4位结果一样也就是下标不变如果第5位是1那么新下标等于旧下标加16也就是加旧容量。这个“第5位”在代码里等价于hash oldCap因为oldCap16二进制是10000只有hash第5位为1时这个表达式才不为0。所以JDK 8的源码里用(e.hash oldCap) 0来区分节点去留为0的留在原索引位置不为0的移动到“原索引oldCap”的位置。不需要重新计算hash也不用做取模一次位与就完成了分类。为了更直观我列一个实际数据对照。旧容量16假设有4个keyhash值分别是5、21、37、53。旧下标就是低4位key的hash二进制至少看5位旧下标 hash15高一位第5位新下标 hash31是否16500101505否21101015121是37100101取低5位101015121是531101015121是注意37和53如果只看低5位和21一样都是10101所以它们新下标都是21。在这个例子里原本都在下标5的链表扩容后被拆成了“5”和“21”两条链。JDK 8扩容时就是按照这个规律把原链表拆成两个链表然后一次性挂到新数组对应的桶上。整个过程用一个循环就能完成高效且优雅。这也是为什么扩容倍数是2最关键的原因只有容量保持2的幂下标计算才能用位与只有扩容翻倍数据迁移才能利用“二进制高位进位”的规律实现无重哈希的链表拆分。如果哪天你看到有人把HashMap的扩容倍数改成3那哈希表的性能就崩了。3.3 扰动函数配合2倍幂保证分布均匀光有2的幂还不够hash值的质量也影响分布。String等对象的hashCode是有规律可循的直接拿来用可能低比特位分布很差。比如两个key的hash分别是16和0如果直接用16作为下标计算依据它们都会被算到下标0冲突严重。所以HashMap在取hash的时候会做一个扰动(h key.hashCode()) ^ (h 16)把高16位异或到低16位。这样低比特位里也混入了高位的特征再和(n-1)做位与时分布会更均匀。源码里的hash方法就叫这个。扰动的作用在容量较小时尤其明显因为当n是16时只有低4位参与下标计算高位的差异全部被丢掉了加了扰动之后高位的随机性被注入到低位让低位的分布更接近均匀随机。配合2倍扩容扰动过的hash在扩容前后依然保持稳定。因为扰动只是对hash本身做位运算不涉及容量。扩容后新下标依赖的比特位数多了一位这一位的值同样来自hash的高位特征所以整个跳变是自然且平滑的。如果容量不是2的幂每次扩容都要改变参与位与的比特位长度hash的分布特性会被彻底打乱那样就不得不对每个节点重新计算完整哈希成本会高得多。4. 扩容的代价与避坑性能损耗和并发隐患4.1 并发扩容曾导致的死循环问题HashMap本来就不是线程安全的但早期版本在并发put时扩容会导致一个著名的死循环问题。JDK 7及之前链表插入用的是头插法也就是说新节点总是插在链表头部。当两个线程同时触发resize它们在迁移链表时可能会把节点的next指针指向一个环之后在这个桶上做get操作就会陷入无限循环CPU直接飙高。具体过程我就不逐行分析了你只需要记住头插法会改变链表顺序多线程并发迁移时容易互相覆盖产生环形引用。JDK 8把链表插入方式改成尾插法新节点加到链表末尾扩容时保持元素顺序不变从数据层面上减少了环的产生概率。但你不要因此就觉得JDK 8的HashMap在并发下是安全的它只是不容易死循环了数据丢失、脏读、覆盖照样会发生。如果你的业务里同一个HashMap会被多个线程同时读写千万别抱侥幸心理。要么在外部加锁要么直接用ConcurrentHashMap。面试时如果对方问“HashMap扩容死循环”你要能说出来这是JDK 7头插法导致的并且知道JDK 8改成了尾插法但线程安全依旧不能依靠HashMap。4.2 频繁扩容的性能损耗与容量预估方法除了并发问题扩容还有实打实的性能开销。第一次扩容要新建数组第二次扩容要把原来的数据都搬一遍如果数据量很大迁移过程会产生大量内存分配和引用赋值GC压力也会增加。在流量高峰期一次意外扩容可能让接口响应时间翻好几倍。怎么避免最直接的办法是创建HashMap时估算好容量。假设你预计要放1000个键值对那么初始容量应该设为多少有人会直接写new HashMap(1000)但如果你看了前面的加载因子就明白了容量1000时阈值是1000 * 0.75 750放1000个数据一定会触发扩容。按照避免扩容的公式初始容量最好大于等于“实际元素数量 / 加载因子”。对于1000个元素1000 / 0.75 1 ≈ 1334而你传进去的容量会被调整到2的幂所以最好是new HashMap(1024)不对1024的阈值是768还是不够。需要传2048吗其实这里有个更稳妥的算法先算expectedSize / 0.75f 1再向上取2的幂。1000除以0.75约等于1333向上取2的幂是2048。所以直接new HashMap(2048)最稳。保守一点也可以用new HashMap(1000 / 0.75 1)结果等于1334HashMap会找到下一个2的幂2048是一样的效果。如果你清楚数据量峰值提前预留20%甚至50%的余量是合理的。但也不要无脑设一个超大值比如明明只会放几十条数据你非要初始化成65536白白浪费内存。HashMap的数组长度太大而实际数据很少遍历的时候还是要走完整个数组长度其实遍历只会走有数据的桶和链表不会空遍历没有桶实际上for循环还是会扫描table数组只是跳过空桶当数组很大而数据很少时遍历成本依然不小因为要挨个检查数组元素是否为null。5. 源码拆解JDK 8的resize()是怎么写的5.1 容量和阈值的计算分支如果你翻过JDK 8的源码resize方法其实不算长但好几层if嵌套容易看晕。我挑关键逻辑出来讲。这一段是计算新容量和新阈值final NodeK,V[] resize() { NodeK,V[] oldTab table; int oldCap (oldTab null) ? 0 : oldTab.length; int oldThr threshold; int newCap, newThr 0; if (oldCap 0) { if (oldCap MAXIMUM_CAPACITY) { threshold Integer.MAX_VALUE; return oldTab; } else if ((newCap oldCap 1) MAXIMUM_CAPACITY oldCap DEFAULT_INITIAL_CAPACITY) newThr oldThr 1; } else if (oldThr 0) { newCap oldThr; } else { newCap DEFAULT_INITIAL_CAPACITY; newThr (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); } // ... 后面还有赋值和建表 }这里重点看几个分支。第一个分支是“旧容量大于0”说明这是普通扩容新容量等于旧容量左移一位也就是乘以2。newThr直接是旧阈值左移一位也乘2。如果旧容量已经到了最大值MAXIMUM_CAPACITY就不再扩容把阈值改成Integer.MAX_VALUE等于告诉HashMap“你别再扩了容量到顶了”。第二个分支是“旧容量为0但旧阈值大于0”出现在你通过构造函数指定了初始容量和加载因子时。构造阶段会把容量调整成2的幂并计算出threshold然后传给resize。所以这里newCap就用oldThr而不是默认16。理解这一点很重要不然你会纳闷为什么resize里会出现threshold当容量的操作。第三个分支是“初始化默认表”用默认容量16和默认阈值12。这三个分支覆盖了HashMap从创建到扩容的所有入口。5.2 链表迁移中的高低位拆分实现建好新数组后迁移数据的代码才是核心。截取链表迁移的关键片段if (e.next null) { newTab[e.hash (newCap - 1)] e; } else if (e instanceof TreeNode) { // 红黑树单独处理 } else { 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 { if (hiTail null) hiHead e; else hiTail.next e; hiTail e; } e next; } while (e ! null); if (loTail ! null) { loTail.next null; newTab[j] loHead; } if (hiTail ! null) { hiTail.next null; newTab[j oldCap] hiHead; } }这段代码就是在做链表拆分。它维护了两个链表loHead/loTail表示“低位链表”也就是hash oldCap等于0的节点它们的新下标不变仍在jhiHead/hiTail表示“高位链表”它们的新下标是j oldCap。迁移时遍历原链表用位与区分每个节点进哪条链最后分别挂到新数组对应的桶上。注意到一个特别重要的细节在拆分链表的循环里它对每个节点只取event.hash oldCap没有重新计算整个下标。这块的性能优势就是2倍扩容带来的。如果旧容量不是2的幂oldCap的二进制不只有一个1那么(e.hash oldCap)的语义就不再是“第n位是否为1”就没法这样高效拆分了。另外这里一定要记得在链尾设置next为null。因为同一个链表里的节点在新数组中可能被分到不同桶如果尾节点的next还指向旧链里的下一个节点新链表就可能会串到别人家里。JDK 8在迁移时显式loTail.next null;和hiTail.next null;就是为了斩断跟旧链的关系。我看过一些修改过的HashMap实现把这段删了或者漏了结果数据迁移后链表出现非预期链接查询逻辑直接乱掉。5.3 红黑树在扩容时的split逻辑如果桶里放的是红黑树迁移逻辑就更复杂一点。JDK 8在TreeNode内部提供了一个split方法专门负责红黑树扩容。它的核心做法和链表很像遍历树上的所有节点也是用e.hash oldCap把节点分成“低位”和“高位”两条链。但是树节点不仅有next指针还有left、right、parent这些指针所以不能像普通链表那样直接拼。split方法会把挂在同一个下标下的TreeNode串成一个双向链表然后再根据链表长度决定是保持红黑树还是退化成普通链表。具体规则是如果拆分后的某个链表长度小于等于6就把TreeNode链表转成普通Node链表如果大于6则继续用红黑树结构。为什么阈值是6而不是8因为6和8之间留了缓冲避免在扩容临界点附近反复横跳。比如一个桶刚转成树下一秒扩容拆分了节点数变成7如果7也要转回链表下一次put又到8又要转树那性能抖动会很严重。阈值设成6相当于给了一个滞后判断让结构不至于频繁切换。红黑树split的代码量不小日常排查问题很少会直接跑到这一层但如果你遇到了HashMap在某个桶访问特别慢可以怀疑一下是不是树化阈值和扩容阈值没有配合好。不过大多数业务并不需要手动干预只要容量和加载因子合理红黑树很少会登场。6. 日常开发中怎么利用好扩容机制6.1 初始化容量估算公式与实操示例知道了扩容机制日常开发里最大的应用场景就是创建Map时估算容量。我习惯用一个工具方法来计算public static K, V HashMapK, V newHashMapWithExpectedSize(int expectedSize) { int capacity (int) (expectedSize / 0.75f 1.0f); return new HashMap(capacity); }这段逻辑和许多工具类里Maps.newHashMapWithExpectedSize的思路一致。它的核心是保证计算出的容量在HashMap内部调整成2的幂之后依然大于expectedSize / 0.75这样插入expectedSize个元素时不会触发扩容。举个例子从数据库查出一万条记录要转成HashMap缓存。直接new HashMap()它会在插入到第13个元素时第一次扩容第25个时第二次然后第49、97……一直扩到足够大。一万条数据大概会触发十几次扩容每次都要把已有数据搬一遍白白的性能损耗。换成new HashMap(10000 / 0.75 1)实际计算值是13334HashMap向上调整为16384足够了。这样全程只需要一次数组分配后面的put都是纯写入速度快不少。这里有个小坑如果你传入的容量是10000而不是10000/0.751那么HashMap容量会被调整为16384吗不会因为10000本身不是2的幂HashMap会向上取整到16384刚好满足。那是不是直接传10000也行表面上也能避免扩容但如果你传入的容量恰好是2的幂比如8192阈值就是8192*0.756144你要放一万条数据必然发生扩容。所以不要只看容量大小要看调整后容量乘以加载因子后是否大于预期元素数。最稳的还是用那个加1的公式。6.2 并发场景的正确姿势别让HashMap背锅扩容的线程安全风险我在前文提过这里再给个明确建议多线程共用Map直接用ConcurrentHashMap别用HashMap加synchronized包一层。ConcurrentHashMap在JDK 8里也用类似的分段思路但粒度细到单个桶并发性能远好于全局锁。它的扩容机制也做了很多优化比如多线程协助迁移大map扩容时多个线程各搬一段速度更快。如果只是读多写少还可以考虑用不可变Map或者各种缓存框架比如Caffeine、Guava Cache它们底层对容量和淘汰策略的优化更贴近业务。你自己实现一个带过期时间的Map很容易因为扩容和清除过期数据的时机没有协调好导致内存暴涨。说到这我想起一个线上事故。某服务启动时加载配置初始化了一个默认HashMap后来配置项从几百涨到几百万每次更新配置都要扩容迁移更新一次卡一次。后来改成按配置最大预估容量初始化并且用ConcurrentHashMap承载并发读写启动加载时间直接从三秒降到几百毫秒。扩容不是洪水猛兽但你要知道它在什么情况下发生以及怎么让它少发生。另一个容易被忽略的点是如果你用HashMap做缓存并频繁淘汰过期数据size会不断增减。扩容触发的判断是size超过threshold但如果删数据把size降下来了它不会自动缩容。HashMap不会在size变小的时候把数组缩小它只会越扩越大除非你重新创建一个新的HashMap。所以长生命周期的大HashMap如果数据量剧烈波动内存会被撑住。对这种场景要么定期重建Map要么用自带缩容能力的缓存结构。最后说点我的个人感受。带过不少新人也面试过不少候选人我发现真正理解HashMap扩容的人不在于能背出resize的源码而是能解释清楚2倍这个数字背后那串位运算逻辑。如果你自己动手写个小demo对比一下容量在2的幂和非2的幂时的迁移路径你会对哈希表的理解上一个台阶。下次再有人问你2倍扩容希望你能说出“因为容量是2的幂所以下标等于hash与容量减一扩容后数据要么留在原下标要么加上旧容量”顺便再补一句“0.75的加载因子是时间和空间的平衡”。能说到这个层次基本就过关了。