03.数组深入浅出分析

数据结构里最基础、也最被低估的一种。看似平平无奇，却是动态数组、栈、队列、堆、矩阵、图、哈希表等几乎所有高级结构的底层物理承载。本篇从一个真实事故切入，彻底讲透它。

---

目录指引与导读

阅读建议：先抓住"连续内存 + 下标计算"这条主线，再读各节细节会更有体感。

• 01. 从工作案例说起
  • 1.1 中间插入的事故
  • 1.2 全篇结构导航
• 02. 数组的本质剖析
  • 2.1 定义与硬约束
  • 2.2 栈堆内存分配
  • 2.3 访问与查找区别
  • 2.4 缓存与SIMD优势
• 03. 数组的使用场景
  • 3.1 业务侧典型场景
  • 3.2 哪些容器底层数组
  • 3.3 各语言数组速览
• 04. 线性表与非线性
  • 4.1 线性表两种实现
  • 4.2 非线性数组扁平化
• 05. 随机访问的原理
  • 5.1 地址计算公式
  • 5.2 硬件专门指令
  • 5.3 验证内存连续
  • 5.4 各语言越界检查
• 06. 插入低效的原因
  • 6.1 插入复杂度分析
  • 6.2 三种插入优化思路
• 07. 删除低效的原因
  • 7.1 经典删除两优化
• 08. 数组与容器对比
  • 8.1 原生数组核心差异
  • 8.2 必用原生数组场景
  • 8.3 安卓特化SparseArray
• 09. 下标为何从0开始
  • 9.1 下标即内存偏移
  • 9.2 半开区间论证
  • 9.3 各语言起始选择
• 10. 多维数组与扩容
  • 10.1 行优先列优先
  • 10.2 扩容倍数取舍
  • 10.3 客户端广泛应用
  • 10.4 数组解题四模式
  • 10.5 环形数组
• 11. 案例回扣与收获
• 12. 思考题深度练
• 13. 课后作业实战
• 14. 进阶专题与延伸

---

01. 从工作案例说起

1.1 中间插入的事故

某个后台服务需要每次请求时，把一条新记录插到"最近操作列表"的最前面（首位是最新）。最初的实现：

LinkedList<Op> recent = new LinkedList<>();

void onRequest(Op o) {
    recent.addFirst(o);           // O(1)，选 LinkedList 的原因
    if (recent.size() > 200) recent.removeLast();
    pushToClient(recent);          // 问题在这
}

听起来很合理——LinkedList 的头插 O(1)。但 pushToClient 里做了这么一件事：

for (int i = 0; i < recent.size(); i++) {
    buffer.append(recent.get(i).toString());   // 链表的 get(i) = O(N)
}

LinkedList.get(i) 要从头遍历 i 次，整个循环退化成 O(N²)。200 条时还能跑，放到一个热点用户（实际会堆到 2000+）上，P99 从 5ms 直飙 200ms。

改动：LinkedList → ArrayDeque（底层是循环数组），头插仍 O(1)，随机访问退化到 O(N) 但这里根本不需要；或者干脆把 recent.get(i) 换成 for-each。问题根除。

这件事让我真正理解数组的核心价值：不是"能动态增长"，而是 连续内存 + 下标直算地址，这两个硬件级特性决定了它的优劣。本篇把这件事说透。

1.2 全篇结构导航

flowchart LR
    A[01.工作案例] --> B[02.数组的本质]
    B --> C[03.使用场景]
    C --> D[04.线性表vs非线性表]
    D --> E[05.随机访问原理]
    E --> F[06.插入开销]
    F --> G[07.删除开销]
    G --> H[08.数组vs容器]
    H --> I[09.为何下标从0]
    I --> J[10.多维数组+均摊扩容]
    J --> K[11.回扣+收获]

---

02. 数组的本质

2.1 定义与两个硬约束

数组（Array） 是一种线性数据结构，用一组 连续的内存空间 存储一组 类型相同 的数据。

两个硬约束缺一不可：

• 连续内存 → 地址可计算 → 随机访问 O(1)
• 类型相同 → 每个元素大小一致 → 无需 padding，也能直接 base + i × size 寻址

为什么"类型相同"是硬约束

设想若允许混合类型：

[int 4B][double 8B][char 1B][long 8B]...

想访问第 i 个元素，就得从头扫描累加每个元素的长度——退化成 O(N)。所以像 Python 的 list 虽然外观上能混存，底层实际存的都是指向对象的统一大小（8B）指针，真正的对象分散在堆上。这也是 Python list 远慢于 NumPy array 的根本原因之一：NumPy 直接存 double[]，下标即可直接寻址；list[i] 要先拿到指针再解引用，多一次 cache miss。

Python list:     ┌→ int 42 (堆)
[ptr][ptr][ptr]──┼→ str "hi" (堆)
                 └→ list[...] (堆)
NumPy  ndarray:
[42.0][3.14][9.8][1.6]...   ← 连续 double，零跳转

数组的另一种硬约束：对齐（Alignment）

