什么是动态数组？ArrayList 的扩容机制是怎样的？

简化版

普通数组长度固定，动态数组（如 Java 的 ArrayList）在它外面包了一层「自动扩容」：底层还是数组，装满时申请一块更大的新数组（Java 里扩到原来的 1.5 倍），把旧元素拷过去，再继续加。因为不是每次都扩容，尾部追加的均摊时间复杂度是 O(1)。

详细版

动态数组 = 底层定长数组 + 自动扩容逻辑。以 ArrayList 为例：

初始容量：new ArrayList<>() 首次 add 时才分配长度 10 的数组（懒加载）。
扩容触发：size == 数组长度 时再 add，就要扩容。
扩容倍数：新容量 = 旧容量 + (旧容量 >> 1)，即 1.5 倍。
搬迁：Arrays.copyOf 把旧数组元素复制到新数组，旧数组被 GC 回收。

// JDK ArrayList 扩容核心（简化）
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1); // 1.5 倍
elementData = Arrays.copyOf(elementData, newCapacity);

扩容是 O(n)（要拷贝所有元素），但它不是每次 add 都发生。把偶尔一次的扩容成本摊到大量 add 上，尾部追加的均摊复杂度是 O(1)。

完整版教学

一、为什么需要动态数组

数组的硬伤是「长度定死」：声明 int[10] 就只能放 10 个。但现实中我们常常事先不知道要放多少元素。动态数组就是来解决这个的——对外表现得像「能无限增长的数组」，对内则在容量不够时偷偷换一块更大的数组。它把「定长数组的随机访问 O(1) 优点」和「能自动增长的便利」结合了起来。

二、扩容的完整过程

add 时先检查 size 是否等于底层数组长度。
若已满，计算新容量（ArrayList 是旧容量的 1.5 倍）。
Arrays.copyOf 创建新数组并把旧元素逐个拷过去。
新元素放进新数组，size++，旧数组等待 GC。

关键点：扩容会产生一次 O(n) 的整体拷贝。所以「一次 add」在最坏情况（触发扩容）是 O(n)，但平摊下来是 O(1)。

三、为什么是 1.5 倍而不是 2 倍

1.5 倍（Java ArrayList）：增长更平缓，浪费的空间更少；而且旧内存块有机会被后续的新分配复用（多次 1.5 倍增长的总和更容易「装回」之前释放的碎片）。
2 倍（如 C++ vector 常见实现、Java HashMap）：扩容次数更少，但每次可能浪费近一半空间，且 2 倍增长后新块永远大于之前所有释放块之和，无法复用旧内存。

两者都是「时间（扩容频率）和空间（浪费多少）」的权衡，没有绝对优劣。

四、均摊 O(1) 的证明思路

假设从空开始连续 add n 个元素，扩容分别发生在容量 1、2、4、8…（以 2 倍为例）时，拷贝成本是 1 + 2 + 4 + … + n ≈ 2n。也就是说 n 次 add 的总拷贝成本是 O(n)，平均每次 O(1)。1.5 倍同理，等比数列求和仍是 O(n)。这就是「均摊分析」：不能只盯着触发扩容那一次的 O(n)，要看长期平均。

五、实战注意点

已知规模就预设容量：new ArrayList<>(1000)，一次到位，避免多次扩容拷贝。
扩容只增不减：ArrayList 删除元素不会自动缩容，需要 trimToSize() 手动回收。
中间插入仍是 O(n)：动态数组解决的是「长度可变」，没解决「中间插入删除要搬移」——那是数组的固有代价。

实现	底层结构	常见扩容策略	需要强调的点
Java `ArrayList`	`Object[]`	旧容量 + 旧容量的一半	首次添加时默认容量通常变为 10
C++ `vector`	连续数组	标准不规定，常见实现约 1.5 或 2 倍	迭代器/指针可能因扩容失效
Python `list`	连续指针数组	过度分配，增长比例不是固定 2 倍	存的是对象引用，不是对象本体

举个具体过程：空 ArrayList 首次添加后容量为 10，继续添加到第 11 个元素时扩到 15；第 16 个元素触发扩到 22；第 23 个元素触发扩到 33。扩容那一次要复制旧元素，但中间很多次 add 只是写入下一个空位。

回答 ArrayList 扩容题时要分清三个词：size 是已有元素个数，capacity 是底层数组长度，length 对数组来说才是固定长度。

六、常见误区与追问

误区：动态数组每次添加都会重新申请数组。 只有容量满了才扩容，大多数尾部添加只是写入已有空位。
误区：尾部添加一定是 O(1)。 从单次最坏情况看，触发扩容时是 O(n)；从长期均摊看才是 O(1)。
误区：ArrayList 删除元素会自动缩容。 删除只移动元素并减少 size，底层容量通常不变，想收缩要显式调用 trimToSize()。
追问：为什么预设容量能提升性能？ 如果已知要放 10 万个元素，提前分配可以减少多轮扩容和数组复制。
追问：扩容为什么不用每次只加 1？ 每次只加 1 会导致连续追加 n 个元素时复制成本接近 1+2+...+n，总成本退化到 O(n²)。
追问：扩容后原数组怎么办？ 新数组接管存储，旧数组不再被引用后由垃圾回收处理；在 C++ 中则由容器释放旧内存。

七、加强记忆

动态数组 = 定长数组 + 自动扩容。装满时申请更大的新数组（ArrayList 是 1.5 倍）并拷贝旧元素，单次扩容 O(n) 但尾部追加均摊 O(1)。1.5 倍 vs 2 倍是扩容频率与空间浪费的权衡。已知规模就预设初始容量，省掉反复扩容。

简化版

详细版