顺序表的底层真相——为什么ArrayList扩容偏偏选1.5倍目录一、真实面试真题引入二、底层扩容机制的源码级解构2.1 add(E e) 的调用链从一行代码到内存搬移2.2 grow()——扩容决策的核心2.3 System.arraycopy——JVM 的底层 memmove2.4 摊销分析add() 真的是 O(1) 吗三、原创案例实战3.1 聊天记录存储引擎——支持批量删除与内存搬移四、源码避坑指南与 Debug 日记五、面试连环炮 Mock Interview六、通俗类比小结一、真实面试真题引入上个月刷牛客看到一个帖某司二面问了这么一道题“ArrayList 的默认容量是 10扩容倍数是 1.5 倍。为什么不是 100为什么不是 2为什么偏偏是 1.5”评论区清一色的1.5 倍是 JDK 设计者的经验选择——正确但跟没说一样。面试官问 1.5 倍他不是想听源码里就写了 1.5。他想听的是1.5 这个数字怎么来的、它比 2 好在哪里、跟内存管理有什么关系、为什么 HashMap 扩容又选了 2 倍。他想确认你不但看了源码还想过源码背后的事。上一期我们聊了 ArrayList 和 LinkedList 在遍历场景下的缓存行差异这一期钻到 ArrayList 内部——当你往一个 ArrayList 里塞第 11 个元素时JVM 到底干了什么。二、底层扩容机制的源码级解构2.1 add(E e) 的调用链从一行代码到内存搬移你写list.add(hello)后面发生了什么翻 JDK 17 源码// ArrayList.javapublicbooleanadd(Ee){modCount;// 结构修改计数fail-fast 用add(e,elementData,size);// 调同名私有方法returntrue;}privatevoidadd(Ee,Object[]elementData,ints){if(selementData.length)// 满了elementDatagrow();// → 扩容elementData[s]e;// 放入新元素sizes1;}两步先看容量够不够不够就扩然后往末尾塞。但真正有意思的东西在grow()里。2.2 grow()——扩容决策的核心privateObject[]grow(){returngrow(size1);// 至少需要 size1 个位置}privateObject[]grow(intminCapacity){intoldCapacityelementData.length;if(oldCapacity0||elementData!DEFAULTCAPACITY_EMPTY_ELEMENTDATA){intnewCapacityArraysSupport.newLength(oldCapacity,minCapacity-oldCapacity,// 最小增长量oldCapacity1// 优先增长量 oldCapacity / 2);returnelementDataArrays.copyOf(elementData,newCapacity);}else{// 初始化为默认容量 10returnelementDatanewObject[Math.max(DEFAULT_CAPACITY,minCapacity)];}}关键在ArraysSupport.newLength这是 JDK 16 之后引入的// ArraysSupport.javapublicstaticintnewLength(intoldLength,intminGrowth,intprefGrowth){intprefLengtholdLengthMath.max(minGrowth,prefGrowth);if(0prefLengthprefLengthSOFT_MAX_ARRAY_LENGTH){returnprefLength;}else{// 超大数组走另一条路这里不展开returnhugeLength(oldLength,minGrowth);}}三个参数掰开了看oldCapacity当前数组长度比如 10minGrowth最小必须增长的量 minCapacity - oldCapacity比如 11 - 10 1prefGrowth期望增长量 oldCapacity 1也就是 oldCapacity 的一半新容量 oldCapacity max(minGrowth, prefGrowth)。大多数时候prefGrowth oldCapacity / 2远大于minGrowth通常 1所以新容量 ≈ oldCapacity oldCapacity/2 1.5 倍。那 1.5 这个数字怎么来的不是拍脑袋。2.3 System.arraycopy——JVM 的底层 memmoveJava 数组分配后长度是死的不能改。扩容不是把数组变大是new 一个新数组把旧数据拷过去旧数组等着被 GC。这一步由Arrays.copyOf→System.arraycopy完成// Arrays.javapublicstaticTT[]copyOf(T[]original,intnewLength){return(T[])copyOf(original,newLength,original.getClass());}publicstaticT,UT[]copyOf(U[]original,intnewLength,Class?extendsT[]newType){T[]copy(Object)newType(Object)Object[].class?(T[])newObject[newLength]:(T[])Array.newInstance(newType.getComponentType(),newLength);System.arraycopy(original,0,copy,0,Math.min(original.length,newLength));returncopy;}System.arraycopy是个 native 方法在 HotSpot 里往下走会调用memmove——C 标准库的内存拷贝函数。它比 for 循环一个个拷快得多因为 memmove 会利用 CPU 的向量指令SIMD一次性搬 16/32/64 字节而且能处理源和目标内存区域重叠的情况。扩容过程的完整时间线add(第11个) 触发 → 检查 size(10) elementData.length(10) → 满了 → grow(): 新容量 10 max(1, 5) 15 → Arrays.copyOf: new Object[15] → System.arraycopy: 把旧数组的 10 个引用拷到新数组 → elementData 指向新数组 → 旧数组失去引用等待 GC → elementData[10] 第11个 → size 11用一张图看这个全过程扩容前: [A][B][C][D][E][F][G][H][I][J] ← 容量10已满 ↓ System.arraycopy 扩容后: [A][B][C][D][E][F][G][H][I][J][ ][ ][ ][ ][ ] ← 容量15 ↑ 旧数组回收2.4 摊销分析add() 真的是 O(1) 吗你可能会问扩容的时候要拷所有元素那不是 O(n) 吗为什么还说 ArrayList 尾部插入是 O(1)答案在摊销分析Amortized Analysis。从容量 10 开始一路 add 到 100 个元素扩容会发生几次初始容量 10第 11 次 add → 扩容到 15拷贝 10 个第 16 次 add → 扩容到 22拷贝 15 个第 23 次 add → 扩容到 33拷贝 22 个第 34 次 add → 扩容到 49拷贝 33 个第 50 次 add → 扩容到 73拷贝 49 个第 74 次 add → 扩容到 109拷贝 73 个总共 add 了 100 次拷贝操作的总次数 101522334973 202 次。平均每次 add 才 2 次拷贝。再推到 n 次 add总拷贝次数 ≈ n n/1.5 n/1.5² … ≈ n × (1/(1-1/1.5)) 3n。均摊下来每次 add 的拷贝次数是常数。所以尾部插入的均摊复杂度是 O(1)。而且如果你提前知道大概要放多少元素构造函数里直接指定容量newArrayList(1000);// 一次性分配省去一整串扩容这个优化在生产代码里很常见哪怕你估不准估个数量级也比不估强。三、原创案例实战3.1 聊天记录存储引擎——支持批量删除与内存搬移搞一个场景做一个小型聊天应用的消息存储模块。消息量大、经常批量清理比如清空某个会话的聊天记录用一个动态数组做底层存储手动管扩容和删除后的内存压缩。importjava.util.Arrays;publicclassChatMessageStore{privateString[]messages;// 底层数组privateintsize;// 当前消息数publicChatMessageStore(){messagesnewString[8];// 初始容量 8size0;}// 添加消息触发扩容publicvoidaddMessage(Stringmsg){if(sizemessages.length){expand();}messages[size]msg;}// 扩容1.5 倍privatevoidexpand(){intnewCapmessages.length(messages.length1);String[]newArrnewString[newCap];System.arraycopy(messages,0,newArr,0,size);messagesnewArr;System.out.printf([扩容] %d → %d, 拷贝 %d 条消息%n,messages.length*2/3,newCap,size);}// 批量删除指定范围的消息后面元素前移publicvoiddeleteRange(intfromIdx,inttoIdx){intdeleteCounttoIdx-fromIdx;// 把后半部分往前搬System.arraycopy(messages,toIdx,messages,fromIdx,size-toIdx);// 清空尾部悬空引用for(intisize-deleteCount;isize;i){messages[i]null;// 防止内存泄漏}size-deleteCount;}// 打印当前状态publicvoiddump(){System.out.printf(size%d, capacity%d, 空闲%d%n,size,messages.length,messages.length-size);for(inti0;isize;i){System.out.printf( [%d] %s%n,i,messages[i]);}}// 测试入口 publicstaticvoidmain(String[]args){ChatMessageStorestorenewChatMessageStore();// 模拟加消息for(inti1;i25;i){store.addMessage(消息i);}store.dump();// size25, capacity27// 模拟批量删除清除前 10 条store.deleteRange(0,10);System.out.println(--- 删除索引 0~9 后 ---);store.dump();// size15, capacity27}}跑一遍输出大致是[扩容] 8 → 12, 拷贝 8 条消息 [扩容] 12 → 18, 拷贝 12 条消息 [扩容] 18 → 27, 拷贝 18 条消息 size25, capacity27, 空闲2 --- 删除索引 0~9 后 --- size15, capacity27, 空闲12扩容、arraycopy、删除后搬移这个例子全串起来了。注意删除后我用messages[i] null显式清空了悬空引用——如果不手动清逻辑上元素被删除了但数组还抓着引用不放GC 不会回收。这就是内存泄漏藏得很隐蔽。四、源码避坑指南与 Debug 日记从 C/Python 转 JavaArrayList 扩容相关的几个坑坑1认为 new ArrayList() 就是容量 0JDK 7 之后new ArrayList()分配的是DEFAULTCAPACITY_EMPTY_ELEMENTDATA——一个共享的空数组实例不是长度为 10 的数组。真正的 10 个容量是在你第一次 add 时才分配的懒初始化。你是说先 list 放着不用——那它就是一个空壳零内存开销。坑2用 ensureCapacity 时以为可以缩容list.ensureCapacity(5);// 如果当前容量 5啥也不干ensureCapacity只确保容量不小于传入值语义是保底不是缩小。缩容用trimToSize()。坑3多线程下 add 触发的 ConcurrentModificationException两个线程同时往 ArrayList 里 add可能同时触发扩容。线程 A 先扩容完elementData指向了新数组线程 B 还在旧数组上操作直接索引越界或数据丢失。ArrayList 不是线程安全的多线程场景老老实实用CopyOnWriteArrayList或外部加锁。坑4你以为扩容只发生在 addaddAll也可能触发扩容。list.addAll(anotherList)和list.add(element)走的都是同一套grow(minCapacity)区别只在于 minCapacity 是size anotherList.size()而不是size 1。五、大厂面试连环炮 Mock Interview面试官“ArrayList 扩容机制说一下。”高分话术“add 时先检查容量满了就调 grow()。新容量由 ArraysSupport.newLength 计算取 oldCapacity max(需要的最小增长量, oldCapacity/2)结果大约是 1.5 倍。扩容时 new 一个新数组System.arraycopy 把旧数据拷过去旧数组失去引用等待 GC。”面试官“为什么是 1.5 倍不是 2 倍”高分话术“这是空间和时间的权衡。设扩容因子为 kn 次 add 的总拷贝开销约为 n/(k-1) 次元素拷贝空间浪费率约为 k-1。k 越大拷贝次数越少时间优但空间浪费越大空间劣。1.5 倍在空间利用率上优于 2 倍——扩容后释放的旧数组内存块在下下次扩容时恰好能被复用减少内存碎片。比如容量 10→15→22→33每次释放的块依次是 10、15、22而 101525 22旧块能拼出下一次扩容所需的空间。2 倍扩容10→20→40→80释放的块是 10、20、40102030 40拼不起来只能从空闲内存里另找更大的连续块。”面试官“那 HashMap 扩容为什么又是 2 倍”高分话术“HashMap 的容量必须是 2 的幂因为它的散列定位用的是hash (capacity - 1)位运算代替取模这要求 capacity 是 2 的幂。扩容翻倍刚好维持这个性质。另外 HashMap 的 rehash 代价远大于 ArrayList 的 arraycopy——每个元素要重新算桶位置所以 2 倍扩容减少扩容频率在 HashMap 里收益更大。ArrayList 只是连续内存搬移代价低得多可以容忍更频繁的扩容来换取更好的空间利用率。”面试官“默认容量为什么是 10”高分话术“这是一个经验值。太小了——比如 2——前几次 add 就会频繁扩容太大了——比如 100——大多数场景用不了这么多浪费内存。10 是 ArrayList 作者 Josh Bloch 根据当时 Java 应用的典型集合大小选的折中值。实际上 JDK 的设计哲学是’先不给等你要了再给’——new ArrayList() 连这 10 个容量都是懒分配的。”六、通俗类比小结把 ArrayList 扩容类比成租房子刚毕业租了个单间容量 10行李不多刚好够用。后来东西越买越多add单间塞不下了得搬家。找房子的时候你不会找一模一样大的——下次还得搬。你找了个大 50% 的两居室1.5 倍扩容把旧房子的东西全搬过去System.arraycopy旧房子退租GC。为什么不直接租个别墅容量 10000月租太贵大部分房间空着空间浪费。为什么不只多租 10%1.1 倍搬家太频繁一年搬七八次谁也受不了。1.5 倍是搬家频率和房租开销之间的一个还不错的平衡点。至于 HashMap2 倍扩容相当于合租——每次搬家人数翻倍但分房间的规则要求房间总数必须是 2 的幂位运算取模所以干脆翻倍。依旧求点赞收藏加关注咱们下期见