数组与动态数组：内存布局与扩容

一句话定义

数组（Array）是在连续内存中存放同构元素的结构，凭「基址 + 下标 × 元素大小」实现 O(1) 随机寻址；动态数组（Dynamic Array）在数组之上封装「满了就搬进更大的连续块」的扩容机制，提供均摊 O(1) 的尾部追加。

为什么重要

数组是几乎所有结构的内存基座：堆用数组存树、哈希表用数组存桶、字符串是字符数组。理解「连续性带来随机寻址与缓存友好、也带来插删搬移」这一对代价，是理解后续一切「数组派 vs 链表派」取舍的原点；扩容则是 kp-004 均摊分析的第一个落地案例。

前置知识

kp-001（ADT）、kp-004（均摊分析）；对内存地址的基本概念。

核心概念

• 随机寻址公式：元素 a[i] 的地址 = 基址 + i × 元素大小，一次乘加完成，与 n 无关 ⇒ 读写 O(1)。
• 插删代价：在第 i 位插入/删除需搬移其后 n−i 个元素 ⇒ 最坏 O(n)；尾部追加为 O(1)。
• 倍增扩容：容量满时申请约 2 倍新块并整体搬迁，单次 Θ(n)、均摊 O(1)（kp-004 证明）。
• 缓存友好性（Cache Locality）：连续内存天然契合 CPU 缓存行与预取器，顺序遍历的实际吞吐常比链表高数倍——这是渐进记号之外的工程常数优势。
• 多维数组行主序：a[i][j] 地址 = 基址 + (i×列数 + j)×元素大小。

直观类比

数组是电影院连排座位：报「第 7 排 3 号」立刻落座（随机访问）；但要往中间塞一个人，整排人都得挪（插删搬移）。动态数组则是影院每隔一段时间把整场观众迁到更大的影厅——迁场贵但次数被摊薄。

原理与机制

扩容策略对比推导：设增长因子为 r（r>1），从容量 1 起连续插入 n 个元素，搬迁总代价为 r + r² + … + r^⌈log_r n⌉ ≤ n·r/(r−1) = O(n)，故均摊 O(1) 且随 r 减小而增大。若改为每次扩容 +c（线性增长），则需 Θ(n²/c) 总搬迁，均摊退化为 Θ(n)。内存回收侧还有「收缩策略」问题：删除导致占用率低于 1/4 时减半收缩，可兼顾空间与震荡（避免在 1/2 附近反复扩缩）。

图示

扩容序列（增长因子 2）：
容量   [1]→[2]→[4]→[8]→[16]
元素   a    ab   abcd abcdefgh …
单次代价 2    4    8        ← 呈几何级数，总和 < 2n
行主序寻址：a[i][j] ⇢ base + (i × C + j) × size
        j=0   j=1   j=2
  i=0 [ a ][ b ][ c ]
  i=1 [ d ][ e ][ f ]     内存中按行连续：a b c d e f

实例或案例

• 三大语言对照：C++ std::vector（倍增约 1.5–2，可 reserve）、Java ArrayList（1.5 倍）、Python list（约 1.125 过度分配但同样均摊 O(1)）。
• 高频交易行情缓冲：用预分配环形数组避免运行时扩容停顿（呼应 kp-004 的尾部延迟讨论）。
• 矩阵遍历调优：按行遍历（顺序内存）比按列遍历快数倍，纯粹是缓存局部性差异，复杂度同为 O(n²)。

常见误区

• 认为「数组插入都是 O(n)」：尾插是 O(1)（均摊），头插/中插才搬移；方向决定代价。
• 在循环中反复 push 大量元素却不预留：触发多次扩容与搬家，性能尖峰可测。
• 二维数组按列遍历却期待数组缓存优势：局部性被破坏，常数劣化数倍。
• 认为动态数组删除元素后容量自动收缩：多数实现不缩，需手动 shrink 或依赖实现的收缩阈值。

自测题

1. 元素为 8 字节、列数 C=100 的行主序二维数组，a[5][7] 相对基址的偏移是多少字节？

答案要点：(5×100+7)×8 = 4056 字节。

1. 为什么动态数组扩容必须按「倍数」而不能按「固定增量」？用均摊分析说明。

答案要点：固定增量 c 使两次扩容间只多 c 个元素，总搬迁 Θ(n²/c)，均摊 Θ(n)；倍数增长使搬迁总代价 ≤ (r/(r−1))·n，均摊 O(1)。

1. 同为 O(n) 的「数组求和」与「链表求和」，为什么实测数组常快 3–10 倍？

答案要点：数组内存连续，命中 CPU 缓存与预取；链表节点分散、每步伴随指针解引用与缓存未命中，常数更大。

与其他知识点的关系

kp-007 链表是数组的主要对照面；kp-008 栈/队列常用数组实现；kp-014 堆把树压进数组；kp-009 哈希表的桶数组是扩容机制的又一应用。

延伸阅读

《算法（第 4 版）》第 1.3 节「背包、队列和栈」中 ResizingArrayStack 的实现；What every programmer should know about memory（Drepper）关于缓存局部性的论述。