一、扩容策略的选择
这一篇对应官方 Lecture 7(ALists, Resizing, vs. SLLists)。
固定数组存满了,想再放一个元素,只有一条路:申请一块更大的,把老数据搬过去。问题在于——新数组开多大。
- 每次多开 1 个位置:连续 N 次添加,搬运次数是 1 + 2 + 3 + … + (N−1) ≈ N²/2。
- 每次把容量翻倍:搬运次数是 1 + 2 + 4 + … ≈ N。
两种策略得到的总代价差了一个数量级。这一篇用真实计数把这件事量出来。
二、AList 的两个长度
动态数组的关键,是把「数组有多长」和「列表里有多少元素」分成两个字段。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58
| public class AList { private int[] items; private int size; public int resizeCount = 0;
public AList() { items = new int[8]; size = 0; }
private void resize(int capacity) { int[] bigger = new int[capacity]; System.arraycopy(items, 0, bigger, 0, size); items = bigger; resizeCount += 1; }
public void addLast(int x) { if (size == items.length) { resize(size * 2); } items[size] = x; size += 1; }
public int get(int i) { return items[i]; }
public int removeLast() { int last = items[size - 1]; size -= 1; return last; }
public int size() { return size; }
public int capacity() { return items.length; }
public static void main(String[] args) { AList L = new AList(); System.out.println("初始容量 " + L.capacity()); for (int i = 0; i < 20; i += 1) { L.addLast(i); if (i == 7 || i == 8 || i == 15 || i == 16 || i == 19) { System.out.println("放完第 " + (i + 1) + " 个:size = " + L.size() + ",容量 = " + L.capacity() + ",扩容次数 = " + L.resizeCount); } } System.out.println("get(19) = " + L.get(19) + ",removeLast() = " + L.removeLast() + ",size = " + L.size()); } }
|
输出:
1 2 3 4 5 6 7
| 初始容量 8 放完第 8 个:size = 8,容量 = 8,扩容次数 = 0 放完第 9 个:size = 9,容量 = 16,扩容次数 = 1 放完第 16 个:size = 16,容量 = 16,扩容次数 = 1 放完第 17 个:size = 17,容量 = 32,扩容次数 = 2 放完第 20 个:size = 20,容量 = 32,扩容次数 = 2 get(19) = 19,removeLast() = 19,size = 19
|
两个观察:
- 第 9 个元素触发扩容。 前 8 个填满了初始容量 8,第 9 个放不下,容量翻到 16。
size 与 capacity 是两回事。 输出中 size = 20 时容量是 32,有 12 个空位;这些空位属于正常预留,不算浪费。
flowchart LR
A["size = 8<br/>capacity = 8"] -->|"再加 1 个"| B["扩容:new int[16]<br/>arraycopy"] --> C["size = 9<br/>capacity = 16"]
C -->|"继续加到 16"| D["size = 16<br/>capacity = 16"]
D -->|"再加 1 个"| E["扩容:new int[32]"] --> F["size = 17<br/>capacity = 32"]
三、均摊分析:把总代价摊到每一次操作
单看一次 addLast,最坏情况是 O(N)——它可能正好赶上搬运全部元素。但连续 N 次操作的总代价是多少?
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
| public class ResizeCount { public static void main(String[] args) { int n = 1_000_000; int capacity = 1; int resizes = 0; long copies = 0;
for (int i = 0; i < n; i += 1) { if (i == capacity) { copies += capacity; capacity *= 2; resizes += 1; } }
long linear = (long) n * (n - 1) / 2;
System.out.println("N = " + n); System.out.println("倍增扩容次数 = " + resizes); System.out.println("倍增总搬运元素数 = " + copies); System.out.println("平均每个元素搬运 " + String.format("%.3f", (double) copies / n) + " 次"); System.out.println("若每次只 +1 扩容,总搬运元素数 = " + linear); } }
|
输出:
1 2 3 4 5
| N = 1000000 倍增扩容次数 = 20 倍增总搬运元素数 = 1048575 平均每个元素搬运 1.049 次 若每次只 +1 扩容,总搬运元素数 = 499999500000
|
这组数字把均摊分析讲完了:
- 扩容只发生 20 次,因为容量按 1、2、4、…、524288 增长,
2^20 = 1048576 已经覆盖 100 万个元素。
- 总搬运 1048575 次,恰好是
2^20 − 1。等比数列求和,量级是 O(N) 而不是 O(N²)。
- 平均到每个元素只有 1.049 次搬运,是个常数。所以
addLast 的均摊复杂度是 O(1)。
对比最后一行:如果改成每次只加 1 个位置,总搬运会到 499999500000 次,相差约 47 万倍。这就是「扩容策略」这一行代码的分量。
四、链表与数组列表怎么选
两种列表都能存序列,但代价分布完全不同。
| 操作 |
SLList |
AList |
| 头部插入 |
O(1) |
O(N),要整体后移 |
| 尾部插入 |
O(N),需走到末尾 |
均摊 O(1) |
| 按下标取 |
O(N) |
O(1) |
| 空间开销 |
每节点一个额外引用 |
预留容量可能空置 |
| 扩容抖动 |
无 |
偶发 O(N) 搬运 |
选型看访问模式:按下标随机访问多 → 数组;头部/中部插入删除多 → 链表。
五、小结
| 概念 |
一句话 |
证据 |
| 双长度 |
size 是元素数,items.length 是容量 |
size = 20 时容量 32 |
| 倍增扩容 |
满了把容量乘 2,不是加常数 |
20 次扩容覆盖 100 万元素 |
| 均摊分析 |
总代价摊到每次操作,得到常数 |
平均搬运 1.049 次/元素 |
| 线性扩容代价 |
每次 +1 会退化成 O(N²) |
总搬运 499999500000 次 |
| 选型 |
随机访问选数组,插删密集选链表 |
取下标 O(1) vs O(N) |
三条能带走的:
- 均摊分析看的是「一串操作的总代价」,不是「单次最坏代价」。 单次可能很贵,但贵的那几次被摊薄后是常数。
- 容量的增长方式决定了复杂度。 乘一个常数得 O(1) 均摊;加一个常数得 O(N) 均摊。差别只在一个字符,量级差一个次方。
size 与 capacity 必须分开。 混用这两个概念,是动态数组实现里最常见的一类 bug。