02. 数组与动态数组

0. 本章先解决什么问题

数组是最基础、最重要的数据结构。很多复杂结构底层都离不开数组。

本章要解决:

• 数组为什么能按下标 O(1) 访问?
• 连续内存为什么让数组 cache 友好?
• 数组插入删除为什么可能慢?
• 动态数组如何扩容?
• 扩容为什么是摊还 O(1),但单次可能很贵?
• 数组适合什么实际问题,不适合什么问题?

数组的核心特征是:

连续存储 + 固定元素大小 + 地址可计算

这张图怎么读

这张图抓住动态数组最容易被误解的一点:容量没满时,尾部追加只是一次写入;容量满时,追加会变成“申请更大连续空间 + 复制旧元素 + 写入新元素”。所以“摊还 O(1)”说的是长期平均成本,不代表每一次追加都一样便宜。

1. 数组的存储形态

数组把元素连续放在内存里:

index:  0   1   2   3   4
data:  [a] [b] [c] [d] [e]

如果每个元素占 size 字节,数组起始地址是 base,那么:

第 i 个元素地址 = base + i * size

这就是数组随机访问快的根本原因。

CPU 不需要从头走到第 i 个元素,只要做一次地址计算。

2. 数组操作成本

数组的优势是访问和遍历。

数组的弱点是中间结构变化。

3. 数组为什么 cache 友好

CPU 访问内存时,通常会把一整条 cache line 搬进 Cache。

数组连续:

[a0][a1][a2][a3][a4][a5]

访问 a0 后,a1、a2 可能已经在 Cache。

所以顺序遍历数组通常非常快。

这就是:

空间局部性

数组在实际性能上经常超过理论复杂度相同但内存分散的结构。

4. 静态数组和动态数组

静态数组容量固定:

capacity = 10

放满后不能继续插入,除非重新申请更大空间。

动态数组在外部看起来能增长,底层通常做:

如果容量足够:
直接写到末尾

如果容量不够:
申请更大数组
复制旧元素
释放旧空间
插入新元素

所以动态数组并不是“真的无限增长”,它是用扩容模拟增长。

5. 扩容策略

常见扩容是按倍数增长,比如 2 倍。

4 -> 8 -> 16 -> 32

如果每次只加 1:

4 -> 5 -> 6 -> 7

每次满了都要复制大量元素,成本太高。

倍增的好处是:

• 扩容次数少。
• 追加操作摊还接近 O(1)。

代价是:

• 可能有未使用容量。
• 扩容那一次有峰值成本。

6. 摊还 O(1) 和单次 O(n)

动态数组尾部追加常说是摊还 O(1)。

含义:

多数追加很便宜
少数追加触发扩容很贵
把扩容成本分摊到很多次追加上,平均接近 O(1)

但对延迟敏感场景,要注意:

触发扩容的那一次仍然可能 O(n)

如果你不希望运行中突然扩容,可以提前预留容量。

边界条件:摊还快不等于尾延迟稳定

摊还分析关心长期平均成本,但系统性能还关心尾延迟。动态数组扩容会同时带来几种峰值:

如果场景是批处理,偶尔扩容通常可以接受。
如果场景是实时请求路径,扩容峰值可能直接变成 P99 抖动。

常见治理方式:

所以“动态数组 append 是 O(1)”只能回答吞吐平均,不足以回答延迟峰值。

7. 插入和删除为什么慢

在数组中间插入:

[a][b][c][d]
插入 x 到 index 1

[a][ ][b][c][d]
x

需要把 b,c,d 后移。

删除中间元素:

[a][b][c][d]
删除 b

[a][c][d]

需要把 c,d 前移。

所以数组适合:

多读、多遍历、尾部追加

不适合:

频繁在中间插入删除

8. 有序数组

如果数组保持有序,查找可以用二分:

查找 O(log n)

但插入仍然要移动元素:

找到插入位置 O(log n)
移动元素 O(n)
总成本 O(n)

所以有序数组适合:

• 数据基本静态。
• 查询多,插入少。
• 需要顺序遍历。
• 需要范围扫描。

