从静态数组的痛点说起为什么必须引入扩容这个机制1.1 固定数组的先天不足我最早开始写代码的时候用的就是C语言里的固定数组。遇到需要存一组学生成绩、一批网络数据包ID这种场景第一反应就是int arr[100]。当时觉得够用了直到某天需要处理的数据量超过了100程序直接越界写把相邻内存里的数据全干翻了调试了整整一个下午才定位到问题。这就是固定数组最大的矛盾你必须在编译期就决定好数组长度但实际运行时的数据量是个未知数。开大了浪费内存开小了就越界崩溃。更麻烦的是数组一旦定义长度就焊死了没有任何补救手段。很多刚入行的朋友会想那我把数组开到足够大不就行了比如定义个int arr[100000]。这在 demo 里没问题但你是用100KB的固定开销去赌数据量永远不会超过这个值一旦业务膨胀、数据量翻倍照样炸。生产环境里这种写法会被运维骂死。另一个痛点体现在业务代码的拼装上。你要写一个往数组末尾追加数据的函数用固定数组就得这样void append(int arr[], int* len, int max_len, int value) { if (*len max_len) { // 只能报错或者忽略没有别的办法 return; } arr[*len] value; (*len); }每次调用都要把max_len传进来每个函数都要做一次是否已满的判断。如果哪次忘了判断就是一个隐性炸弹。这种代码写多了你会非常清楚地意识到数组的容量管理不该是业务代码操心的事情它应该被封装成一个独立的、自动扩容的组件。这也是为什么几乎所有现代语言的标准库都有动态数组——Java 的ArrayList、C 的vector、Python 的list底层本质都是同一个东西。1.2 动态数组要解决的核心矛盾动态数组要解决的核心矛盾其实就一句话既要拥有数组随机访问的高效特性又要摆脱固定长度的束缚。数组随机访问是 O(1) 的因为data[i]的地址就是data i * sizeof(T)这是指针运算直接算出来的没有任何中间查找过程。这个优势太宝贵了链表虽然插入删除灵活但访问第 i 个元素必须从头遍历最坏 O(n)。所以动态数组的设计目标就是保留连续内存的随机访问能力同时在元素个数超过当前容量时自动扩大存储空间。围绕这个核心衍生出三个总要处理的子问题什么时候扩容需要一个标记当前元素个数和当前容量的机制。扩多大扩容倍率直接决定后续插入的时间开销总和。扩容时怎么搬数据新内存分配好了之后旧数据怎么移动旧空间怎么释放。这三个问题串联起来就是动态数组的底层逻辑骨架。把这个骨架在我的个人项目里搭过一遍之后再去看标准库的源码很多设计决策一下就懂了比如为什么ArrayList的扩容不直接用newCapacity而是有一堆位运算为什么 Cvector在插入时要区分有能力容纳和需要重新分配两条路径。1.3 你其实天天在用动态数组写业务代码的朋友可能觉得手写动态数组是造轮子没必要。但我想说所有标准库的容器类底层都是这套逻辑加上内存分配策略的包装。Java 里用ArrayList做数据缓存往里面add几百万条数据你看到的是从容的不断追加背后其实是无数次容量检查 - 扩容 - 搬移数据的循环。Python 的list.append一样它内部也维护着 allocated 和 ob_size扩容策略大致是 0、4、8、16、32、64……这样倍增上来的。理解这些你在排查线上问题时会多一个视角。举个例子往ArrayList里插入大量数据时卡顿不少人第一反应是GC 问题或IO 瓶颈实际上可能是扩容造成的大规模内存拷贝每次扩容都是一次 O(n) 的批量搬运。如果你清楚扩容逻辑就能预判这种性能拐点提前用构造器指定初始容量。另一个收益是面试。手写动态数组是各大厂手撕代码的高频题面试官不是要你背代码而是想看你有没有想到 size 和 capacity 的分离、扩容倍率选型、搬移元素的顺序、以及均摊复杂度这些点。把这些底层逻辑吃透面试基本稳。2. 结构设计的关键size 和 capacity 如何配合决定扩容时机2.1 三个核心字段data、size、capacity动手设计一个动态数组结构体只需要三个字段但每个字段的职责必须分清楚typedef struct { int* data; // 指向连续内存的指针真正存数据的地方 int size; // 当前已用元素个数即逻辑长度 int capacity; // 当前内存能容纳的最大元素个数 } DynamicArray;新手最容易搞混size和capacity。用生活化的类比capacity是你的衣柜总格数size是已经挂进去的衣服件数。衣柜总格数在买家具时就定死了但你的衣服会越来越多总格数不够的时候就需要换个更大的衣柜把衣服一件件搬过去——这就是扩容。搞清楚这两个概念的区别是理解动态数组一切后续逻辑的前提。为什么不能只用size一个变量不够了直接换大的因为当前有没有存满这件事必须要有capacity来回答。只靠size只能知道存了几个元素没法知道还能不能再插入。每次插入都去计算内存大小也不现实维护一个capacity字段就相当于把当前容量这个信息缓存下来了检查一次 O(1)。2.2 初始化的细节与内存布局初始化函数是第一个容易出问题的点。一个干净的初始化应该把三件事都做对分配初始内存、设置初始容量、把 size 清零。初始容量选多少我看的很多教科书代码喜欢用4或8这不是随便拍的数。初始容量太小会导致早期频繁扩容太大又浪费内存一个只存两三个数据的动态数组占了几百字节说不过去。通常取 4~16 之间是比较合理的具体的值可以根据应用场景调整。初始化其实有两派做法一派是懒分配data先指向 NULLcapacity存0等到第一次插入时再分配内存另一派是预先分配一小块内存。我偏向后者因为懒分配在判断扩容条件时要额外处理capacity 0的情况代码多一个分支不如一开始就分配好简洁且不容易漏判断。#define INITIAL_CAPACITY 8 DynamicArray* da_create(void) { DynamicArray* arr (DynamicArray*)malloc(sizeof(DynamicArray)); if (!arr) return NULL; arr-data (int*)malloc(INITIAL_CAPACITY * sizeof(int)); if (!arr-data) { free(arr); return NULL; } arr-size 0; arr-capacity INITIAL_CAPACITY; return arr; }注意到malloc之后必须先判断返回值再往下走。内存分配失败返回 NULL 是很常见的事尤其是长时间运行的服务内存碎片化严重。如果忽略分配失败后面直接arr-data[0] 1就是在 NULL 指针上写入程序立刻崩。写好错误处理是手写容器类的基本功。2.3 扩容检查每次插入前的那个 if插入逻辑的第一步永远不是写数据而是检查容量。这个检查的逻辑极朴素但位置很重要if (arr-size arr-capacity) { da_resize(arr, arr-capacity * 2); }这个判断必须在还没有写入新元素之前做。我见过有人写成插入之后发现size capacity再补救那就已经晚了数据已经写到越界内存里了。更安全的写法是检查size capacity因为逻辑上 size 永远不该超过 capacity只要相等就说明满了。有人用是为了防御性编程万一此前某处 bug 导致 size 异常至少能在扩容出发前暴露出来。我个人的做法是因为相信自己其它逻辑正确写反而会掩盖 bug 的痕迹。不过这个属于个人风格没有绝对的对错。扩容检查的位置也一样适用于任意位置插入在搬移元素之前就确认容量足够。如果先搬移再扩容搬移用的还是旧内存后面还要再搬一次白干活。所以先判断容量、再处理位移这个顺序是铁律。3. 插入操作的三层逻辑确认位置、搬移元素、写入数据3.1 尾部插入最简单也是最高频push_back尾部追加是动态数组最常用的操作看着简单但恰恰是它撑起了整个动态数组的性能神话。为什么单独说尾插因为尾部插入有两个天然优势不需要移动任何已有元素只需要在data[size]处写值然后 size 加一摊还下来是 O(1) 时间复杂度。如果你后续要写头插或任意位置插入以尾插为起点逐步加复杂逻辑理解起来会顺很多。尾插首先重复上面说的容量检查然后写指针、更新 size就结束了void da_push_back(DynamicArray* arr, int value) { if (arr-size arr-capacity) { da_resize(arr, arr-capacity * 2); } arr-data[arr-size] value; arr-size; }这里有个容易忽略的坑arr-data[arr-size]这一行下标的取值是 size 还是 size-1新元素永远放在当前最后一个元素的下一个位置所以下标就是 size。如果写成data[size-1]第一次插入时 size 为0那就是写入data[-1]直接越界写。这个细节新手特别容易写错我建议每次写完都先跑一个空数组插入的用例确保第一个元素落在下标0。3.2 任意位置插入搬移方向的讲究任意位置插入比尾插复杂在多了元素搬移这一步。目标是把新元素放到index处同时把原本index及之后的所有元素都往后挪一位。伪逻辑如下检查index是否在[0, size]范围内注意index size是合法的相当于尾插。检查容量满了就先扩容。从size-1开始把data[i]的值赋给data[i1]一直做到i index。把新值写入data[index]size 加一。搬移方向是关键。你必须从最后一个元素开始往前搬而不能从index开始往后搬。解释一下为什么搬移操作是相邻元素的后移覆盖。如果你先搬data[index]到data[index1]那data[index]的旧值就还在那里等你再回头想把data[index1]搬到data[index2]时data[index1]已经变成旧data[index]的副本了原来的data[index1]被覆盖消失了。整个数组相当于把 index 处的值复制到了后面其它元素根本没动这显然不对。从后往前搬就完全没问题先把最后一个元素搬到空出来的最后一个1位置再把倒数第二个搬到最后一个的位置依此类推每个元素都跨越一格不存在覆盖还没搬走的元素的可能。这个方向性我用一个极简的例子验证过。假设数组是[1, 2, 3]要在 index1 的位置插入 9。从后往前搬的顺序是先把3从下标2搬到3数组变成[1, 2, 3, 3]再把2从下标1搬到2数组变成[1, 2, 2, 3]然后在 index1 处写9最终[1, 9, 2, 3]。方向一错结果全乱。3.3 为什么从后往前搬移是对的用逆序推导来看如果还有点绕可以从反面来想搬移的本质是要在 index 处腾出一个空位同时保持 index 之后所有元素的相对顺序不变。如果你从前往后搬前面元素一旦覆盖后面元素后面的原始值就丢了除非你用一个临时变量把后面元素先存起来。也就是说从前往后搬意味着每个后移元素都要先暂存整个操作的时间复杂度会变成 O(n) 而且还费一个临时内存。从后往前搬则完全不需要暂存每一次移动的目标位置都是已经被移走元素留下的空位不需要担心原始值被覆盖。这是非常典型的设计权衡根据目标位置空洞的演化方向选择搬移遍历方向省掉临时存储。理解了任意位置插入删除操作就是反向搬移。删除 index 处元素要把它之后的元素整体往前挪一位方向相反、从 index1 开始往前覆盖最后 size 减一。所以插入和删除本质上是同一个逻辑的镜像。这也是动态数组和链表在操作层面最大的不同链表改的是指针指向O(1) 时间动态数组要搬数据最坏 O(n)。但动态数组随机访问又是 O(1)所以没有绝对的优势只有场景适配。4. 扩容机制的底层逻辑分配新内存、搬移旧数据、释放旧空间4.1 扩容时机与扩容倍率的选型扩容的触发时机的判断很简单就是插入前发现size capacity。但真正有技术含量的是扩容倍率的选型。我在项目里最开始用的是固定增量扩容就是capacity 16这样扩后来发现这种方式对连续插入大量数据的场景极不友好假设初始容量 8固定增量 16连续插入 100 个元素扩容次数多达 6~7 次每次都要重新分配内存、搬移全部已有数据总搬移量是 O(n²) 级别。倍增策略则完全不同。初始容量 8插入到第9个元素时扩容到16此时搬移了8个元素再插入到第17个时扩容到32搬移16个再扩容到64搬移32个。累加起来插入了 n 个元素后的总搬移次数约为 8 16 32 ... n 2n是 O(n) 量级。虽然单次扩容的最坏代价是 O(n)但均摊到每次插入上只是常数级别的开销。这就是为什么主流语言动态数组几乎都采用倍增扩容C 的vector用 2 倍Java 的ArrayList用 1.5 倍再加一个最小增量。至于为什么不用更大的倍率比如3倍甚至10倍扩容倍率越大均摊搬移越少但每次扩容后内存浪费也越严重可能有一大半容量是空的。2 倍是个兼顾时间和空间的经典平衡点。1.5 倍的空间利用率更高代价是均摊搬移稍多而且 Java 选 1.5 倍还有个私心新容量比 2 倍更紧凑配合连续内存分配缓存更友好。4.2 动态扩容的标准流程扩容本身是一个三步走的过程分配新内存、搬移旧数据、释放旧空间。代码实现如下void da_resize(DynamicArray* arr, int new_capacity) { int* new_data (int*)malloc(new_capacity * sizeof(int)); if (!new_data) { // 分配失败时的处理策略后面单独讲 return; } for (int i 0; i arr-size; i) { new_data[i] arr-data[i]; } free(arr-data); arr-data new_data; arr-capacity new_capacity; }这里有三个细节值得展开。第一分配新内存和搬移数据为什么要分开能不能realloc一步搞定realloc确实可以而且在原地能扩大的时候效率极高不需要搬移。但可移植性上有讲究realloc的行为随内存分配器而异某些场景可能因为无法原地扩展而自动搬移但这部分开销其实和手动搬移是等价的。老实说我后来自己也改用realloc了源码简洁很多。不过理解手工流程仍然有价值因为realloc处理不了的情况比如需要在扩容同时做一些自定义改造还是要回到手工步骤。第二搬移用的是memcpy还是for循环对于int这种简单类型memcpy效率更高编译器能优化成机器级的内存拷贝指令。但如果是自定的结构体类型、含有指针或者需要调用析构逻辑的类型用memcpy就危险了浅拷贝可能造成多次释放同一块内存的严重 bug。我在这篇博文里用for循环是为了展示逻辑实际工程里请根据元素类型选择。第三free(arr-data)这步不能省。如果你分配了新内存却没有释放旧内存每次扩容都会泄漏一块旧内存。长时间运行的程序扩容几十次就泄漏几十块内存会一点点涨上去最后 OOM。这是一个极其隐蔽的坑不仔细看内存曲线根本发现不了。4.3 均摊时间复杂度的证明思路很多人听说过动态数组尾插的均摊复杂度是 O(1)但不知道为什么。证明思路很简单用会计法思考。每次成功的尾插我们假设它花费 1 个单位的当前时间和 1 个单位的存款。存款存下来直到扩容发生时一次性花掉。扩容发生时需要把旧数组累计算出的 n/2 个元素都搬一次花费 n/2 个单位。而此前已经存了 n/2 次存款刚好够付这笔账。于是摊还下来每次尾插就是 2 个单位的固定开销即 O(1)。这个推导结果很重要它解释了为什么动态数组尾插在实践里如此优秀。把壁纸贴到 10 万个元素的数组尾部理论上几乎每次都是 O(1)只是偶发一次 O(n) 的扩容但那次扩容的开销被之前的十多万次插入均摊掉了宏观上看不出性能抖动。但要注意这个结论只适用于尾插。头插和任意位置插入因为要搬移元素是 O(n) 的扩容搬移只是额外增加成本并不改变数量级。5. 完整可运行的 C 语言实现从零开始手写并验证5.1 结构体定义与初始化把前面几节讲的设计落到完整代码里我直接贴一个可运行版本。这个版本已经包含结构体定义、创建/销毁、尾插、任意位置插、删除、扩容、打印。注释我会写得比较详细方便你按步骤理解。#include stdio.h #include stdlib.h #define INITIAL_CAPACITY 8 typedef struct { int* data; int size; int capacity; } DynamicArray; DynamicArray* da_create(void) { DynamicArray* arr (DynamicArray*)malloc(sizeof(DynamicArray)); if (!arr) return NULL; arr-data (int*)malloc(INITIAL_CAPACITY * sizeof(int)); if (!arr-data) { free(arr); return NULL; } arr-size 0; arr-capacity INITIAL_CAPACITY; return arr; } void da_destroy(DynamicArray* arr) { if (!arr) return; free(arr-data); free(arr); } void da_resize(DynamicArray* arr, int new_capacity) { int* new_data (int*)malloc(new_capacity * sizeof(int)); if (!new_data) { // 分配失败保持原状避免数据丢失 fprintf(stderr, Memory allocation failed during resize\n); return; } for (int i 0; i arr-size; i) { new_data[i] arr-data[i]; } free(arr-data); arr-data new_data; arr-capacity new_capacity; } void da_push_back(DynamicArray* arr, int value) { if (arr-size arr-capacity) { da_resize(arr, arr-capacity * 2); } arr-data[arr-size] value; arr-size; } void da_insert(DynamicArray* arr, int index, int value) { if (index 0 || index arr-size) { fprintf(stderr, Index out of range: %d\n, index); return; } if (arr-size arr-capacity) { da_resize(arr, arr-capacity * 2); } for (int i arr-size - 1; i index; i--) { arr-data[i 1] arr-data[i]; } arr-data[index] value; arr-size; } void da_remove(DynamicArray* arr, int index) { if (index 0 || index arr-size) { fprintf(stderr, Index out of range: %d\n, index); return; } for (int i index; i arr-size - 1; i) { arr-data[i] arr-data[i 1]; } arr-size--; } void da_print(DynamicArray* arr) { printf(size%d, capacity%d\n, arr-size, arr-capacity); for (int i 0; i arr-size; i) { printf(%d , arr-data[i]); } printf(\n); }注意da_remove里删除后不需要重置被废弃的最后一个元素的值为0因为 size 减一后它已经不属于逻辑范围下次插入会直接覆盖它。但如果数组存的是指针类型删除后最好手动把那个元素置 NULL避免垂悬引用。5.2 插入与扩容实现上面代码中我想特别强调da_insert里的 for 循环条件for (int i arr-size - 1; i index; i--)。注意 i 的类型是int。如果数组是空的arr-size - 1等于 -1循环直接不进入这是对的。但如果你把 i 的类型换成size_t无符号类型-1 会被解释成一个巨大的正整数循环会一直往下跑产生灾难性的越界写入。这是 C/C 里非常经典的无符号数与有符号数混用坑我在这里栽过一次调了一个多小时才意识到问题。强烈建议你在做数组下标循环时统一用int或者ptrdiff_t不要为了跟上时代用size_t而忽略负数边缘。扩容函数da_resize我在失败时只打了日志就返回保持了原有数据不变。这是一种失败时不破坏现状的安全策略。有些实现会在失败时直接抛异常或退出程序但作为容器类最好不要因为一次扩容失败就把所有已有数据弄丢。你可以在此基础上做增强比如失败时尝试更小的扩容倍率或者抛出异常让上层决定怎么处理。5.3 测试流程与结果验证代码写完了必须跑测试。我的测试思路是这样的先尾插三五个元素确认基本情况没问题再故意触发一次扩容插入超过初始容量的数据看扩容后数据是否完整再测试任意位置插入的搬移方向最后测越界插入的异常拦截。int main(void) { DynamicArray* arr da_create(); // 1. 尾插触发扩容 for (int i 0; i 10; i) { da_push_back(arr, i * 10); } da_print(arr); // 预期: size10, capacity16, 元素 0,10,...,90 // 2. 中间插入 99 da_insert(arr, 3, 99); da_print(arr); // 预期: 99 落在下标3后面的元素整体后移 // 3. 删除下标5的元素 da_remove(arr, 5); da_print(arr); // 4. 越界插入 da_insert(arr, 99, 1); // 预期打印错误信息程序不崩溃 da_destroy(arr); return 0; }我实际跑过这段代码输出顺序和数据值都是对的第一次尾插触发扩容后 capacity 变为16中间插入后 99 确实出现在下标3删除后数组长度减一且后续元素前移越界插入被拦截并打印了友好报错。整套流程走通底层逻辑和代码实现就闭环了。如果你也想验证扩容时机可以在da_resize里加一行打印日志每次扩容都会输出当时的 size 和 new_capacity配合测试插入数量能非常直观地看到扩容节奏。6. 手写过程中踩过的坑与后续优化方向6.1 内存泄漏与扩容失败处理前面提到过扩容时忘记free(arr-data)是最常见的内存泄漏。一旦容器是长期存活的比如全局缓存、连接池每次扩容泄漏一块旧内存累积下来就是事故。排查的时候你可能会看到内存占用曲线像台阶一样稳定上涨每上一个台阶就对应一次扩容。不过这里也要补充说明在内存分配失败的情况下旧内存其实不能随便释放因为新内存还没分配成功你需要先把旧数据稳稳保住等下次分配成功后再释放。这段顺序上的哲学是新内存优先旧内存善后。内存泄漏检测工具也值得养成习惯。Linux 下用 Valgrind 跑一遍测试程序如果看到definitely lost或indirectly lost的字节数就说明某处忘了 free。我手写动态数组的早期版本第一次跑 Valgrind 就报了几百字节的泄漏定位后发现就是扩容分支上漏了free(arr-data)。这个调试经历比看十篇博客都管用强烈建议你也跑一遍。6.2 缩容大部分场景下不建议做的操作有扩容就会有人想到缩容——数量减少到某个阈值时缩小容量省内存。这个想法听起来很美实际工程却很少这么干。最大的原因是缩容会引入未来的扩容抖震。假设当前容量 1024内存里只剩 10 个元素你缩容到 16省了一大批内存。但如果紧接着又插入一批数据又得扩容回去白白做一次大搬移。频繁的缩容-扩容交替会让性能剧烈抖动形成所谓的抖动陷阱。C 的vector还提供了一个有趣的现象clear()清空所有元素后capacity()不变。这意味着内存不释放只是 size 归零。当初我不理解认为这是 bug后来才体会到这是为了复用已分配的内存避免反复扩容。如果你想真正释放内存可以用shrink_to_fit()但它通常只是一次尝试不保证强制缩容。基于这些经验我对缩容的结论是默认不缩除非你能证明内存长期空置且短期内不会再插入大量数据。6.3 从手写动态数组到更深的底层世界手写一遍动态数组只是入门顺着这个方向往下走还有好几个进阶方向。第一个是泛型化给动态数组加上void*数据指针或 C 模板让它能存任意类型。这一步会迫使你思考元素大小、对齐、内存布局这些更底层的细节。第二个是内存分配器优化改用realloc并复用空闲内存或者引入对象池。实际项目里动态数组频繁扩容的分配开销可能是性能瓶颈之一合理的分配策略比算法本身更影响性能。第三个是并发安全给插入和扩容加上锁或者无锁设计这会让复杂度上一个台阶但也是理解并发容器如何工作的很好的练习。往工程落地方向看你还可以对比标准库的源码。比如去看 glibc 的malloc如何处理大块连续内存或者看 JavaArrayList的grow方法如何和hugeCapacity兜底溢出。看完你会有种豁然开朗的感觉原来我们手写的那套逻辑和标准库的雏形是同一个谱系标准库只是加了更多的防御和优化。我至今仍保留着自己手写的第一版动态数组代码不是为了再用它而是为了记住那些从错误中学到的底层逻辑。动手写一遍胜过读十遍 API 文档。