现代 CPU 要求 N 字节的基本类型必须存放在 N 字节对齐的地址（int 在 4 字节对齐、double 在 8 字节对齐）。数组天然保证对齐——只要首地址对齐，后续元素因步长一致也自动对齐。这是为什么 int[] 永远比 ArrayList<Integer> 快一截：后者每个元素都是 Integer 对象，对象头 + 指针 + padding 让访问偏移不再是一条 MOV 指令能搞定的。

2.2 栈堆内存分配

栈分配（~1ns，自动释放，大小编译期确定）：
┌─────────────┐
│ int arr[5]  │
│ [0][1][2][3][4]
└─────────────┘

堆分配（~100ns，手动/GC释放，运行期决定大小）：
┌──────┐       ┌─────────────────┐
│ *arr │──ptr─→│ [0][1][2][3][4] │
└──────┘       └─────────────────┘

各语言差异：

语言	默认位置	机制
C/C++	栈或堆，程序员控制	int a[N] 栈；malloc 堆
Java	堆	所有对象都在堆，GC 回收
Go	编译器逃逸分析决定	不逃逸→栈；否则→堆
Swift	小数组内联，大的上堆	值类型 + COW

栈 vs 堆的实测差距

// 栈上分配 + 释放：几乎零开销
void stack_test() {
    int arr[1000];          // 仅仅把 rsp 减 4000
    arr[500] = 42;
}   // 自动释放：rsp 加回去

// 堆上分配：malloc 内部走空闲链表/伙伴系统，锁竞争 + 元数据
void heap_test() {
    int* arr = malloc(1000 * sizeof(int));  // ~50-200ns
    arr[500] = 42;
    free(arr);                              // ~50-100ns
}

经验值：一次 malloc+free 约为 100ns，一次 stack 分配几乎为 0。这是为什么高性能代码（HFT、游戏引擎、编解码器）对"不在热路径上 malloc"有铁律——很多底层项目直接用 对象池 / arena allocator 预分配一大块，再在里面"逻辑切片"。

Go 的逃逸分析示例

// 不逃逸：栈分配，零 GC 压力
func sum() int {
    arr := [1024]int{}      // 栈上数组
    for i := range arr { arr[i] = i }
    s := 0
    for _, v := range arr { s += v }
    return s
}

// 逃逸：因为返回了切片指向的数据，编译器被迫放堆上
func build() []int {
    arr := make([]int, 1024)    // 堆分配
    return arr
}

验证：go build -gcflags="-m" main.go 会打印 moved to heap: arr。工程上能避免逃逸就避免——减少 GC 压力在高并发服务里能降 P99 一个量级。

2.3 访问 vs 查找：两个常被混淆的概念

操作	输入	复杂度
访问（Access）arr[i]	已知下标	O(1)
查找（Search）find(v)	已知值	无序 O(N)、有序 O(log N)
包含（Contains）	判断是否存在	同查找

"数组查找 O(1)" 是错的。正确说法：数组的随机访问是 O(1)。

三种"访问"的边界案例

操作	示例	时间
随机访问已知下标	arr[13]	O(1)
访问最后一个元素	arr[arr.length - 1]	O(1)（仍是下标访问）
按值查找无序数组	indexOf(v)	O(N)
按值查找有序数组	二分查找	O(log N)
访问不定长元素数组	如 UTF-8 字符串第 i 个字符	O(N)（要从头解码）

最后一行容易踩坑——Go 的 s[i] 拿到的是第 i 个字节不是第 i 个字符，因为 string 是 UTF-8 变长编码，"按字符下标"需要 O(N) 扫描。Python 3 的 str 则在内部切换多种定长编码（PEP 393），s[i] 才是真正 O(1)。

2.4 缓存与SIMD优势

现代 CPU 每次加载一整条 缓存行（Cache Line，通常 64B）。顺序数组遍历，首次 miss 之后接下来十几个元素全部缓存命中；链表因为离散，基本每跳都 miss。

数组遍历：
[a₀][a₁][a₂]...[a₇]  ← 一次缓存加载 8 个 int
命中率 > 95%

链表遍历：
[node₀]   [node₃]   [node₁]   ← 每节点位置不可预测
命中率 ≈ 0%，每次 miss 约 100ns

连续内存还让编译器可以生成 SIMD 指令（AVX2 一次处理 8 个 int），速度再翻数倍。NumPy 能比 Python 原生 list 快 100 倍，根源就在这。

缓存层级与实测耗时

CPU 核心──L1 32KB──L2 256KB──L3 几~几十MB──DRAM 几~几十GB
        ~1ns     ~4ns      ~10ns         ~100ns

跑一段 JMH：对 1 亿个 int 求和，分别用数组和链表：

@Benchmark
public long sumArray(ArrayState s) {
    long sum = 0;
    for (int v : s.array) sum += v;
    return sum;
}

@Benchmark
public long sumList(ListState s) {
    long sum = 0;
    for (int v : s.list) sum += v;
    return sum;
}

典型结果（M1/i7 量级）：

实现	耗时	miss 率	说明
int[]	~40ms	< 5%	顺序访问 + SIMD 自动向量化
ArrayList<Integer>	~150ms	~15%	装箱 + 指针跳一次
LinkedList<Integer>	~900ms	> 60%	每次 next 都 miss

