23、动态数组的扩容策略：倍数扩容与线性扩容、性能分析

动态数组，说白了就是能自动长大的数组。但怎么个长法，这里头大有讲究。我见过不少新手，直接写死一个固定大小，结果数据一多就崩。也有人每次只加一个元素，结果程序慢得像蜗牛。今天咱们就来聊聊，到底该怎么扩容才靠谱。

两种主流扩容策略

动态数组的扩容，核心就两个思路：线性扩容和倍数扩容。嗯，咱们一个一个看。

线性扩容：每次加固定大小

线性扩容，就是每次容量不够了，就增加一个固定的数值。比如当前容量是10，每次扩容加5个，那下次就是15，再下次20。代码实现很简单：

// 线性扩容示例：每次增加 FIXED_STEP 个元素
#define FIXED_STEP 10

int* linear_expand(int* arr, int* capacity) {
    *capacity += FIXED_STEP;
    int* new_arr = (int*)realloc(arr, (*capacity) * sizeof(int));
    if (!new_arr) {
        // 处理失败
        return NULL;
    }
    return new_arr;
}

这种策略的好处是内存增长可控，不会一下子吃掉太多内存。但问题也很明显——如果数据量很大，扩容次数会非常多。每次扩容都要搬数据，搬一次就是O(n)的开销。你想想看，如果插入100万个元素，每次只加10个，那得搬多少次？

倍数扩容：每次翻倍

倍数扩容，就是每次容量不够时，直接翻倍。比如从10变成20，再变成40，80……这是目前最常用的策略。C语言标准库的很多动态数组实现，用的就是1.5倍或2倍扩容。

// 倍数扩容示例：每次翻倍
int* double_expand(int* arr, int* capacity) {
    *capacity *= 2;  // 翻倍
    int* new_arr = (int*)realloc(arr, (*capacity) * sizeof(int));
    if (!new_arr) {
        return NULL;
    }
    return new_arr;
}

为什么大家都爱用倍数？因为均摊时间复杂度低。你想想，每次翻倍，之前搬的数据量总和，其实和最后一次搬的数据量差不多。均摊下来，每次插入的代价是O(1)。这就是所谓的“摊还分析”。

性能对比：一张图看懂

为了让你更直观地理解，我画了一张对比图。横轴是插入次数，纵轴是累计的搬移开销。

从图上能明显看出来，线性扩容的累计开销增长得越来越快，而倍数扩容则平缓得多。我个人习惯用1.5倍扩容，因为2倍扩容有时会浪费太多内存，1.5倍在时间和空间上更均衡。

扩容因子怎么选？

倍数扩容也不是越大越好。我整理了一个表格，方便你对比：

避坑指南：realloc 的陷阱

说到扩容，就不得不提realloc。这个函数看似方便，但有几个坑要注意：

• realloc失败返回NULL，原指针不释放。所以千万别直接 ptr = realloc(ptr, new_size)，否则失败后原内存就丢了。正确做法是用临时变量。
• realloc可能搬动数据。如果当前内存块后面没有足够的连续空间，它会重新分配一块，然后把旧数据拷过去。这个过程是O(n)的。
• 频繁realloc会导致内存碎片。尤其是线性扩容，每次只加一点点，内存碎片会越来越严重。

// 正确的realloc用法
int* tmp = (int*)realloc(arr, new_capacity * sizeof(int));
if (tmp == NULL) {
    // 错误处理，arr仍然有效
    free(arr);  // 或者根据业务决定
    return NULL;
}
arr = tmp;  // 只有成功后才赋值

嗯，这里要注意，realloc并不是万能的。如果你需要频繁扩容，可以考虑用链表或者分块数组来替代。但如果你坚持用动态数组，那就老老实实选好扩容策略。

实际项目中的选择

我在做嵌入式项目时，内存只有几十KB，这时候用倍数扩容就太奢侈了。我一般会预估最大数据量，然后一次性分配够，或者用线性扩容+小步长。但在服务器端开发中，内存相对充裕，我几乎无脑用1.5倍扩容。

说白了，没有银弹。你得根据你的场景来选。但有一点是确定的：不要用固定步长去处理海量数据，否则性能会很难看。

好了，关于动态数组的扩容策略，就聊到这儿。记住，选对策略，你的程序才能跑得又快又稳。