Array
数组是一种线性结构，由连续内存空间存储相同类型元素的集合
Array = 一段连续内存 + 固定步长 + 常数时间寻址
首元素索引为0
address(i) = base_address + i * element_size
Cache友好
[0] [1] [2] [3] [4]
├─────┼─────┼─────┼─────┼─────┤
│ 10 │ 20 │ 30 │ 40 │ 50 │
└─────┴─────┴─────┴─────┴─────┘
1000 1004 1008 1012 1016
Fixed Array
长度在编译期或创建时就确定，之后永远不变的内存块
int a[1024];
特点：
- 长度不可变
- 地址永远不变
- 零额外开销
- 行为完全可预测
- Cache/SIMD/DMA友好
性能特点：
| 操作 | 成本 | 说明 |
|---|---|---|
| 随机访问 | O(1) | 通过索引 |
| 增删（尾部） | O(1) | 无开销 |
| 增删（中间） | O(n) | 需要移动后方元素 |
| 查找（有序） | O(log n) | 二分查找 |
| 查找（无序） | O(n) | 遍历 |
致命代价：
- 长度不可变：不确定最大规模会导致要么浪费内存，要么直接炸
- 越界
- 不适合动态数据
适用场景：
- 数据规模确定
- 实时系统
- 内存布局敏感
- 高频访问
不适合：
- 数据规模未知
- CRUD型业务
- 频繁增删
哲学意义：放弃灵活性，换取绝对可控
Dynamic Array
动态数组，在静态数组的基础上实现了扩容
核心
┌──────────────┐
│ data* │ -> 指向一段连续内存
├──────────────┤
│ size │ -> 当前元素个数
├──────────────┤
│ capacity │ -> 已分配容量
└──────────────┘
扩容
扩容的核心问题：内存连续性
数组在内存中必须是连续存储的，这是其O(1)随机访问的基础，但也正是扩容昂贵的主要原因
内存示意图
初始数组（已满）：
┌───┬───┬───┬───┐
│ 1 │ 2 │ 3 │ 4 │
└───┴───┴─┬─┴───┘
地址:1000-1015 16字节
想要扩容到8个元素，但1000-1023地址可能已被占用：
┌───┬───┬───┬───┬───┬───┬───┬───┐
│ 1 │ 2 │ 3 │ 4 │ ? │ ? │ ? │ ? │
└───┴───┴───┴───┴───┴───┴───┴───┘
无法原地扩展
扩容过程
伪代码
void expand_array(int** arr, int* capacity) {
// 1. 重新计算容量（通常翻倍）
int new_capacity = *capacity * 2;
// 2. 申请新的连续内存空间
int* new_array = malloc(new_capacity * sizeof(int));
// 3. 检查分配是否成功
if (new_arr = NULL) {
// 内存不足，扩容失败
return;
}
// 4. 复制所有元素（O(n)操作）
for (int i = 0; i < *capacity; i++) {
new_arr[i] = (*arr)[i];
}
// 5. 释放旧内存
free(*arr);
// 6. 更新指针和容量
*arr = new_arr;
*capacity = new_capacity;
}
总成本 = 分配内存 + 复制n个元素 + 释放内存
成本分析
1. 内存分配成本
- 操作系统查找足够大的连续空闲内存块（可能需要遍历空闲链表）
- 分割内存块（如果找到的块比需要的大）
- 更新内存分配表
- 如果物理内存不足，可能触发缺页中断、页面置换
- 如果找不到连续块，可能触发内存碎片整理
频繁扩容会导致大量内存碎片，小碎片无法被利用，总空闲内存虽然很多，但没有连续的大块内存
2. 数据复制成本
假设数组有100万个元素，每个元素8字节
初始数组大小为8MB
需要扩容时
- 分配新内存：16MB
- 复制8MB数据
即使现代CPU很快，这也是显著的延迟
内存带宽限制
如果内存带宽是20GB/s, 复制8MB的数据大约为0.4ms
但实际还要考虑
- 缓存未命中
- TLB未命中
- 内存控制器排队
3. 缓存不友好
// 复制大数组会污染缓存
int* old_array = ...; // 在缓存中
int* new_array = malloc(new_size);
// 复制过程
for (int i = 0; i < old_size; i++) {
// 1. 从old_array[i]读取（可能缓存命中）
// 2. 写入new_array[i]（新内存，肯定缓存未命中）
// 3. 这会逐出缓存中的其他有用数据
new_array[i] = old_array[i];
}
扩容策略
翻倍扩容（常用）
capacity *= 2
插入n个元素的摊还分析：
总复制次数 = 1 + 2 + 4 + … + n/2 约等于 n
平均每个元素复制约2次
摊还时间复杂度 = O(1)
固定增量扩容
capacity += 10
插入n个元素的复制次数：
总复制约等于 10 + 20 + 30 + … 约为 O(n^2)
平均每个元素复制O(n)次，性能差
对比
插入1,000,000个元素
| 策略 | 总复制次数 | 平均每个元素复制次数 |
|---|---|---|
| 固定 +10 | ～50,000,000,000 | ～50,000 |
| 固定 +100 | ~5,000,000,000 | ~5,000 |
| x2 | ~2,000,000 | ~2 |
| x1.5 | ~3,000,000 | ~3 |
翻倍策略虽然会浪费一些空间，但时间效率最高
扩容的摊还分析（Amortized Analysis）
为什么说摊还时间复杂度是O(1)？
示例：
插入序列：第1,2,3,…,n个元素
扩容发生时刻：容量=1,2,4,8,…,直到>=n
复制成本：
插入第1个元素：复制0个（初始容量1）
插入第2个元素：复制1个（扩容到2）
插入第3个元素：复制2个（扩容到4）
插入第5个元素：复制4个（扩容到8）
…
插入第2^(k+1)个元素：复制2^k个（扩容到2^(k+1)）
总复制次数 = 1 + 2 + 4 + … + 2^k < 2n
平均每个元素复制 < 2 次
所以即使单次扩容是O(n)，n次插入的平摊成本是O(1)
优化策略
- 预分配：一次性分配，不存在扩容问题
- 使用更合适的数据结构：如果频繁增删，数组不是最优选择
- 批量操作：避免多次单元素插入，这会触发多次扩容；批量添加，一次扩展
动态数组的代价
指针/引用失效
动态数组在扩容时会重新分配内存，原内存被释放，所有指向旧内存的指针/引用全部失效
这是动态数组导致的一种特性，最好的做法就是避免碰它，不要妄图使用或修补它实时系统不友好
内存浪费（trade-off）
Multidimensional Array
多维数组在逻辑上是多维的，但在物理内存中始终是一维连续存储的
- 逻辑视图（三维数组）
int cube[2][3][4] = {
{{1,2,3,4}, {5,6,7,8}, {9,10,11,12}},
{{13,14,15,16}, {17,18,19,20}, {21,22,23,24}}
};
- 物理视图（内存中连续存储）
内存地址：[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24]
内存布局模式
- Row Major
- Column Major
二维数组A[M][N]可以想象成一个M行N列的表格
A[0][0] A[0][1] A[0][2] ... A[0][N-1]
A[1][0] A[1][1] A[1][2] ... A[1][N-1]
...
A[M-1][0] ... A[M-1][N-1]
内存是线性的，所以二维数组必须展开成一维存储。这就是 Row Major 和 Column Major的区别
row-major 行优先/行主序
C/C++/Python等大多数语言使用
按行存储，先把第一行存完，再存第二行…
二维数组示例
int matrix[3][4] = {
{1, 2, 3, 4},
{5, 6, 7, 8},
{9, 10, 11, 12}
};
内存布局
┌─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┐
│00 │01 │02 │03 │10 │11 │12 │13 │20 │21 │ 22 │23 │
├─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┤
│ 1 │ 2 │ 3 │ 4 │ 5 │ 6 │ 7 │ 8 │ 9 │ 10 │ 11 │ 12 │
└─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┘
地址计算公式：对于A[M][N]，元素A[i][j]的线性地址计算：
$addr(A[i][j])=base_addr+(i*N+j)*element_size$
优点：遍历数组时按行顺序访问缓存友好（CPU缓存行连续）
column-major 列优先/列主序
Fortran/Matlab/Julia使用
按列存储，先存第一列，再存第二列…
- Fortran示例
INTEGER :: matrix(3,4) = RESHAPE([1,2,3,4,5,6,7,8,9,10,11,12], [3,4])
- 内存布局（按列展开）
┌─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┐
│00 │10 │20 │01 │11 │21 │02 │12 │22 │03 │13 │23 │
├─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┤
│ 1 │ 2 │ 3 │ 4 │ 5 │ 6 │ 7 │ 8 │ 9 │ 10 │ 11 │ 12 │
└─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┘
地址计算公式：
$addr(A[i][j])=base_addr+(j*M+i)*element_size$
优点：对按列遍历的算法更高效，比如矩阵乘法的某些实现
为什么行主序更“缓存友好”
- CPU的特点
- cache line 机制
- 局部性
- 行主序的优势
- 二维数组在C/C++中是行主序排列的
- 当按行遍历数组时，逻辑访问和内存物理顺序一致
- 结果：缓存命中率高，CPU一次加载一个cache line, 就可以顺序访问多个元素
- 列主序的劣势（在行主序语言中）
- 如果按列遍历二维数组，访问的元素在内存中不是连续的
- 每次访问可能跨越多个cache line, 导致频繁的缓存未命中
- CPU必须不断从主存加载数据，速度大幅下降
不同维度的地址计算
通用公式推导
对于n维数组：arr[d₁][d₂]...[dₙ]
行主序：
元素arr[i₁][i₂]...[iₙ]的偏移量：
offset = ((...((i₁ × d₂ + i₂) × d₃ + i₃)...) × dₙ + iₙ) × element_size
列主序：
offset = ((...((iₙ × dₙ₋₁ + iₙ₋₁) × dₙ₋₂ + iₙ₋₂)...) × d₁ + i₁) × element_size