不适合频繁更新的大集合。

9. 多维数组和行优先

二维数组本质上仍然存成一维连续空间。

常见行优先布局:

matrix[row][col]
地址 = base + (row * cols + col) * element_size

按行遍历:

for row:
  for col:

通常比按列跳着访问更 cache 友好。

这解释了矩阵计算中访问顺序的重要性。

10. 常见坑

长度表示已有元素个数。容量表示底层能容纳多少元素。

size <= capacity

11. 联系实际:什么时候选数组

优先考虑数组或动态数组的场景:

1. 需要按下标快速访问。
2. 需要顺序遍历大量数据。
3. 数据量变化主要发生在尾部。
4. 数据结构要 cache 友好。
5. 需要紧凑内存。
6. 数据基本静态,查询远多于插入删除。

谨慎使用数组的场景:

1. 频繁头部或中间插入删除。
2. 数据大小不可预测且扩容峰值不可接受。
3. 元素很大且经常复制。
4. 需要按 key 快速查找。

小实验:手算一次扩容成本

假设动态数组初始容量是 4,扩容策略是容量翻倍。现在连续 append 17 个元素。

可以把每次操作写成账本:

17 次 append 里,真正因为扩容复制的元素总数是:

4 + 8 + 16 = 28

如果只看第 17 次,它很贵;如果看 17 次整体,复制成本被分摊到了多次 append 上。这就是摊还分析的直觉。

排障卡:为什么追加偶尔会突然慢一下

当一个程序在不断往动态数组里追加数据时,如果你观察到“绝大多数 append 很快,偶尔有一次明显变慢”,不要只怀疑算法复杂度写错。可以按这个顺序检查:

1. 当前 size 是否刚好接近 capacity。
2. 本次操作是否触发扩容和整段复制。
3. 元素本身是否很大,复制是否带来额外内存带宽压力。
4. 扩容时是否需要申请一块更大的连续空间,导致分配器成本上升。
5. 如果延迟峰值不可接受,是否能提前预留容量,或者改用分块结构。

这个问题在日志缓冲、批量收集、构建临时结果集、读取大文件时都可能出现。数组的平均性能很好,但实时性分析要盯住扩容峰值。

手推:中间插入为什么要搬动后半段

数组要求元素连续存放。假设:

index: 0 1 2 3 4
value: A B C D E

现在要在 index 2 插入 X,结果应是:

A B X C D E

为了给 X 腾位置,原来的 C、D、E 都要向右移动:

E -> index 5
D -> index 4
C -> index 3
X -> index 2

如果从左往右搬:

C 先覆盖 D
D 的原值丢失

所以移动顺序还必须从尾部往前。这里有两个成本:

这就是为什么数组适合尾部追加和按下标访问,但不适合频繁在头部或中间插入。

边界条件:预留容量解决扩容,不解决中间移动

提前 reserve 可以避免多次扩容复制,但它不能改变数组连续布局带来的移动成本。

如果容量足够:

capacity 足够,不需要申请新数组

在头部插入仍然要移动所有已有元素:

n 个元素整体右移一格

所以优化数组性能要先区分:

慢在扩容复制?
还是慢在插入/删除导致的元素移动?

前者可以通过预留容量、分块增长缓解;后者通常要换访问模型,比如队列、链表、树、间接索引或分段结构。

12. 学完本章你能解决什么问题

学完这一章,你应该能解决或开始分析这些问题:

1. 数组为什么能 O(1) 按下标访问?
2. 连续内存为什么让数组遍历快?
3. 动态数组如何扩容?
4. 尾部追加为什么是摊还 O(1),但扩容那次是 O(n)?
5. 中间插入删除为什么需要移动元素?
6. 有序数组适合什么场景?
7. 为什么二维数组遍历顺序会影响性能?
8. 实际需求中什么时候应该优先选数组?

数组是很多结构的底层地基。理解数组,就理解了地址计算、连续存储、扩容和缓存友好性的核心。

延伸阅读

• ArrayList
• from - zero · data-structures