面试问HashMap扩容机制十个有八个能脱口而出“默认容量16、负载因子0.75、容量翻倍”。但你让他讲清楚“扩容时一条链表上的节点是怎么迁移到新数组的”或者“为什么JDK1.8里用e.hash oldCap就能判断该留原地还是往后挪”多半就卡壳了。坦白讲HashMap的扩容代码是所有集合类里最值得精读的一段——它把位运算、数据结构、并发安全这几块知识全串在了一个方法里。这篇文章就顺着resize()源码往下拆把扩容的前因后果、触发时机、迁移细节、1.7和1.8的差异全部过一遍。适合正在准备Java面试的人也适合那些想真正读源码但每次都被各种和位运算劝退的朋友。读完之后你再去看ConcurrentHashMap的并发扩容会发现很多思路是一脉相承的。1. 扩容到底在解决什么问题存储骨架与两个关键数值的设计1.1 HashMap的底层结构决定了“扩容”是必然操作HashMap底层是一个NodeK,V[] table数组也就是俗称的桶数组。每来一个key先算hash再用(n - 1) hash定位到数组的某个下标把节点放进去。如果多个key算出来的下标一样就在这个桶下面挂链表。链表太长超过8且数组长度达到64时链表会转成红黑树把查询从O(n)降到O(log n)。问题在于数组的长度是固定的总不可能无限装。如果一直往里put链表只会越来越长查询性能越来越差。所以HashMap必须有一个“快满的时候赶紧把数组变大、把数据重新分布”的机制——这就是扩容。很多人以为“HashMap数组满了才扩容”这是错的。数组是散列结构不可能等它满实际上元素个数达到一个阈值就会触发扩容这个阈值远小于数组长度。比如默认容量16阈值是12也就是说放了12个元素就会扩容到32。留出四分之一的空间是为了减少碰撞保证散列均匀。1.2 容量为什么必须是2的幂这是理解扩容的钥匙。HashMap的索引计算不是取模运算而是(n - 1) hash。这个式子能成立的前提是n必须是2的幂。因为2的幂减1之后二进制全是一串1比如16减1是15二进制0000 1111这时候 hash就相当于取hash的低4位等价于hash % 16但位运算比取模快得多。如果容量不是2的幂n - 1的二进制就不是全1索引分布会不均匀某些桶永远用不上某些桶挤成一堆。所以HashMap在构造时如果传了非2的幂容量会用tableSizeFor()把容量调整成“大于等于该值的最小2的幂”。这里要记住一个结论HashMap的所有设计都在围绕“2的幂”展开扩容翻倍oldCap 1不是为了简单变大一倍而是为了让索引计算继续走位运算同时让数据迁移变得极其高效。具体怎么高效第三节再详细说。1.3 负载因子0.75时间与空间的一笔账负载因子loadFactor的默认值是0.75它决定了阈值threshold capacity * loadFactor。为什么是0.75而不是0.5或者1这个值本质上是时间成本和空间成本的权衡。负载因子调大比如1.0数组利用率高、省内存但碰撞概率变大链表变长查询变慢。负载因子调小比如0.5碰撞减少、查询快但有一半空间浪费而且频繁扩容每次扩容都要迁移数据性能开销也不小。HashMap源码注释里给了个很有意思的参考理想情况下桶中节点的数量服从泊松分布当负载因子为0.75时单个桶内节点数到达8的概率约是千万分之六。这也是树化阈值为什么定为8的统计学依据。所以0.75不是拍脑袋定的是JDK团队在大量实践和概率模型下选出来的经验值。如果你能明确知道数据量可以在构造HashMap时指定一个更合适的负载因子但绝大多数场景下直接用默认值就好。2. 扩容从哪里开始put流程中resize()的触发时机与threshold计算2.1 一个key进来之后putValue里发生了什么看扩容之前得先弄清楚put是怎么走的。JDK1.8的putVal()核心流程如下final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { NodeK,V[] tab; NodeK,V p; int n, i; if ((tab table) null || (n tab.length) 0) n (tab resize()).length; if ((p tab[i (n - 1) hash]) null) tab[i] newNode(hash, key, value, null); else { // 冲突处理链表追加、红黑树插入、覆盖旧值 } modCount; if (size threshold) resize(); return null; }注意几个细节第一次put时table是null所以会走进resize()这其实是HashMap的懒加载——构造时不创建数组第一次put才创建。hash不是直接用的key.hashCode()而是经过扰动函数处理static final int hash(Object key) { int h; return (key null) ? 0 : (h key.hashCode()) ^ (h 16); }把高16位和低16位做异或目的是让高位的特征也参与索引计算。因为(n - 1) hash只用到低几位如果不同对象的hashCode低位相同、高位不同不做扰动的话冲突会很严重。扩容判断发生在插入之后size threshold才调resize()。也就是说这次put导致size超过阈值扩容是在put完成之后做的不是先扩容再插。2.2 threshold是谁算出来的构造器与晚分配机制很多读者会被threshold弄晕因为它在不同时期有不同含义。无参构造时loadFactor 0.75threshold 0table null。第一次put时resize()里会发现oldCap 0 oldThr 0于是走默认分支newCap DEFAULT_INITIAL_CAPACITY (16)newThr (int)(0.75 * 16) 12。有参构造时比如new HashMap(10)JDK1.8的做法是this.loadFactor loadFactor; this.threshold tableSizeFor(initialCapacity);这时threshold被临时存成经过对齐的容量值。tableSizeFor(10)结果是16所以threshold 16。注意此时它存的不是真正的扩容阈值而是一个“准容量”。等到第一次resize时else if (oldThr 0) newCap oldThr;把16当成新容量然后再走后面的逻辑算出newThr 16 * 0.75 12。所以一个new HashMap(10)实际只能存12个元素就会扩容而不是16个。这个“threshold先存容量、再变成阈值”的晚分配机制是JDK1.8引入的优化。早期版本构造时会直接创建一个Entry数组而1.8把数组创建推迟到第一次put省了“创建了却没用上”的浪费。2.3 扩容触发的真实时机元素个数超过阈值不是数组满了结合上面的流程可以总结出扩容的两个触发点一是初始化table为nullresize()负责创建初始数组。二是容量不足每次put完如果size threshold就调用resize()。这里的size是HashMap里所有键值对的总数不是某个桶的链表长度。哪怕数组里很多桶还是空的只要总数超过阈值就要扩容。所以阈值好比一个水位线它永远低于容量给每个桶留了缓冲空间。这也是HashMap性能优于“满了才扩”的设计的原因——散列冲突在低负载因子下会显著减少。3. resize()核心流程源码拆解新数组创建、链表拆分与红黑树分树3.1 新容量和新阈值计算的四个分支resize()的开头是一段分支判断决定新容量和新阈值。直接看代码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) // 情况二有参构造的第一次put newCap oldThr; else { // 情况三无参构造的第一次put newCap DEFAULT_INITIAL_CAPACITY; newThr (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); } if (newThr 0) { float ft (float)newCap * loadFactor; newThr (newCap MAXIMUM_CAPACITY ft (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE); } threshold newThr; // ... 创建新数组开始迁移 }这里有个容易被忽视的细节oldCap DEFAULT_INITIAL_CAPACITY这个条件决定了只有当旧容量不小于16时新阈值才直接翻倍。如果初始容量小于16比如你传了个非2的幂的容量被对齐成8第一次扩容时newThr不会跟着翻倍而是走newThr 0的分支用newCap * loadFactor重新计算。这是源码里一个比较隐蔽的小逻辑面试时能点出来会加分。另一个边界是MAXIMUM_CAPACITY值为1 30。如果容量已经达到这个上限就不再扩容了而是把threshold压到Integer.MAX_VALUE让你随便往里塞——反正数组已经到极限硬扩也没意义。3.2 单节点桶的直接迁移新数组创建好之后进入迁移阶段。迁移的核心是遍历旧数组的每个桶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 { // 链表拆分逻辑 } } } }如果桶里只有一个节点直接通过e.hash (newCap - 1)算出新索引放进去。这里要注意迁移时并没有重新调用hashCode()因为e.hash在put时已经算好并存储在节点里了。重新计算哈希很贵而且也没必要——只需要用同一份hash值配合新掩码重新定位即可。3.3 链表拆分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; } } while ((e next) ! null); if (loTail ! null) { loTail.next null; newTab[j] loHead; } if (hiTail ! null) { hiTail.next null; newTab[j oldCap] hiHead; }判断条件只有一个(e.hash oldCap) 0。为什么这一位能决定去留因为扩容是翻倍newCap oldCap 1。新掩码比旧掩码高一位这一位的权值恰好就是oldCap。举例来说oldCap 16时旧掩码是0000 1111新掩码是0001 1111。某个节点在新数组的下标取决于hash的第5位从0开始数是0还是1如果hash 16 0第5位是0新索引和旧索引完全一样。如果hash 16 1第5位是1新索引等于旧索引加16。所以根本不需要逐项重新计算每个元素的位置只要看hash新增的那一位就能把一整条链表均匀地分成两半一半留在原下标j一半挪到j oldCap。lo就是留在低位区的链hi就是移动到高位区的链。这个设计非常巧妙它把O(n)的重新哈希优化成O(n)的位运算判断而且迁移过程中链表的相对顺序保持不变。同时因为新掩码多了一位原本挤在同一条链表上的节点有机会被分配到两个不同的桶散列均匀性在扩容后天然得到改善。3.4 红黑树的分树与退化当桶里是红黑树时迁移逻辑走TreeNode.split()。核心思路和链表拆分一模一样也是用(e.hash bit)区分高低位但它多了一步拆完之后要根据节点数量决定继续保留树结构还是退化成链表。if (loHead ! null) { if (lc UNTREEIFY_THRESHOLD) tab[index] loHead.untreeify(map); else { tab[index] loHead; if (hiHead ! null) loHead.treeify(tab); } }如果拆分后某条链的节点数小于等于UNTREEIFY_THRESHOLD6就把红黑树退化回链表否则保持树结构。这里有个缓冲设计树化阈值是8退化为链表阈值是6中间留了2的差距就是为了防止元素在边界处频繁插入删除导致树和链表反复切换浪费性能。一个细节是TreeNode本身继承自LinkedHashMap.Entry所以它也有next指针可以像普通链表一样遍历。split()实际上先按照next指针把所有树节点串起来遍历一遍边遍历边按位拆成两条链然后再决定各自树化还是退化。3.5 一个具体的迁移示例光看代码不直观拿个例子走一遍。假设旧容量oldCap 8扩容到16某个旧桶下标是3里面有3个节点hash分别是3、11、27。key的hashhash 7旧索引hash 8hash 15新索引去向3303留在原桶3113811移动到桶1138273811移动到桶1138旧桶3的链表被拆成两条hash3单独留在newTab[3]hash11和hash27组成新链表挂到newTab[11]。整个过程没有调用一次求模运算也没有重新计算hash纯粹靠位运算完成分配。4. JDK1.7和JDK1.8的扩容差异从环形链到尾插法4.1 1.7的头插法与并发扩容死循环JDK1.7的扩容代码是另一个思路transfer()方法里遍历旧数组每个桶的链表用头插法把节点迁移到新数组void transfer(Entry[] newTable, boolean rehash) { int newCapacity newTable.length; for (EntryK,V e : table) { while(null ! e) { EntryK,V next e.next; int i indexFor(e.hash, newCapacity); e.next newTable[i]; newTable[i] e; e next; } } }头插法意味着遍历旧链表时每处理一个节点就把它插到新桶的头部。如果旧链是a - b - c迁移到新桶后顺序会反转成c - b - a。单线程下没问题但多线程并发扩容时两个线程同时操作同一条链表就会踩出大坑。经典的死循环场景是这样的线程A执行到next e.next后时间片用完线程B完成了整条链的迁移把链变成了b - a。线程A接着执行时它手里的e和next还是旧链的状态于是头插操作把a插到了b前面结果链表的next指针出现循环引用形成a - b - a - b...的环形结构。以后任何get操作走到这个桶上都会无限循环CPU直接飙满。这个问题在1.7时代是真实存在的线上事故很多人应该都听过“HashMap死循环导致服务器CPU 100%”的经典案例。4.2 1.8为什么改用尾插法JDK1.8把迁移改成了尾插法也就是前面看到的loTail/hiTail这条逻辑。每个节点按顺序追加到链尾保留了链表原有的相对顺序。这样一来即便多线程并发resize也不会因为头插反转而形成环形引用。所以1.8修复了1.7并发扩容死循环的问题。但注意HashMap依然不是线程安全的。1.8只是把“死循环”这个极端问题解决了并发put时依然存在数据覆盖丢失的可能。比如两个线程同时算出空桶位置同时执行tab[i] newNode(...)后写的把先写的覆盖了一个key就无声无息地丢了。所以并发场景该用ConcurrentHashMap还是得用别因为死循环没了就掉以轻心。4.3 1.8在扩容时机与寻址上的其它优化除了尾插法1.8还在几个地方做了调整扩容判断时机1.7是addEntry()里先判断size threshold table[bucketIndex] ! null再扩容1.8改成put完成后再判断。扰动函数简化1.7的hash做了4次扰动h ^ (h 20) ^ (h 12); return h ^ (h 7) ^ (h 4);。1.8简化为一次异或h ^ (h 16)。因为红黑树的引入降低了冲突成本不需要那么多扰动来摊平分布。迁移代价降低1.7每个节点都要重新indexFor()计算下标1.8用(e.hash oldCap)位运算直接分成高低两条链迁移效率更高。5. 扩容机制引发的高频面试题与工程避坑5.1 为什么HashMap线程不安全除了死循环还有数据覆盖面试里问“HashMap为什么不安全”不能只回答“并发会死循环”。1.8虽然不死循环了但不安全体现在两个层面一是并发put丢数据。两个线程在同一时刻往同一个桶插入节点都判断桶为空结果后写的覆盖先写的数据丢失。二是fail-fast机制。HashMap的迭代器在迭代过程中会检查modCount一旦发现modCount变化任何结构性修改都会让这个值1包括put、resize、remove立即抛ConcurrentModificationException。这意味着并发修改时你甚至无法安全地遍历一个HashMap。ConcurrentHashMap之所以安全是因为它把table分成了多个Segment1.7或者用CAS synchronized锁住单个桶的头节点1.8让并发操作粒度大大降低。有人会问ConcurrentHashMap扩容时是怎么线程安全的它引入了多线程协助扩容的机制多个线程各自认领一段下标范围的桶帮忙迁移。理解了HashMap的lo/hi拆分逻辑再看ConcurrentHashMap的transfer()会非常顺畅。5.2 如何避免频繁扩容容量预估的正确姿势扩容是个成本不低的操作要新建数组、迁移所有节点。如果你的HashMap数据量是已知的最好在构造时直接指定容量避免多次扩容。但注意new HashMap(n)并不代表能放n个元素。因为HashMap有个阈值限制真正能装下的元素数约等于n * 0.75。比如new HashMap(10000)实际容量被tableSizeFor对齐成16384阈值12288能装一万多。如果想确定10000个元素不触发扩容最稳的写法是int expectedSize 10000; MapString, Object map new HashMap((int) (expectedSize / 0.75f) 1);10000除以0.75加1约等于13334对齐后容量是16384阈值1228810000个元素稳稳放得下。Guava的Maps.newHashMapWithExpectedSize(expectedSize)底层就是这个公式本质是“如果你想放N个元素请按N/负载因子申请容量”。从源码里还能看到一个有意思的点JDK1.8构造HashMap时tableSizeFor会把任意非2的幂容量对齐成2的幂。比如你传了一个非常奇葩的容量1000对齐后是1024。所以预估容量的时候不需要自己纠结“是不是2的幂”大概齐就行源码帮你处理。5.3 几个容易被忽略的边界情况大量key哈希冲突时会有性能衰减。虽然红黑树能兜底但树化本身有代价。如果key对象的hashCode()写得稀烂比如都返回同一个常数那HashMap会直接退化成链表或一棵大树的性能。工程上遇到这种情况优先检查key的hashCode实现而不是盲目调负载因子。扩容期间迭代器失效。如果你在遍历HashMap的同时往里put即使没有多线程也可能因为扩容导致modCount变化而抛异常。需要在遍历时修改结构要么用Iterator.remove()要么用ConcurrentHashMap替换。key为null的hash是0。hash(null)直接返回0所以null key永远落在数组下标0的位置。理解了这一点在分析桶分布时别把null key的桶当成异常。不要迷信“默认容量16就够用”。场景不同HashMap的表现差异很大。比如你有50万条数据又没指定容量它会经历大约15次扩容50万/16不断翻倍到524288每次扩容都要全量迁移。一次扩容可能才几毫秒但连续几十次累积起来就是肉眼可见的耗时。提前算好容量能把这些开销直接抹掉。5.4 从扩容源码延伸到其它集合的思考看完了HashMap的扩容再去对比ArrayList的扩容会特别有感触。ArrayList扩容说白了就是Arrays.copyOf把旧数组整体拷贝到新数组元素位置不变不需要重新寻址因为它是线性结构。而HashMap因为是散列结构扩容还得做一遍数据重分布迁移逻辑复杂得多。这也是为什么HashMap的resize是集合框架里最值得精读的一段代码。有一点需要提醒HashMap的扩容不是“数组元素满了才发生”而是“元素个数超过阈值”就发生。阈值是容量乘负载因子得到的默认情况下数组其实还有约四分之一的空间是空闲的。理解了这一点很多关于HashMap的误解都能迎刃而解。最后说点我自己的体会。我第一次看resize()源码时觉得它“不过就是新建一个数组然后把元素搬过去”真正看懂lo/hi拆分和红黑树的split之后才意识到这套设计把“扩容”这种本来就很重的操作做到了尽可能少的重新哈希也尽量保持了链表的相对顺序。这个思路在之后研究ConcurrentHashMap的并发扩容多线程协助迁移桶时帮了我大忙。如果你也在啃源码我建议不要只盯着resize()这一个方法把putVal、treeifyBin、split、getNode串起来读你会发现HashMap整个设计是环环相扣的。顺着这条线把1.7的老代码也翻出来对比一下很多面试题不用背看着代码自己就推出来了。