面试十次有九次会问到 HashMap 的扩容机制可大多数回答都停在当元素个数超过阈值就翻倍然后重新 hash这一层。真往深了问——负载因子为什么是 0.75为什么容量必须保持 2 的幂JDK8 扩容迁移数据时到底怎么做到不重新计算 hash 的并发下扩容为什么会死循环能答上来的人就没那么多了。这篇文章想把 HashMap 扩容机制从头到尾串起来讲一遍。目标读者有三类准备面试想拿源码细节加分的人、工作中要排查 HashMap 引发的性能或线程安全问题的开发、以及想彻底搞明白集合底层逻辑的初学者。内容基于 JDK8 及之前版本的 HashMap 实现JDK8 是当前主力版本和 JDK7 的差异我会单独标出来。1. 扩容的触发时机0.75 这个数字不是拍脑袋定的1.1 阈值公式与两个容易被忽视的边界HashMap 内部有两个核心字段tableNode 数组和threshold扩容阈值。扩容的唯一触发条件是table 中已有的元素个数超过 threshold也就是size threshold这时就会调用resize()。threshold的计算公式很简单threshold capacity * loadFactor默认构造下初始容量 capacity 是 16负载因子 loadFactor 是 0.75所以第一次扩容的阈值就是 16 * 0.75 12。也就是说你往 HashMap 里插入第 13 个键值对的时候就会触发扩容table 从 16 变成 32。这里有两个边界情况经常被忽略。第一个是容量上限当oldCap (1 30)时HashMap 不再扩容直接把 threshold 设为Integer.MAX_VALUE防止溢出。第二个是自定义初始容量时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; }打个比方你new HashMap(7)实际容量不是 7而是 8new HashMap(9)实际容量也不是 9而是 16。这个机制很多面试题会拐弯问如果答不上来就前功尽弃了。还有一点要注意JDK7 和 JDK8 的扩容触发时机有个细微差别。JDK7 是先判断size threshold再插入新元素也就是扩容之后才 putJDK8 是先完成插入然后size threshold时才扩容。虽然最终效果都是超过阈值后触发但赋值顺序和 resize 调用点不一样偶尔会在线上日志里看到差异。1.2 负载因子为什么是 0.75而不是 0.5 或 1.0负载因子的本质是空间换时间的调节旋钮。如果你把负载因子调成 1.0意味着 table 塞满了才扩容桶内的链表会越来越长get 操作的耗时从 O(1) 退化成 O(n)因为每次都要遍历一条很长的链表。如果你把负载因子调成 0.5链表会很短、查询很快但数组有一半空间是空的内存浪费严重。0.75 是 JDK 作者在时间和空间之间取的折中值。源码注释里有一段很有名的推导在随机 hashCode 下桶内元素个数服从泊松分布参数约为 0.5对应负载因子 0.75 的场景此时桶内链表长度达到 8 的概率低于千万分之一。这就是为什么 TREEIFY_THRESHOLD链表转红黑树的阈值定成 8——正常情况下链表根本长不到 8一旦出现说明要么哈希函数太烂要么有人在恶意构造数据这时候用红黑树把最坏情况从 O(n) 改善到 O(log n) 是值得的。同时树退化回链表的阈值是 6中间留下 7 这个缓冲区间避免元素在链表和树之间反复横跳造成不必要的性能损耗。1.3 为什么容量必须是 2 的幂容量保持 2 的幂是 HashMap 一系列操作的基石。最大的原因在定位下标这一步正常情况下hash % capacity是取模运算但取模在 CPU 指令层面比位运算贵得多HashMap 直接用位运算替代i (n - 1) hash当 n 是 2 的幂时(n - 1) hash等价于hash % n因为n - 1的二进制恰好是低位全 1与运算就相当于截取 hash 的低 log2(n) 位也就是余数。这个设计还带来一个连锁优势扩容后元素的新下标不需要重新计算。因为容量从 oldCap 变成oldCap 1多出来的只有最高位那一个 bit。只要看(e.hash oldCap)的结果为 0 就留在原下标为 1 就去原下标 oldCap。这在下一章细讲。2. resize 扩容的完整执行链路新数组创建、数据迁移与链表拆分2.1 JDK8 的 resize 源码拆解resize()是 HashMap 里最核心也是最复杂的方法之一。我把 JDK8 主干逻辑简化一下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; } newCap oldCap 1; if (newCap MAXIMUM_CAPACITY oldCap DEFAULT_INITIAL_CAPACITY) newThr oldThr 1; } // 省略 oldThr0 / new HashMap 等初始化分支 // 第二步创建新数组 NodeK,V[] newTab (NodeK,V[])new Node[newCap]; table newTab; // 第三步迁移旧数据 if (oldTab ! null) { for (int j 0; j oldCap; j) { NodeK,V e; if ((e oldTab[j]) ! null) { oldTab[j] null; if (e.next null) newTab[e.hash (newCap - 1)] e; else if (e instanceof TreeNode) ((TreeNodeK,V)e).split(this, newTab, j, oldCap); else { // 链表迁移见 2.2 } } } } return newTab; }整体分三步走计算新容量和新阈值、创建新数组、遍历旧数组迁移数据。迁移时又分了三种情况桶里只有一个节点、桶里是红黑树、桶里是链表。这三种情况的处理方式完全不同是扩容机制的细节核心。2.2 一条位运算规则决定元素去往新数组的哪个位置链表迁移的代码我单独拎出来讲JDK8 用了 lo 和 hi 两条链来拆分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; }看懂这段代码的关键是理解(e.hash oldCap)的含义。举个例子假设扩容前容量是 16hash 是 4二进制...0000100和 hash 是 20二进制...0010100。扩容前(16-1) hash的结果都是 4所以这两个元素挤在同一个桶里形成链表。扩容到 32 之后重新计算下标时用(32-1) hashhash 431 4 4还在原来的下标 4。hash 2031 20 20下标变成了原来的 4 16 20。差异在哪就在于 hash 从低到高的第 5 位对应 oldCap16 的那一位。(e.hash 16)为 0 的是 hash 4结果留在原位为 1 的是 hash 20结果移动 oldCap。所以 JDK8 只需要用一次位运算就能确定整条链表里每个节点该去哪边根本不用重新计算 hash也不需要取模。还有一个细节值得注意JDK8 的迁移保持了链表元素的相对顺序。lo 链按原顺序接好hi 链也按原顺序接好最后分别挂到新数组上。而 JDK7 迁移时用的是头插法每遍历一个节点就插到新桶头部所以 JDK7 扩容后链表顺序会反转。这个顺序上的差异直接影响第四章要讲的并发死循环问题。2.3 红黑树桶在扩容时怎么拆当桶里的元素已经树化成红黑树时迁移逻辑走的是split方法。它的思路和链表迁移本质上是一样的遍历整棵红黑树的所有节点用(e.hash oldCap)分成低位链 lo 和高位链 hi同时统计两条链的节点数量lc和hc。拆分完之后的处理规则是如果某条链的节点数小于等于 6也就是UNTREEIFY_THRESHOLD就把这条链从 TreeNode 退化成普通 Node 链表因为节点太少红黑树的旋转和变色成本反而高于线性遍历如果两条链的数量都超过 6就用 TreeNode 重新组织成红黑树挂到新桶上。这个树退链表的阈值和第一章提到的 8 树化阈值之间隔着 7就是防止元素在两种数据结构之间频繁切换。我在自测红黑树拆分逻辑时最常犯的错误是以为红黑树整体迁移、整体复制——不是的它是拆成两条 Node 链之后各自判断去留理解了这一点split方法就没秘密了。3. put/get 全流程中 equals 的关键地位hash 碰撞之后靠它一锤定音3.1 put 一个 key 时要过四道关卡很多新人对什么情况下会调用 equals这个问题一脸懵。我们完整走一遍 put 流程就能说清楚 equals 到底在哪里、什么时候、为什么出场。第一步是计算 hashJDK8 用了扰动函数static final int hash(Object key) { int h; return (key null) ? 0 : (h key.hashCode()) ^ (h 16); }hashCode()返回的 int 是 32 位的而 table 容量通常远小于 2 的 32 次方定位下标时只用得到低位。如果两个 hashCode 的高位不同、低位相同直接(n-1) hash就会撞到同一个桶。扰动函数把高 16 位异或到低 16 位让高位信息也参与下标计算降低碰撞概率。第二步是定位桶下标i (n - 1) hash。这里拿到的是桶在数组中的位置但桶里可能已经有别的元素了。第三步是检查桶里是否已经有同一个 key。判断逻辑是if (p.hash hash ((k p.key) key || (key ! null key.equals(k))))这里有个优先级先比 hashhash 相同再看引用是否同一个对象引用不同才动用equals。很多人的误区在于以为 HashMap 只用 hash 判断 key 是否相等——不是的hash 相等只是充分必要条件之一最终判断权在 equals。第四步分三种情况如果桶是空的直接newNode放入如果桶首节点就是要覆盖的 key直接覆盖 value否则就遍历链表或红黑树逐个节点用同样的p.hash hash (k p.key || key.equals(k))去判断找到了就覆盖找不到就尾部插入新节点。链表长度超过 8 时会走treeifyBin但如果整个 table 长度还不到 64会先 resize 而不是树化因为这时树化收益不大把数组扩一倍更划算。3.2 get 的查找逻辑hashCode 决定去哪个桶equals 决定是不是它get 的流程是 put 的逆过程核心是getNodefinal NodeK,V getNode(int hash, Object key) { NodeK,V[] tab; NodeK,V first, e; int n; K k; if ((tab table) ! null (n tab.length) 0 (first tab[(n - 1) hash]) ! null) { // 先检查桶首节点 if (first.hash hash ((k first.key) key || (key ! null key.equals(k)))) return first; // 桶里还有后续节点 if ((e first.next) ! null) { if (first instanceof TreeNode) return ((TreeNodeK,V)first).getTreeNode(hash, key); do { if (e.hash hash ((k e.key) key || (key ! null key.equals(k)))) return e; } while ((e e.next) ! null); } } return null; }可以看到整个查找过程是三层漏斗先通过 hash 定位到唯一一个桶然后在桶内先用 hash 快速过滤最后用equals精准匹配。正因为这样HashMap 对 equals 和 hashCode 有一个硬性约定equals 相等的两个对象hashCode 必须相等。如果违反了这条约定就会出现同一个 key 能 get 到两个不同的 value、放入两次产生两个条目的诡异问题。说实话这个约定属于 Java 基本功但在实际项目里踩坑的大有人在。最典型的场景是拿自定义对象做 key只重写 equals 不重写 hashCode。比如用一个User对象做 keyequals比较的是 id但 hashCode 还是默认的Object.hashCode()基于内存地址两个 id 相同的 User 对象 hash 不同HashMap 会把它们当成两个 key缓存命中率直接崩盘。排查这种问题最好的方式就是打断点看hash()方法返回值。4. 并发扩容为什么是 HashMap 噩梦的源头死循环与丢数据的完整推演4.1 JDK7 头插法在并发扩容下如何把链表变成环这是 Java 历史上最有名的并发故障之一两个线程同时对 HashMap 做 resize最终导致链表成环任何一次 get 都可能让 CPU 飙到 100%。核心元凶就是前面说的头插法 并发迁移。我用一个自洽的推演还原现场。假设某个桶里有一条链表A - B - null线程 T1 和线程 T2 同时进入 transfer 逻辑。JDK7 的迁移循环大致长这样do { EntryK,V next e.next; // ① 先保存下一个节点 e.next newTable[i]; // ② 当前节点指向新桶头部 newTable[i] e; // ③ 当前节点成为新桶头 e next; // ④ 移动到下一个节点 } while (e ! null);T1 执行到第 ① 步时它手里保存的是e A、next B然后被操作系统调度挂起。它还没有修改任何链表结构。T2 在这期间把整条链表完整迁移了。因为头插法迁移到新桶后链表顺序反转为B - A - null此时新桶的头节点是 BB 的 next 指向 AA 的 next 指向 null。现在 T1 恢复执行它对内存的最新感知是新桶头部是 B但自己本地变量还握着一份旧的e A、next B。它继续执行第 ② 步A.next newTable[i]也就是A.next B。第 ③ 步newTable[i] AA 成为新桶头部。问题来了此刻新桶里的链是A - B - ...而 B.next 在 T2 迁移后已经指向 A。于是从新桶头部出发遍历A 指向 BB 指向 A环形链表诞生。之后任何 get 操作一旦索引到这个桶就会在循环里转不出来伴随着 CPU 被打满JVM 直接假死。4.2 JDK8 的尾插法为何仍不安全JDK8 把迁移改成尾插法并且保持了链表相对顺序所以不会再出现环形链表这是很多人误以为JDK8 的 HashMap 并发安全了的原因。但事实远没那么乐观。并发扩容时两个线程可能同时执行resize操作同一个桶的同一个节点链表。它们各自维护自己的 lo/hi 两条链迁移过程中会同时修改节点的next指针。因为在没有任何同步的前提下两个线程对同一内存地址的写入互相覆盖最终某些节点的next可能被置空或指向错误位置节点从链表中丢失。表现出来就是数据静默丢失并发写入 1000 个 key程序不报错但 size 可能只有 900且后续 get 某些 key 返回 null。除此之外JDK8 的put还存在size非原子的问题。两个线程同时执行size实际可能只 1导致 size 与真实元素数不符。迭代 HashMap 时还会触发 fail-fast 机制抛出ConcurrentModificationException因为modCount的修改同样不是线程安全的。所以准确的说法是JDK8 解决了并发扩容下 CPU 100% 的死循环问题但没有解决并发读写下的数据丢失、size 错乱和迭代失败问题。HashMap 从头到尾就没承诺过线程安全这话不是开玩笑的。4.3 线上如何发现与规避扩容引起的并发问题在线上有比较明显的特征某个线程长期 RUNNABLE 且 CPU 占用高线程 dump 里栈顶停在HashMap.getNode或HashMap.put附近。JDK7 时代还经常出现一次扩容之后集群里好几台机器同时 CPU 飙升的事故。规避方案按优先级排序直接用 ConcurrentHashMap。它把整个 table 分成多个 segmentJDK7或用 CAS synchronized 锁单个桶JDK8扩容时也做了特殊的并发迁移处理是并发场景下的正解。初始化时预估容量减少扩容次数。既然扩容是事故高发点那就少扩容、不扩容。具体做法下一章给公式。如果只是读多写少也可以用Collections.synchronizedMap(new HashMap(...))包裹一层但并发写多时性能不如 ConcurrentHashMap因为它是全表锁。我的个人建议是但凡有第二个线程可能访问同一个 HashMap就直接上 ConcurrentHashMap别纠结。HashMap 的并发坑属于不在现场看不出来、一到现场就是事故的类型不值得用生产事故换经验。5. 对比 ArrayList 的扩容策略翻倍和 1.5 倍背后的设计取舍5.1 ArrayList 扩容机制速览ArrayList 的扩容机制和 HashMap 完全不是一个思路但两者经常被拿来对比。ArrayList 内部是 Object 数组默认空构造时数组是空数组第一次 add 才会扩容到默认容量 10。之后每次容量不够时调growprivate void grow(int minCapacity) { int oldCapacity elementData.length; int newCapacity oldCapacity (oldCapacity 1); // 1.5 倍 if (newCapacity - minCapacity 0) newCapacity minCapacity; if (newCapacity - MAX_ARRAY_SIZE 0) newCapacity hugeCapacity(minCapacity); elementData Arrays.copyOf(elementData, newCapacity); }oldCapacity (oldCapacity 1)就是1.5 * oldCapacity。扩容时调用Arrays.copyOf本质上是System.arraycopy把老数组整体拷贝到新数组。5.2 为什么 ArrayList 选 1.5 倍HashMap 选 2 倍这两个倍数差异背后是两类容器的定位差异。ArrayList 扩容的成本是整段内存的连续拷贝代价非常高所以它不能在容量上限附近抖来抖去需要留出余量但又不能像 HashMap 那样粗暴翻倍否则数组扩容到很大时浪费的空间也是整段连续内存。1.5 倍是一个既减少扩容次数、又不至于浪费太多空间的折中。数学期望上1.5 倍增长时扩容频率比 2 倍高但总体分配的内存更接近实际使用量。HashMap 则不同它的容量必须是 2 的幂这是最低要求否则位运算定位、扩容索引重算全部失效。而 2 的幂天然意味着每次扩容恰好翻倍——如果你想用接近 1.5 倍的比例并且保持 2 的幂只能退化成 1 倍不扩容或 2 倍没有中间项。既然 HashMap 翻倍带来的索引重算几乎零成本一条位运算判断高低位选择 2 倍对于它是最优解。维度ArrayListHashMap触发条件add 时数组已满size threshold 容量 * 0.75扩容倍数1.5 倍2 倍数据迁移System.arraycopy 整组拷贝逐个桶迁移、链表/树拆分新下标计算保序拷贝下标不变位运算留原位或 oldCap容量要求无必须为 2 的幂主要成本连续内存拷贝遍历全表节点重新分布这个对比表是我面试时经常画的。从设计哲学上看ArrayList 是线性结构位置就是顺序本身扩容只是换一块更大的连续内存HashMap 是哈希结构扩容是让元素分布得更稀疏代价不仅是拷贝还有重散列所以它必须从机制上把重散列成本降到最低。5.3 从两套机制里能抄到业务代码里的经验第一条经验是初始化时预估容量没有之一。HashMap 扩容最痛的点在于要遍历全表、拆链、重挂元素越多越贵。如果能在构造时给出合理容量全程零扩容性能和稳定性都会有明显提升。给 HashMap 定初始容量的公式是// expectedSize 是你计划放入的元素数量 // 除以 0.75f 是为了保证放满 expectedSize 个元素之前不触发扩容 // 1 是补偿浮点误差防止临界卡在阈值上 new HashMap((int) (expectedSize / 0.75f) 1);举个例子你确定要放 100 个元素100 / 0.75f 1 134HashMap 会把 134 向上修正为 2 的幂 256。如果你直接new HashMap(100)最终容量被 tableSizeFor 修正为 128但扩容阈值是 128 * 0.75 96意味着第 97 个元素就扩容了你实际只利用了 75% 就触发一次全量迁移得不偿失。ArrayList 的预估就更简单了构造时直接new ArrayList(expectedSize)精确命中目标容量避免多次 arraycopy。如果数据量级完全未知也没有更好的办法但至少别在循环里反复触发扩容——那种for循环里不断 add 几万条数据的场景每次扩容都要把前面所有元素拷贝一遍整体复杂度从 O(n) 变成 O(n log n) 甚至更高。第二条经验是峰值容量即上限。如果你要存放的最大数据量是 1 万那就按 1 万估不要按平均存量估。因为 HashMap 扩容阈值是按当前 capacity 算的一旦插入节奏超过阈值resize 成本完全不可控。我在实际项目中看过一个接口明明查询结果最多 200 条却每秒钟会被调用几百次代码里每次响应都new HashMap()默认容量开始 put到了一定业务量就频繁触发扩容GC 压力直接拉满。改成预估容量后接口的 P99 延迟降了差不多 40%。HashMap 扩容机制平时安安静静但它在高并发场景下的成本是实打实的。结合前面几章的内容再看扩容问题它其实是一个什么时候触发、怎么触发、触发时有什么代价、并发触发会有什么后果、如何从源头规避的完整链条。只要沿着这条链把源码读一遍即使面试官换个角度问 HashMap 底层实现原理也逃不开这几个点。唯一要多花时间的是亲手写几个自定义 key 的 demo验证一下 equals 和 hashCode 的坑毕竟纸上得来终觉浅能跑出问题才是真理解。