数据结构与算法 / 系统课时
动态数组与扩容机制
动态数组与扩容机制
动态数组看似可以不断增长,底层仍是长度固定的普通数组。本课拆解容量检查、创建新数组、复制元素和替换引用的过程,并解释尾部追加为何具有均摊 复杂度。
学习目标
- 区分动态数组的有效长度
size与底层容量capacity。 - 掌握按比例扩容、数据复制和零容量处理。
- 能解释单次扩容 与连续追加均摊 的区别。
扩容本质与触发条件
动态数组始终满足 0 <= size <= capacity。当 size < capacity 时,新元素可直接写入下标 size;当二者相等时,必须先扩容。
扩容不是修改原数组长度,而是计算新容量、创建更大的数组、复制全部有效元素,再让字段引用新数组。旧数组失去引用后由运行时回收。

按固定小增量扩容会频繁复制。通用动态数组通常按比例增长,例如两倍或约 1.5 倍。初始容量为 0 时不能直接翻倍,否则新容量仍为 0,必须设置最小起始容量。
为什么追加是均摊 O(1)
触发扩容的单次追加需要复制当前 n 个元素,因此最坏为 。但以两倍增长为例,连续加入 n 个元素时,历史复制量近似为 1 + 2 + 4 + ...,其总和小于 2n。
因此一系列追加的总工作量仍为 ,平均到每次操作就是均摊 。均摊结论描述操作序列,不代表每一次追加都耗时相同。
主示例:实现可扩容整数数组
下面的 Java 17 示例支持尾部追加、指定位置插入和显式 trimToSize。扩容采用两倍策略,零容量时从默认容量 4 开始。
java
import java.util.Arrays;
public class DynamicArrayDemo {
public static void main(String[] args) {
DynamicIntArray array = new DynamicIntArray(2);
array.add(10);
array.add(20);
array.add(30);
array.add(40);
array.add(50);
array.insert(2, 25);
System.out.println(
"扩容后: " + array
+ ", size=" + array.size()
+ ", capacity=" + array.capacity()
);
array.trimToSize();
System.out.println(
"整理后: " + array
+ ", size=" + array.size()
+ ", capacity=" + array.capacity()
);
}
static final class DynamicIntArray {
private static final int DEFAULT_CAPACITY = 4;
private int[] elements;
private int size;
DynamicIntArray(int initialCapacity) {
if (initialCapacity < 0) {
throw new IllegalArgumentException("初始容量不能小于 0");
}
elements = new int[initialCapacity];
}
void add(int value) {
ensureCapacity(size + 1);
elements[size++] = value;
}
void insert(int index, int value) {
if (index < 0 || index > size) {
throw new IndexOutOfBoundsException("插入位置越界");
}
ensureCapacity(size + 1);
// System.arraycopy 能安全处理同一数组内的重叠区间。
System.arraycopy(
elements,
index,
elements,
index + 1,
size - index
);
elements[index] = value;
size++;
}
void trimToSize() {
if (size != elements.length) {
elements = Arrays.copyOf(elements, size);
}
}
int size() {
return size;
}
int capacity() {
return elements.length;
}
private void ensureCapacity(int minimum) {
if (minimum <= elements.length) {
return;
}
int oldCapacity = elements.length;
if (oldCapacity > Integer.MAX_VALUE / 2) {
throw new IllegalStateException("数组容量已接近整数上限");
}
int newCapacity = oldCapacity == 0
? DEFAULT_CAPACITY
: oldCapacity * 2;
if (newCapacity < minimum) {
newCapacity = minimum;
}
elements = Arrays.copyOf(elements, newCapacity);
}
@Override
public String toString() {
return Arrays.toString(Arrays.copyOf(elements, size));
}
}
}编译并运行:
bash
javac DynamicArrayDemo.java
java DynamicArrayDemo预期输出:
text
扩容后: [10, 20, 25, 30, 40, 50], size=6, capacity=8
整理后: [10, 20, 25, 30, 40, 50], size=6, capacity=6容量策略与边界
扩容前必须先判断容量,不能先写入再扩容。Arrays.copyOf 返回新数组,若不接收返回值,底层引用仍指向旧空间。
删除后不一定要自动缩容。过于积极地在添加和删除之间扩缩,会产生反复复制。工程实现常采用较低利用率阈值,或像示例一样提供显式整理方法。对象数组删除元素后还应清空失效尾部引用。
示例在翻倍前检查整数上限,用于说明容量计算必须防护;真实 JDK 集合还会考虑虚拟机允许的最大数组长度,并采用更严格的增长策略。
按自己的节奏,确认真正理解。