ArrayList 是怎么扩容的？｜阿里巴巴算法面经解析

60 秒回答模板

ArrayList 底层不是链表，而是一个 Object[] 数组配合 size 记录已存元素个数。空参创建时通常不会立刻分配长度为 10 的数组，而是先使用空数组，第一次 add 时通过 ensureCapacity 相关逻辑确认最小容量，默认扩到 10。之后每次追加元素都会先判断 size + 1 是否超过当前数组长度；如果容量够，直接把元素放到 elementData[size] 并让 size 加一；如果不够，就创建新数组，常见 OpenJDK 实现按 oldCapacity + oldCapacity / 2 扩大，也就是约 1.5 倍。如果 1.5 倍仍小于本次所需最小容量，就以最小所需容量为准；再通过数组复制把旧元素搬到新数组。因为扩容时要复制已有元素，所以单次扩容最坏是 O(n)，但连续尾部追加时，扩容不是每次发生，均摊下来 add 通常是 O(1)。随机访问是 O(1)，但中间插入或删除需要移动后续元素，所以是 O(n)。还要注意 ArrayList 有最大容量限制，容量过大可能触发 OutOfMemoryError。

考点 底层结构

主线 懒分配与默认容量

易错点 把 ArrayList 说成链表结构，忽略其底层是 O…

深入解析

底层结构

ArrayList 的核心数据结构是 Object[] elementData，配合 int size 表示当前真实元素个数。数组长度代表当前容量，size 代表已经放进去的元素数量，两者不是一回事。由于底层是连续数组，所以按下标访问元素可以直接定位，时间复杂度是 O(1)，这也是 ArrayList 适合频繁随机读取的原因。

懒分配与默认容量

空参构造 ArrayList 时，常见实现并不会马上创建长度为 10 的真实数组，而是先引用一个共享空数组，等第一次 add 时再分配容量。第一次添加元素时，最小需求容量是 1，但空参构造的默认扩容会把容量提升到 10。这样做可以避免创建很多空 List 时浪费内存。

添加元素路径

执行 add(E e) 时，关键步骤不是直接写数组，而是先确保 size + 1 的容量需求能够被满足。容量够时，元素直接写入 elementData[size]，然后 size 自增。容量不够时，会进入 grow 逻辑，先计算新容量，再分配新数组并复制旧数据，最后再完成本次写入。

扩容规则

常见 OpenJDK 实现的扩容公式是 newCapacity = oldCapacity + oldCapacity / 2，也就是约 1.5 倍增长。这个策略在空间浪费和复制频率之间折中：扩得太小会频繁复制，扩得太大会浪费内存。如果计算出的新容量仍小于本次最小需求容量，就会直接使用最小需求容量。

复制成本

ArrayList 扩容不是原地把数组变长，因为 Java 数组长度固定。扩容时必须申请一个更大的新数组，再把旧数组中的已有元素复制过去。这个复制过程和当前元素数量线性相关，所以单次扩容的最坏时间复杂度是 O(n)，并且会产生额外内存占用和对象引用复制开销。

复杂度判断

尾部追加在容量充足时是 O(1)，遇到扩容时是 O(n)，但由于扩容按比例增长，连续多次 add 的总复制成本会被摊薄，所以均摊复杂度通常说是 O(1)。随机插入、随机删除不是 O(1)，因为数组中间位置变化会导致后续元素整体移动，复杂度通常是 O(n)。

容量上限

ArrayList 不能无限扩容，一方面受数组最大长度、虚拟机实现和整数上限影响，另一方面受堆内存大小限制。当容量非常大时，扩容需要同时持有旧数组和新数组一段时间，容易触发 OutOfMemoryError。面试中提到这个点，可以体现对真实运行风险的理解。

对比回答

和普通数组相比，ArrayList 封装了自动扩容、size 管理和集合接口能力，但底层仍然受数组连续存储影响。和 LinkedList 相比，ArrayList 随机访问更快、内存局部性更好，但中间插入删除需要搬移元素；LinkedList 不需要数组扩容，但查找位置本身通常要线性遍历。

易错点

把 ArrayList 说成链表结构，忽略其底层是 Object[] 数组。
认为空参构造时一定立刻创建长度为 10 的数组。
只说扩容 1.5 倍，却不说明容量不足时会复制旧数组。
把尾部 add 直接说成永远 O(1)，没有区分最坏和均摊复杂度。
混淆 size 和 capacity，误以为元素个数等于底层数组长度。
忽略中间插入删除要移动元素，错误地认为所有操作都很快。

面试官追问

为什么 ArrayList 扩容选择约 1.5 倍，而不是每次加 1 或直接翻倍？

每次加 1 会导致频繁扩容和频繁数组复制，连续追加时性能很差；直接翻倍可以减少扩容次数，但可能造成较多空闲容量浪费。约 1.5 倍是在复制次数和空间利用率之间做折中。

ArrayList 和 LinkedList 在插入删除上谁更快？

不能简单说 LinkedList 一定更快。如果已经拿到节点，链表插入删除调整引用即可；但按下标插入删除时，LinkedList 通常还要先遍历到目标位置。ArrayList 则需要移动数组元素，适合读多写少和尾部追加。

ensureCapacity 有什么作用？

ensureCapacity 可以提前把底层数组扩到预期容量，适合已经知道大概元素数量的场景。这样能减少后续 add 过程中的多次扩容和数组复制，改善批量写入性能。

ArrayList 删除元素后容量会自动缩小吗？

一般删除元素只会让 size 变小，并把被移除位置或尾部引用置空以帮助垃圾回收，底层数组容量通常不会自动缩小。需要主动调用 trimToSize 才可能尝试收缩容量。

ArrayList 是线程安全的吗？

ArrayList 本身不是线程安全集合。多个线程同时修改可能导致数据覆盖、size 不一致或遍历时并发修改异常。需要外部同步、使用 Collections.synchronizedList，或者根据场景选择并发集合。