数组跟链表在"理论复杂度相同"的情况下，实测差 20 倍——这就是现代 CPU 给数组的红利。

SIMD 的威力

// 普通写法：每次加一个 int
for (int i = 0; i < n; i++) c[i] = a[i] + b[i];

// AVX2 手写：一次加 8 个 int
for (int i = 0; i < n; i += 8) {
    __m256i va = _mm256_loadu_si256((__m256i*)(a + i));
    __m256i vb = _mm256_loadu_si256((__m256i*)(b + i));
    __m256i vc = _mm256_add_epi32(va, vb);
    _mm256_storeu_si256((__m256i*)(c + i), vc);
}
// 吞吐量 8 倍提升，前提是数组连续且对齐

现代编译器会对简单循环自动向量化（autovectorization），但前提仍然是连续、对齐、类型一致——三者缺一，SIMD 就没法用。所以数组天生就是 SIMD 的最佳载体。

---

03. 数组的使用场景

3.1 谁在用数组

业务层："按索引存取 + 按顺序遍历" 为主的场景：

业务	为何用数组
音视频帧缓冲	零拷贝 / DMA / SIMD 都要求连续内存
图像像素处理	二维矩阵天然数组
游戏地图格子	map[x][y] 坐标 O(1)
时间序列 / K 线	等间距采样 + 范围查询
列表分页展示	按 index 随机访问

3.2 哪些容器底层数组

集合	底层	备注
Java ArrayList	Object[]	1.5 倍扩容
Java ArrayDeque	循环数组 + 位运算代替取模	容量必须 2 的幂
C++ vector	T*	2 倍扩容（GCC）
Go slice	指向数组的 header	动态扩容
Python list	PyObject**	约 1.125 倍
Rust Vec<T>	RawVec	2 倍
Java PriorityQueue	Object[]	堆的数组实现
String	char[] / byte[]	—

ArrayDeque 那个细节值得一提：

// (head - 1) & (len - 1) 等价于对 2 的幂取模，但只需 1 个时钟周期
head = (head - 1) & (elements.length - 1);

取模要 20~40 周期，这就是为什么它强制容量是 2 的幂。

Go slice 的三元组结构

Go 的 slice 并不是数组本身，而是一个 24 字节的结构体，指向底层数组：

type slice struct {
    data unsafe.Pointer   // 指向底层数组
    len  int              // 当前长度
    cap  int              // 容量
}

s := make([]int, 5, 10)   // len=5, cap=10
s2 := s[1:3]              // 新 header，但 data 指向 s 的数组第 1 个元素
s2[0] = 99                // 也会改到 s[1]——共享底层数组

这个设计让 切片（slice）是廉价操作（只是复制 header），但也带来"内存意外泄漏"的坑——只要持有一个小切片，就无法 GC 掉整个大数组。标准做法：用 append([]T(nil), s...) 或 slices.Clone 显式复制。

Rust Vec 的三元组

pub struct Vec<T> {
    ptr: NonNull<T>,    // 指向堆
    len: usize,
    cap: usize,
}   // 同样 24 字节（64-bit）

Rust 的 Vec 在 drop 时会保证释放堆上的内存；移交所有权（move）时只是 memcpy 这 24 字节 header——零成本抽象的典型代表。

3.3 各语言数组速览

语言	声明	大小	边界检查	特性
C	int a[10]	固定	❌	不检查越界（缓冲区溢出根源）
Java	int[] a = new int[10]	固定	✅	抛 AIOBE
Swift	[Int]	动态	✅	值类型 + COW
Go	[10]int 数组 / []int 切片	前者固定后者动态	✅	数组传参拷贝
JS	Array	动态	❌	越界返 undefined，稀疏时退化为哈希表
Rust	[i32; 10]	固定	✅	编译期保障

Java 一维 vs 二维数组的重要差异

Java int[] 是真正连续内存，但 int[][] 不是——它是"数组的数组"：外层是指针数组，每一行都是独立的堆对象：

Java int[3][4]:
外层 int[][] ──┬──→ int[4] [1][2][3][4]      （堆位置 A）
              ├──→ int[4] [5][6][7][8]      （堆位置 B，与 A 不连续）
              └──→ int[4] [9][10][11][12]   （堆位置 C）

C/C++ int a[3][4]:
[1][2][3][4][5][6][7][8][9][10][11][12]     （真正 48 字节连续）

后果：遍历 arr[i][j] 时，每换一行就可能 cache miss；C/C++ 遍历按行走则几乎全命中——这是 Java 数值计算比 C/C++ 慢 2-3 倍的主要原因之一。要追平只能用 int[]（一维）手工索引 arr[i * cols + j]，或走 off-heap（ByteBuffer.allocateDirect）。Project Panama 的 MemorySegment（JDK 21+）和 Valhalla 的 value class 正是冲着这个痛点去的。

---

04. 线性表与非线性表

4.1 线性表：逻辑概念的两种实现

线性表是逻辑结构——元素排成一条线。物理上有两种实现：

顺序存储（数组）：
[A][B][C][D][E]    连续内存，下标定位

链式存储（链表）：
[A|→] ... [B|→] ... [C|∅]    指针串联

