数组与动态数组：会自我扩建的编号储物柜

可视化演示

展示数组连续内存与O(1)随机访问、动态数组倍增扩容过程、以及均摊分析append常数复杂度证明。

数组基础特性：一排钉死的编号柜

还记得仓库里那排水泥浇筑的柜子吗？施工队进场时，先量好场地，再按统一宽度一个挨一个地浇筑。柜子之间的间距分毫不差，编号从 0 开始递增。这样的设计有个巨大的好处：你不需要挨个查看柜门上的号码，只要知道排头的坐标和每个柜子的宽度，心里一算就能直达任意一个柜子。这就是数组最核心的直觉——“算着走”而不是“找着走”。

把这个场景搬到计算机里：内存就是一长条连续编址的“仓库走廊”。数组在创建时，向操作系统一次性申请一段连续的内存空间，并记录下这段空间的起始地址。与水泥柜排一样，数组有三个硬性约束：空间连续、长度固定、所有元素占用的字节数相同（即元素类型统一）。正因为这三个约束，访问第 i 个元素才能变成一次纯粹的数学计算。

数组的随机访问之所以是 O(1)，秘密全在下面这个寻址公式里。它把“找柜子”变成“算地址”，一次乘加搞定：

水泥柜排的优点是“一步直达”，代价却是长度固定。一旦浇筑成型，想多塞一个柜子就得推倒重建。包裹少的时候还好，可一旦爆仓，你就必须面对“搬家”这个新问题了——这正是动态数组登场的理由。

动态数组原理：会自己扩建的移动柜墙

爆仓那天，经理当机立断：在旁边空地搭一排更大的新柜，把旧柜里的包裹全部搬过去，然后拆掉旧柜。整个流程分四步——找新场地、搬包裹、拆旧柜、更新门牌记录。而且经理规定：以后每次快满仓时都自动重复这套流程，不用你操心。这就是动态数组：一个“长了脑子”的数组，它记得自己还剩多少空位，满了就自动扩容。

动态数组内部维护三个关键信息：一块指向堆内存的指针（相当于新场地的地址）、当前容量 capacity（柜子总数）、当前长度 size（已用柜子数）。每次执行 append（尾部追加包裹）时，它先检查 size 是否等于 capacity。如果没满，直接把包裹放进 data[size]，然后 size 加一；如果满了，就触发扩容流程。

扩容的具体动作是：先向操作系统申请一块更大的连续内存（新场地），把旧内存里的 size 个元素逐个拷贝过去（搬包裹），释放旧内存（拆旧柜），最后更新指针和 capacity（改门牌）。关键在于扩容时容量翻倍，而不是只加一格：

等到新柜搭好，你会惊喜地发现：虽然每次搬家都要折腾一番，但搬家的频率越来越低。4→8 搬一次，8→16 搬一次，16→32 搬一次……包裹越多，两次搬家之间的“安稳期”越长。这就是倍增策略的巧妙之处——把昂贵的搬家摊薄到漫长的日常存取里。

均摊分析：搬家费平摊到每次存件

经理要求你记账：每次搬家雇搬运工都要花一大笔钱，这钱该算在哪个包裹头上？如果算在搬家当天的包裹上，那天的成本高得吓人；如果把这笔钱平摊到从上次搬家到这次搬家之间存进来的所有包裹上，每单成本其实微乎其微。这种“把偶尔的高额开销摊到日常操作上”的记账方式，就是均摊分析的思想。

均摊分析不纠结某一次操作的最坏情况，而是看“连续执行 n 次操作，总成本除以 n 的平均值”。对动态数组来说，append 偶尔会触发 O(n) 的扩容拷贝，但绝大多数时候只是 O(1) 的原地写入。我们需要证明：把 n 次 append 的总成本加在一起，平均下来仍然是常数。

假设容量从 1 开始，每次翻倍。第 k 次扩容时，容量从 2^k 变成 2^{k+1}，需要搬运 2^k 个元素。把这些搬运量加起来，恰好是一个几何级数：

对比一下反面教材：如果每次满仓只加 1 格（增量扩容），那么第 m 次扩容要搬 m 个元素，n 次操作的总搬运量约为 n²/2，均摊下来是 O(n)——每存一个包裹平均要搬半个仓库的东西，这显然不可接受。所以倍增不是偷懒，而是数学上最优的选择，它用“偶尔大搬家”换来了“永远很轻松”。

空间局部性：紧挨的柜子搬运起来快

扩容问题解决了，经理又发现一个省钱秘诀：由于柜子紧挨在一起，搬运工推着小车从 0 号柜走到 97 号柜，一路顺过去就能把整排包裹搜刮干净，小车上的“临时货架”（缓存）装得满满当当。反过来，如果柜子东一个西一个散落在仓库各处，搬运工每取一件都要推车跑一趟远路，效率天差地别。这正是空间局部性的威力。

