扩缩容（Resize）
动态数组在元素数量超出容量时扩容、在元素过少时缩容的机制，用于平衡时间效率与空间利用率。
定义
扩容（Expand）：当动态数组的元素个数达到当前容量上限时，申请一个更大的底层数组，并将所有元素复制到新数组中。
缩容（Shrink）：当动态数组的元素个数减少到一定程度时，申请一个更小的底层数组，释放多余的空间。
为什么需要扩缩容？
静态数组的限制
静态数组的容量在创建时就固定了：
- 无法在原有内存后面"追加"空间（后面的内存可能已被占用）
- 只能重新申请更大的连续内存，再复制所有数据
空间利用率问题
如果从不缩容：
- 假设初始容量 1000，但只存储了 10 个元素 → 990 个空间被浪费
- 长期运行的应用程序可能积累大量无用内存
扩缩容策略
本文实现的策略（Java MyArrayList）：
| 操作 | 触发条件 | 新容量计算 | 时间复杂度 |
|---|---|---|---|
| 扩容 | size == capacity |
newCap = 2 * oldCap |
O(n) |
| 缩容 | size == capacity / 4 |
newCap = oldCap / 2 |
O(n) |
为什么扩容是 2 倍？
常见选择：1.5 倍或 2 倍
- 2 倍扩容：实现简单，扩容次数少，但可能浪费更多空间
- 1.5 倍扩容：空间利用率更高，但扩容次数稍多
时间效率：使用乘法扩容（而非加法），保证均摊时间复杂度为 O(1)。
为什么缩容条件是 1/4 而不是 1/2？
防止抖动（Thrashing）：
假设缩容条件是 1/2：
1. 数组容量 100，元素 50（刚好一半）
2. 添加一个元素 → 触发扩容 → 容量 200
3. 删除一个元素 → 剩 50 个 → 触发缩容 → 容量 100
4. 反复操作 → 频繁扩缩容，性能严重下降
使用 1/4 作为阈值：
- 当元素降到 1/4 时才缩容
- 留出缓冲空间，避免临界点反复横跳
均摊时间复杂度
虽然单次扩缩容需要 O(n)，但均摊下来每次操作的成本是 O(1)。
直观理解：
- 假设初始容量 1，依次添加 n 个元素
- 扩容发生在：1→2, 2→4, 4→8, ... , 2^k → 2^(k+1)
- 每个元素被复制的次数：最多 log₂(n) 次
- 均摊到 n 次操作：O(log n) / O(1) ？实际是 O(1)
精确的均摊分析：
- 使用记账方法或势能分析
- 每次插入操作"预付"一些成本用于未来的扩容
- 最终证明：n 次插入的总成本 = O(n)，均摊 = O(1)
实现示例
private void resize(int newCap) {
E[] temp = (E[]) new Object[newCap];
for (int i = 0; i < size; i++) {
temp[i] = data[i];
}
data = temp;
}
缩容触发：
public E removeLast() {
// ...
if (size == cap / 4) {
resize(cap / 2);
}
// ...
}
相关概念
总结
扩缩容是动态数组的核心机制。设计良好的策略（2倍扩容、1/4缩容）能够在时间效率和空间利用率之间取得平衡，并通过均摊分析保证长期性能。