维度	数组	链表
存储密度	高	低（每节点多一个指针）
随机访问	O(1)	O(N)
插入删除（已定位）	O(N)	O(1)
空间灵活性	需预分配	按需
缓存友好	极好	极差

4.2 非线性数组扁平化

完全二叉树用数组存：

       1            index: 0 1 2 3 4 5 6
      / \           value: 1 2 3 4 5 6 7
     2   3
    / \ / \         parent(i) = (i-1)/2
   4  5 6  7        left(i)   = 2i+1
                    right(i)  = 2i+2

省掉每个节点 16B 的指针，缓存友好——PriorityQueue、堆排序、Go heap 包都是这么做的。

非线性结构	数组实现	应用
完全二叉树 / 堆	层序存	PriorityQueue
图（稠密）	邻接矩阵 adj[i][j]	Floyd
并查集	parent[i]	Kruskal
线段树	一维（4N 空间）	区间查询
Trie	children[node][char]	自动补全

---

05. 随机访问的原理

5.1 地址计算公式

一维：addr(a[i])       = base + i × size
二维：addr(a[i][j])    = base + (i × cols + j) × size（行优先）
三维：addr(a[i][j][k]) = base + (i × d₂d₃ + j × d₃ + k) × size

5.2 硬件为这事做过专门指令

; x86：一条指令完成基址+变址+缩放
mov eax, [rbx + rcx * 4]    ; base=rbx, index=rcx, size=4