CPU 访问内存时，并不是一个字节一个字节地取，而是以缓存行（cache line，通常 64 字节）为单位，一次性成块加载到高速缓存里。数组元素在内存中连续排列，意味着当你访问 data[i] 时，CPU 已经把 data[i] 附近的几十个字节一起搬进了缓存。接下来访问 data[i+1]、data[i+2] 时，数据已经在缓存里等着了，无需再访问慢速主存。

假设数组元素是 4 字节的 int，那么一个 64 字节的缓存行正好能装下 16 个元素。顺序遍历数组时，每拉取一行缓存，16 次访问全部命中：

对比链表：链表的每个节点是单独申请的内存，地址七零八落。访问链表第 i 个节点时，往往每走一步都要重新拉一次缓存行，利用率可能跌到几十分之一。这也是为什么在 AI 场景中，处理连续的张量数据时数组几乎总是首选——连续本身就是一种性能优化。

缩容策略：包裹少了就搬进小仓

旺季过去，包裹一天天减少。经理看着那排巨大的柜子直皱眉：场地租金是按面积算的，空着 3/4 的柜子纯属烧钱。于是他定下规矩——当包裹数量降到某个阈值以下，就主动搬回小场地，把容量缩下来。但这里有个陷阱：如果每次少一个包裹就立刻缩一次容，就会陷入“刚搬完小仓又爆仓、刚搬完大仓又空旷”的来回折腾，搬运费反而更贵。这种现象叫抖动（thrashing）。

正确的缩容策略必须与扩容策略“对称”。既然扩容是“满到 100% 时翻倍”，那么缩容就应该“空到 25% 时减半”。也就是说，当元素个数 size 小于等于容量的四分之一时，才把容量缩为原来的一半：

这个“四分之一阈值”是工程上的经典约定，比如 Java 的 ArrayList 和 Rust 的 Vec 在缩容时都参考了类似的逻辑。它体现了一种重要的思维：在时间（搬运开销）与空间（浪费的内存）之间做权衡——不能只顾一头，而是找一个让两头都舒服的平衡点。

复杂度对比：不同操作的成本账本

现在给仓库的各类操作列一张成本账本。取某号柜的包裹：一步直达，O(1)。往尾部存包裹：平时放下就走，偶尔搬一次家，均摊 O(1)。往头部塞包裹：所有柜子都要往后挪一格，O(n)。在乱柜里翻找某个特定包裹：最坏得翻遍所有柜子，O(n)。这张账本决定了数组适合什么场景、不适合什么场景。

回到仓库的比喻：数组就像那排整齐划一的水泥柜，适合“按号取件、尾仓入库”的高效流水线；动态数组则是它的进阶版——水泥柜学会了自动扩建、自动缩编，却依然保持整齐排列的所有优点。理解了这套存储逻辑，你就掌握了几乎所有高性能数据结构的底层地基：向量、张量、嵌入表、日志缓冲……它们都是这排“会自我扩建的编号储物柜”在不同场景下的化身。

AI 应用场景

Python 演示

# dynamic array demo: doubling expansion and quarter shrinkclass DynamicArray:    def __init__(self):        self.capacity = 4        self.size = 0        self.data = [None] * self.capacity        self.copy_count = 0     def append(self, value):        if self.size == self.capacity:            self._resize(self.capacity * 2)        self.data[self.size] = value        self.size += 1     def pop(self):        if self.size == 0:            raise IndexError("empty array")        value = self.data[self.size - 1]        self.size -= 1        if self.size <= self.capacity // 4 and self.capacity > 4:            self._resize(self.capacity // 2)        return value     def _resize(self, new_capacity):        new_data = [None] * new_capacity        for i in range(self.size):            new_data[i] = self.data[i]        self.copy_count += self.size        self.data = new_data        self.capacity = new_capacity     def __getitem__(self, index):        if 0 <= index < self.size:            return self.data[index]        raise IndexError("index out of range")     def __len__(self):        return self.size  if __name__ == "__main__":    arr = DynamicArray()    for i in range(10):        arr.append(i)    print("elements:", [arr[i] for i in range(10)])    print("capacity:", arr.capacity, "size:", len(arr))    for _ in range(6):        arr.pop()    print("after 6 pops -> capacity:", arr.capacity, "size:", len(arr))     big = DynamicArray()    for i in range(100000):        big.append(i)    print("100k appends total copy:", big.copy_count)    print("amortized copy per append:", big.copy_count / 100000)

1. if self.size == self.capacity:判断柜子是否已满，满了才触发扩容。
2. self._resize(self.capacity * 2)扩容时容量直接翻倍，而不是加一。
3. for i in range(self.size): new_data[i] = self.data[i]把旧柜里的包裹逐个搬进新柜。
4. self.copy_count += self.size记录搬运次数，用于验证均摊结论。
5. if self.size <= self.capacity // 4 and self.capacity > 4:元素少于容量四分之一时才缩容，防止抖动。
6. self._resize(self.capacity // 2)缩容只缩一半，与倍增对称。
7. big.copy_count / 100000观察均摊值：10 万次 append 平均每次搬运约 2 个元素，印证 O(1)。

常见误区

面试题