; ARM：同样一条指令
LDR R0, [R1, R2, LSL #2]

ALU 一个时钟周期搞定。这就是 O(1) 的硬件根基。

三种寻址模式的生成对比

int a[N], *p;

// 模式 1：直接下标
int x = a[i];
// 编译后：mov eax, [rbx + rcx*4]    一条指令

// 模式 2：指针走
p = a; for (i=0; i<N; i++) { use(*p); p++; }
// 编译后内层：mov eax, [rbx]; add rbx, 4   两条

// 模式 3：链表 next
struct Node { int v; Node* next; };
for (Node* p = head; p; p = p->next) use(p->v);
// 编译后内层：mov eax, [rbx]; mov rbx, [rbx+8]   两条，但 rbx 依赖前一次读

模式 3 里 rbx 依赖前一次读取——这是一个"load-to-use 依赖链"，CPU 的乱序执行失效，流水线被迫串行。这就是链表遍历"哪怕命中 cache"也比数组慢的微观原因。

分支预测的影响

// 数组遍历：循环边界 i<N 可被分支预测器完美预测（除最后一次 miss）
for (int i = 0; i < N; i++) sum += a[i];

// 链表遍历：p != NULL 的判断要到读完 p->next 才能知道
while (p) { sum += p->v; p = p->next; }  // 每次都是"等到下一轮才知道该走哪"

这一层是大多数教材不提的"数组胜利"——不止 cache，连分支预测都偏向数组。

5.3 验证内存连续

int arr[5] = {10, 20, 30, 40, 50};
for (int i = 0; i < 5; i++)
    printf("a[%d] addr=%p offset=%ld\n",
           i, &arr[i], (char*)&arr[i] - (char*)&arr[0]);
// 偏移严格 0, 4, 8, 12, 16

5.4 各语言越界检查

语言	越界	性能损耗
C/C++	未定义行为	0
Java / Swift / Rust / Go	抛异常 / panic	3%~5%（JIT 可消除大部分）
JS	返 undefined	0

越界检查的 JIT 消除

虽然"每次访问都检查"听起来很贵，但现代 JIT（HotSpot C2、Graal、V8 TurboFan）能识别"循环里 i 只在 [0, N) 变化"这种模式，把检查提到循环外（range-check elimination, RCE）：

for (int i = 0; i < arr.length; i++) {
    sum += arr[i];        // JIT 知道 i 永远不越界，移除检查
}

损耗因此从理论的 ~30% 降到实测的 3-5%。这就是为什么 Java 虽然比 C 慢，但不会慢出一个量级。

但一旦循环条件被掩盖（例如 for (int i=0; i < unknownFn(); i++)），RCE 就失效——所以写数值密集代码时，把循环上界固化成局部变量是个小技巧。

---

06. 插入低效的原因

6.1 插入复杂度分析

graph LR
    A[插入位置] --> B[末尾 O#40;1#41;]
    A --> C[中间 O#40;n#41;]
    A --> D[开头 O#40;n#41;]

平均代价 (1+2+...+n)/n = O(n)。

6.2 三种优化思路

① 无序数组的 O(1) 插入——尾部交换法

// 不要求保序时，把目标位置元素搬到末尾
void insertFast(int[] a, int size, int idx, int v) {
    a[size] = a[idx];   // 原值挪到末尾
    a[idx]  = v;        // 新值放进去
    // 2 次赋值，O(1)
}

② 用 System.arraycopy 代替手写 for

// 底层 memcpy/memmove，比 for 循环快 5~10 倍
System.arraycopy(arr, index, arr, index + 1, size - index);
arr[index] = value;

③ 分块数组（C++ std::deque 思路）

把大数组切成若干小块，块内数组、块间链表。插入只需在一个块里移 √N 个元素，整体 O(√N)。数据库 B+ 树本质上就是这思路的极致。

④ Gap Buffer（文本编辑器专用）

编辑器里光标附近频繁插入——emacs、VSCode 的底层 buffer 就是 gap buffer：

光标位置的 gap 是一段空闲区间，插入时直接写入 gap 并缩小 gap
[H][e][l][l][o][_][_][_][_][w][o][r][l][d]
              ↑          ↑
             光标         gap 结束
输入 'X'：
[H][e][l][l][o][X][_][_][_][w][o][r][l][d]

• 光标不动时插入 O(1)
• 光标移动 K 个字符要移动 K 个元素——但移动是"预摊"的，用户通常连续编辑一个区域
• 相比 ArrayList，在文本编辑场景下平均快 10 倍以上

⑤ memcpy vs memmove 的选择

System.arraycopy 内部会判断源和目标是否重叠：

• 不重叠用 memcpy（SIMD 加速）
• 重叠用 memmove（从后往前拷贝避免覆盖）

插入场景是重叠的（同一数组内搬移），所以实际走的是 memmove 路径——比 memcpy 稍慢但仍远快于手写 for。

---

07. 删除低效的原因

同插入，平均 O(N)，需要把后面的元素向前搬。

// ArrayList.remove(index) 核心
public E remove(int index) {
    E old = (E) elementData[index];
    int numMoved = size - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index + 1, elementData, index, numMoved);
    elementData[--size] = null;   // 置空帮助 GC
    return old;
}

7.1 两个经典优化

① 无序数组：末尾覆盖法，O(1)

void removeFast(int[] a, int idx, int size) {
    a[idx] = a[size - 1];   // 末尾覆盖目标位置
    // 逻辑 size--
}

游戏 ECS 架构大量用这招。

② 标记删除 + 批量整理

先打标记不搬数据，空间不够时再集中整理一次——这就是 JVM 标记清除 GC、数据库 MVCC 软删除、SSD FTL 的核心思想。

场景	标记方式	整理触发
JVM GC	可达性分析	内存阈值
数据库	is_deleted=1	vacuum
文件系统	inode 标记	trim
SSD	页级标记	垃圾块阈值

结论：数组的 O(1) 访问是绝对优势，O(N) 的插入删除是绝对代价——承认代价，再用"不保序 / memcpy / 分块 / 标记"四招优化。

批量删除的"双指针"模板

删除多个元素时不要一个个 remove——每次都 O(N)，总代价 O(N²)。用双指针一次走完：

// LeetCode 27: 原地移除所有值等于 val 的元素
int removeAll(int[] a, int val) {
    int write = 0;
    for (int read = 0; read < a.length; read++) {
        if (a[read] != val) a[write++] = a[read];
    }
    return write;    // 前 write 个元素是保留的，O(N) 一趟完事
}

这是数组"原地算法"的母模式——LeetCode 26、27、80、283 等题目都是它的变体。本质上是把 N 次 O(N) 的删除均摊成 O(1) 每次。

---

08. 数组与容器对比

8.1 原生数组核心差异

维度	原生数组	容器（ArrayList/vector/slice）
大小	固定	动态（扩容）
类型	原始类型（Java 免装箱）	对象类型（Java 需装箱）
便捷方法	无	add/remove/sort/stream
跨 JNI / 网络 IO	原生数组必需	不可用

8.2 什么时候必须用原生数组

1. JNI / FFI：跨语言调用必须传 byte[]
2. NIO ByteBuffer / Netty ByteBuf：网络 IO 缓冲
3. 音视频编解码：PCM / YUV 数据就是字节数组
4. Android Bitmap：像素数据 int[]
5. 密码学：AES 固定长度 byte 数组

8.3 安卓特化SparseArray

// 替代 HashMap<Integer, V>，底层是两个平行数组
SparseArray<String> map = new SparseArray<>();
map.put(1, "one");   // int[] keys + Object[] values，二分查找 O(log N)
// 比 HashMap<Integer,V> 省 40% 内存（无 Entry 对象、免装箱）

SparseArray / ArrayMap 的适用边界

场景	推荐	原因
N < 数百、不频繁插入	SparseArray/ArrayMap	省内存，查询足够快
N 大或插入频繁	HashMap	二分插入是 O(N)，大量插入会拖慢
key 不是基本类型 int	ArrayMap	SparseArray 只支持 int/long key

Android 官方建议：Adapter、布局相关的 int→Object 映射优先用 SparseArray；业务数据模型的 String→Object 映射用 ArrayMap。用错地方反而变慢。

Swift 的 ContiguousArray

Swift Array<T> 对 @objc 类型会透明桥接到 NSArray，带来少量开销；当你确定只在 Swift 侧用、且对性能敏感（比如图像处理），应该显式选 ContiguousArray<T>：

var pixels = ContiguousArray<UInt8>(repeating: 0, count: 1920*1080*4)
// 保证连续内存布局，适合 SIMD 操作

---

09. 为何下标从 0 开始

9.1 本质：下标是"偏移量"不是"序号"

arr[3] 的含义是"从首地址偏移 3 × size"。偏移量天然从 0 起，第一个元素的偏移恰好是 0。

从 1 开始需要每次寻址多一次减法：base + (i-1) × size。C 诞生在 PDP-11（几 MHz）上，这一次减法是实打实的开销。

9.2 Dijkstra 的半开区间论证

半开区间 [0, N) 的长度 = N - 0 = N，直观；闭区间 [1, N] 长度 = N - 1 + 1，容易出 off-by-one。

9.3 各语言起始选择

起始	语言	说明
0	C/C++/Java/Go/Rust/Swift/Kotlin/JS	主流
0（+负数语法糖）	Python	arr[-1] 即 arr[len-1]
1	Lua / MATLAB / Fortran	数学家思维

---

10. 多维数组与动态扩容

10.1 行优先 vs 列优先

逻辑 3×4 矩阵：
  col0 col1 col2 col3
row0 1   2    3    4
row1 5   6    7    8
row2 9   10  11  12

行优先（C/Java/Go/Swift）：[1,2,3,4,5,6,7,8,9,10,11,12]
列优先（Fortran/MATLAB）：[1,5,9,2,6,10,3,7,11,4,8,12]

重要实践：按存储顺序遍历。Java/C 写二维循环时，外层应该是 i（行），内层是 j（列）——反了缓存命中率能差 3~5 倍。

实测：行遍历 vs 列遍历

// 1024 x 1024 的 int 矩阵（4MB，远超 L2）
for (int i = 0; i < N; i++)
    for (int j = 0; j < N; j++) sum += a[i][j];   // 行优先：约 5ms

for (int j = 0; j < N; j++)
    for (int i = 0; i < N; i++) sum += a[i][j];   // 列优先：约 35ms

7 倍差距——纯粹因为缓存行利用率不同。行遍历每加载一个 cache line（64B = 16 个 int）用满 16 个元素；列遍历每加载一个 cache line 只用 1 个 int，然后就跳到下一行去了。

矩阵乘法的分块优化

教科书三重循环 C = A × B 的 i-j-k 顺序访问模式会导致 B 矩阵列遍历，性能极差。优化两步：

1. 循环重排 i-k-j：B[k][j] 在内层按行，缓存友好，速度可提升 3-5 倍；
2. 分块（tiling / blocking）：把矩阵切成缓存行大小的子块，先把子块加载进 L1 再算，再次提升 2-3 倍。

这正是 BLAS（Basic Linear Algebra Subprograms）、Intel MKL、OpenBLAS 等数值库的核心优化。同样的 O(N³) 算法，实现得好和实现得差能差 50 倍以上——说明复杂度分析只是下限，工程实现才是真正的胜负手。

10.2 扩容倍数取舍

容器	倍数	最坏空间浪费	N 次插入扩容次数
Java ArrayList	1.5×	33%	log₁.₅N
C++ vector (GCC)	2×	50%	log₂N
Go slice	<256: 2× ; ≥256: 1.25×	50%/20%	介于两者
Python list	~1.125×	12.5%	~8 logN

均摊 O(1) 证明（以 2 倍扩容为例）：

总拷贝 = 1 + 2 + 4 + 8 + ... + N = 2N - 1
N 次 append 总代价 = (2N - 1) 拷贝 + N 实际赋值 ≈ 3N
均摊每次 = 3N / N = O(1) ✓

实战建议：能预估数据量就指定初始容量，零扩容。

// 差：默认容量 10，插 1w 条扩容 ~24 次
List<String> a = new ArrayList<>();

// 好：一步到位
List<String> a = new ArrayList<>(10000);

10.3 数组在客户端的广泛应用

• Android RecyclerView.Adapter.getItemCount() / onBindViewHolder(position)：靠 List.get(position) 的 O(1) 随机访问
• iOS UITableView 的 cellForRowAt indexPath：同理
• 前端虚拟列表：Math.floor(scrollTop / itemHeight) 算出可见区间首尾 index，然后 data.slice(start, end)——数组 O(1) 访问是虚拟滚动的根基

10.4 数组解题四模式

模式	核心	典型题
双指针	一快一慢 / 左右夹逼	两数之和（有序）、移除元素、合并有序数组
原地哈希	用下标当哈希键	First Missing Positive、Find Duplicate
前缀和	预计算区间和	子数组和、区间更新
滑动窗口	可变窗口滑动	最大子数组和、最小覆盖子串

示例——三次反转实现旋转数组，空间 O(1)：

void rotate(int[] a, int k) {
    k %= a.length;
    reverse(a, 0, a.length - 1);
    reverse(a, 0, k - 1);
    reverse(a, k, a.length - 1);
}

10.5 环形数组（Ring Buffer）

"头删 + 尾插都 O(1) 且不移动元素"的数组，是生产者-消费者、音频环形缓冲、Disruptor 等高性能场景的核心：

容量 8，head=2, tail=6：
[_][_][A][B][C][D][_][_]
        ↑head       ↑tail

enqueue(E): a[tail++]=E, tail &= 7   →  [_][_][A][B][C][D][E][_]
dequeue():  return a[head++], head &= 7   →  [_][_][_][B][C][D][E][_]

两个关键细节：

1. 容量取 2 的幂：tail & (cap - 1) 替代 tail % cap，省 20+ 周期
2. 满/空判定：用 size 字段或预留一个空位，否则 head == tail 无法区分

工业级实现：LMAX Disruptor 在此之上加了缓存行填充避免伪共享（false sharing），单生产者-单消费者能做到 2500 万 ops/s，比 ArrayBlockingQueue 快 5-10 倍。

// 缓存行填充示例（避免两个 long 共享一个 64B 的 cache line）
class Sequence {
    long p1, p2, p3, p4, p5, p6, p7;   // 56B 填充
    volatile long value;
    long p8, p9, p10, p11, p12, p13, p14;
}

JDK 8+ 的 @Contended 注解能自动做这件事。

---

11. 本篇收获与案例回扣

11.1 回到开篇的 LinkedList 事故

回过头看那段代码：

for (int i = 0; i < recent.size(); i++)
    buffer.append(recent.get(i).toString());

问题的本质是 把"按下标访问"施加在一个根本不支持 O(1) 随机访问的结构上。ArrayList（数组底层）的 get(i) 是 O(1)，LinkedList 的 get(i) 是 O(N)——同样的代码，底层结构不一样，复杂度天差地别。

修复有两条路：

1. 换成 for-each（链表遍历用迭代器，O(N)）
2. 换底层结构成 ArrayDeque（循环数组，头插 O(1)、下标访问 O(1)）

第二条路才是最彻底的——因为这个业务要的就是"频繁头插 + 顺序读"，循环数组正是为此而生。

11.2 八个核心收获

八个带走点：

1. 数组的本质是"连续内存 + 类型相同"，两者合力撑起 O(1) 随机访问
2. 访问 ≠ 查找：访问 O(1)，查找无序 O(N)
3. 缓存友好性是数组被低估的最大优势，实际性能优势远大于理论复杂度
4. 插入删除 O(N)，但不保序时可优化到 O(1)（末尾交换）
5. System.arraycopy 比手写 for 快 5~10 倍
6. 动态数组均摊 O(1)，预估容量能免扩容
7. 行优先语言按行遍历，否则缓存命中率掉几倍
8. 下标是偏移量不是序号，从 0 开始是硬件一致性选择

---

12. 思考题

1. 下标设计：除了"少一次减法"，从 0 开始还有什么优势？（提示：半开区间 [0, N) 表达长度的简洁性、空区间、切片）
2. 缓存实验：用你熟悉的语言测 1000×1000 二维数组的行遍历与列遍历，解释耗时差异。Java 的 int[][]（本质是"数组的数组"，每行独立对象）和 C 的真二维数组相比，缓存表现差在哪？
3. 扩容策略：若扩容倍数取 1.0（每次只多一个位置），N 次 append 的总拷贝次数是多少？和 2 倍相比差在哪？这说明了什么？
4. 并发数组：多线程同时 add() ArrayList 会出什么问题？CopyOnWriteArrayList 解决的代价是什么？有更好的方案吗？（提示：分段数组、Disruptor 的无锁环形缓冲）
5. 算法设计：LeetCode 41「缺失的第一个正整数」要求 O(N) 时间 O(1) 空间。它利用了数组的什么特性？为什么链表做不到？

---

13. 课后作业实战

作业 1（必做）——链表 vs 数组实测

分别用 LinkedList 和 ArrayList 实现开篇的"最近 200 条记录"需求，压测 QPS 5000、持续 1 分钟下：

• 平均耗时 / P99
• GC 次数、Old Gen 增长
• 尝试把 for (int i; i < n; i++) list.get(i) 换成 for-each，再次压测

写一份分析报告，解释每一组数字背后的原因。

作业 2（必做）——实现一个 ArrayDeque

从零实现一个循环数组版的双端队列，要求：

• addFirst / addLast / removeFirst / removeLast 都是 O(1)
• 容量自动扩容（2 倍，且必须保持 2 的幂）
• 用位运算代替取模
• 编写单元测试覆盖"绕圈"边界场景

对比你自己实现的性能与 JDK ArrayDeque，分析差距来源。

作业 3（进阶）——设计帧缓冲

给你一个视频解码回调，每 1/30 秒产生一帧 1080p RGBA 图像（约 8MB）。要求：

• 缓冲最新 30 帧（1 秒），旧帧覆盖
• 支持多消费者并发读取任一帧
• 不允许在回调里分配内存

请基于"环形数组 + 预分配 + 版本号"设计方案，给出核心数据结构与主要操作的伪代码，并分析其内存峰值、最坏延迟、多消费者一致性。

---

14. 进阶专题与延伸

14.1 列式存储（Columnar Storage）

传统行存把一条记录的所有字段放一起，列存则把同一列的所有值连续存。这是 ClickHouse、Parquet、DuckDB 等 OLAP 引擎性能超群的根源。

行存：  [id=1, name=A, age=20] [id=2, name=B, age=30] [id=3, name=C, age=25]
列存：  id  = [1, 2, 3]          ← 只读 age 时，只扫这一列
        name= [A, B, C]
        age = [20, 30, 25]

为什么快？三点：

1. 只读需要的列——SELECT avg(age) 不需要加载 name、email 等字段，IO 减少 10-100 倍；
2. 同列数据类型相同，压缩率极高——整数列用 bit-packing，字符串列用字典编码，整体压缩 5-20 倍；
3. SIMD 天然适配——同类型连续数据，avg/sum/max 直接向量化。

取舍：列存写单条记录要分散写多个列，写入放大；所以 OLTP 用行存、OLAP 用列存。HTAP 系统（TiDB、ClickHouse 23+）则同时维护两份。

14.2 向量数据库与 Embedding 存储

LLM 时代，文档/图像都被编码为 768 或 1536 维的向量（embedding）。数十亿条向量的存储本质就是一个超大二维数组：

float32 embeddings[N][D]     // N 条 × D 维
1 亿条 × 1536 维 × 4 B ≈ 600 GB

相似度搜索不可能线性扫描 1 亿条，所以引入近似算法：

算法	思想	代表
IVF（倒排文件）	k-means 分簇，查询时只搜最近的几个簇	FAISS IVF
HNSW	多层图索引，log N 跳	FAISS HNSW、Milvus、pgvector
PQ（Product Quantization）	切块量化压缩	FAISS IVFPQ
ScaNN	各向异性量化	Google

本质都是"在大数组上构造索引"——数组仍是承载 embedding 的物理地基，索引只是加速层。

14.3 GPU / TPU 的张量内存

深度学习的"张量（Tensor）"本质是带 shape 元数据的多维数组：

# PyTorch
x = torch.randn(32, 3, 224, 224)   # 形状 (batch, channel, height, width)
# 底层：一段连续的 float32 内存，大小 32*3*224*224*4 = 19.3 MB
# 索引 x[i,j,k,l] = base + (i*3*224*224 + j*224*224 + k*224 + l) * 4

Stride（步长）机制让张量可以"零拷贝转置"：

y = x.transpose(1, 2)       # 只改 stride 数组，不搬数据
z = x.view(32, -1)          # 只改 shape 元数据

这是 NumPy/PyTorch 常数级 API 的底层魔法——数据是共享的，视图是廉价的。代价是：某些操作要求数据是 "contiguous"，否则要 .contiguous() 触发真拷贝。

GPU 的额外要求：

• 合并访问（coalesced access）：一个 warp（32 线程）访问的地址必须连续，否则性能腰斩；
• 共享内存 bank 冲突：48KB 的 shared memory 分 32 个 bank，跨 bank 访问最优；
• Tensor Core：只吃特定形状（如 16×16×16）的矩阵块——底层仍是连续数组，但粒度从"元素"升级到"tile"。

AI 工程的性能优化有一半都在处理"让数组的布局符合硬件期望"。

14.4 无锁并发数据结构里的数组

高并发场景下，最能撑住吞吐的结构几乎都是"数组 + 原子变量"：

结构	底层	性能
AtomicIntegerArray	int[] + 每元素 CAS	千万级 ops/s
Disruptor RingBuffer	环形数组 + 序号	2500 万 ops/s
Striped LongAdder	数组分段计数	亿级 ops/s
Java ConcurrentHashMap	数组 + CAS + synchronized	千万级 put/s
Michael-Scott 队列	链表	百万级 ops/s

数组比链表更适合无锁的根本原因：

• 数组元素地址稳定，CAS 目标明确；
• 链表的 CAS 要处理"前驱节点可能已被并发删除"的 ABA 问题；
• 数组对 CPU 的"预取（prefetch）"友好，提前把下一块数据拉进缓存。

所以几乎所有追求极致吞吐的队列都用环形数组而不是链表——Kafka、Netty、Disruptor、LMAX 无一例外。

14.5 经典书与论文

• Cormen et al. 《算法导论》第 4 版——第 11 章动态表的均摊分析，以及扩容倍数的严格证明
• Bryant & O'Hallaron 《深入理解计算机系统》——缓存与内存层级必读章节
• Drepper, Ulrich. 2007. What Every Programmer Should Know About Memory——共 114 页的内存层级权威综述
• Martin Thompson. Mechanical Sympathy blog——Disruptor 作者的高性能随笔合集
• 《C++ Concurrency in Action》(Anthony Williams)——无锁数据结构设计的权威
• 《Designing Data-Intensive Applications》第 3 章——列式存储、LSM 树、B+ 树的横向对比

工程代码：

• Netty io.netty.util.internal.shaded.org.jctools 的 MpscArrayQueue / SpscArrayQueue——JCTools 是 JVM 上无锁队列的事实标准
• LMAX Disruptor（github.com/LMAX-Exchange/disruptor）——环形数组 + 缓存行填充 + 无锁序号
• Apache Arrow（arrow.apache.org）——列存 + 零拷贝跨语言数据共享的工业级方案
• FAISS（github.com/facebookresearch/faiss）——Meta 的向量检索库，看"巨型数组上的近似算法"最佳例子

---

至此数组这一篇就讲完了。下一篇《04.链表的设计和实践》里，我们会走进数组的"对立面"——看链表如何用指针换自由度、如何在"频繁插入删除"的场景上弯道超车，以及为什么 Linux 内核依然倾爱侵入式链表。读完下一篇再回过头看本篇，你会对"数据结构没有银弹，只有权衡"这句话有更深的体感。