摊还 O(1) · 1.5 vs 2 · 缩容滞后

扩容的摊还与增长因子

数组按下标取值是 $O(1)$ ，前提是元素定宽、内存连续。而连续内存的长度在 malloc 那一刻就定死了，一个「能一直往里塞」的容器却不可能事先知道要多大。动态数组的全部机制都从这个矛盾长出来：装满就另要一块更大的，把旧内容复制过去，再把旧块还回去。

本页问三件事：换多大、总代价多少、元素删光之后要不要换回去。

1 · 容量与长度的分离

动态数组同时记两个数：已经装了几个元素，以及底层那块内存最多能装几个。前者是长度，后者是容量，两者的差额是预留出来的空位。

分开记的意义在于，push 的绝大多数次数不必碰分配器。只有长度撞上容量的那一次要重新分配，其余次数就是往预留区里写一个值再把长度加一。各语言把这对数字暴露成不同的名字：C++ 是 size() 与 capacity()，Rust 是 Vec::len 与 Vec::capacity，Go 的 slice 是内建的 len 与 cap，Java 的 ArrayList 则只公开 size()，容量藏在私有的 elementData.length 里。

容量不是随便定的。它决定了「多久碰一次分配器」，也决定了「白付多少内存」，这两项由同一个参数控制——每次扩容放大多少倍。

2 · 成倍扩容的摊还代价

先看一种不成倍的做法：每次固定加 $c$ 个槽。装到 $n$ 个元素要重分配 $n/c$ 次，第 $i$ 次复制 $ic$ 个元素，总复制量是 $\sum_i ic = \Theta(n^2/c)$ 。摊还到每次 push 是 $\Theta(n)$ ，常数时间的承诺当场作废。

按倍数 $f$ 放大则不然。最后一次扩容复制约 $n/f$ 个元素，再往前一次约 $n/f^2$ ，构成公比 $1/f$ 的几何级数：

$\displaystyle \text{总复制量} \approx \frac{n}{f}\left(1 + \frac{1}{f} + \frac{1}{f^2} + \cdots\right) = \frac{n}{f-1}$

加上 $n$ 次 push 本身的写入，摊还每次约 $1 + 1/(f-1)$ 次数组写入。 $f = 2$ 时 2 次， $f = 1.5$ 时 3 次， $f = 1.25$ 时 5 次。

图 2-1 · 逐次 push 的数组写入次数与容量阶梯，纵轴取对数，红柱是触发扩容的那一次。可改增长因子、push 次数与初始容量，观察摊还值与最贵一次的差距。

$f = 2$ 、初始容量 1、push 十万次的实测总写入是 231071，摊还每次 2.311，比闭式解的 2.00 高出一截。原因与哈希表那边同源，负载因子与成倍扩容 §2 已经拆过：这个比值取决于 $n$ 落在扩容周期的哪个位置，闭式解描述的是整周期的平均而非任意一点。

值得单独记一笔的是同一串操作的代价分布：p50、p99、p999 都是 1，到 p99.99 才涨到 129，而最贵的一次是 65537。它发生在第 65537 次 push，容量从 65536 翻到 131072，把已有的 65536 个元素全部复制过去。摊还分析把这一次平摊给了前面六万多次，但请求延迟不会自己平摊。

3 · 增长因子与已释放内存的复用

倍数取 2 还是 1.5，表面看只是「多久扩一次」与「浪费多少空间」之间挪一格。folly 的 fbvector 给出了另一条理由，它与常数无关，与分配器的行为有关。

设第 $k$ 次分配要的容量是 $c_k$ 。此刻正在使用的是 $c_{k-1}$ 那一块，更早的 $c_0, \dots, c_{k-2}$ 已经全部释放。如果分配器把这些相邻的空闲块合并成一整段，那么这一段的长度是 $\sum_{i \le k-2} c_i$ 。判据只有一句：这个前缀和够不够装下 $c_k$ 。

定理 3.1 倍数为 2 时前缀和恒为 $2^{k-1} - 1$ ，而本次要的是 $2^k$ ，永远差一块；倍数小于黄金分割 $\varphi = (1+\sqrt 5)/2 \approx 1.618$ 时，前缀和迟早追上。

证明前缀和 $S_k = \sum_{i \le k-2} f^i = \dfrac{f^{k-1}-1}{f-1}$ 。要求 $S_k \ge f^k$ ，即 $f^{k-1}(1 - f(f-1)) \ge 1$ 。当 $f^2 - f - 1 \ge 0$ ，也就是 $f \ge \varphi$ 时左边非正，不等式对任何 $k$ 都不成立；当 $f < \varphi$ 时括号为正，左边随 $k$ 指数增长，必有一个 $k$ 使它成立。∎

图 3-1 · 每次分配所需容量与此前已释放块的前缀和逐档对照，绿色是首次够用的那一档。可切换增长因子与初始容量，观察首次可复用的档位随倍数逼近 1.618 而推迟。

实测把这个结论钉到了具体档位上。 $f = 1.5$ 、初始容量 1 时的容量阶梯是 1, 2, 3, 5, 8, 12, 18, 27, 41, 62，首次够用发生在第 6 次分配： $1+2+3+5+8 = 19 \ge 18$ 。而连续模型解出的是 $k \ge 5$ ——第 5 次分配要 12，前缀和 $1+2+3+5 = 11$ ，只差 1。差的这一格来自 Math.ceil：真实的分配器只给整数字节， $1.5^k$ 的取整误差在头几档还占着不小的比重。这一条是先写了正文的「第 5 次」再跑引擎才发现不对的，改的是正文。

倍数继续往上靠，档位急剧后推：1.4 在第 5 档、1.5 在第 6 档、1.6 在第 11 档、1.618 要到第 26 档，而 1.7 与 2 在四百档内一次都没有。初始容量也影响它：同样 1.5 倍，初始容量 16 时首次可复用提前到第 5 档，取整误差被摊薄了。

这个论证有个前提值得挑明：它假设分配器会把相邻的空闲块合并。jemalloc 与 tcmalloc 对中小尺寸走 size class 分桶，同一桶内的空闲块不与邻桶合并；大尺寸直接走 mmap，释放时归还内核。所以「1.5 倍能吃回旧内存」更像是在 dlmalloc 那类合并空闲块的分配器上成立的结论。引擎判得了前缀和够不够，判不了分配器肯不肯合并。

4 · 缩容的滞后区间

删到只剩几个元素时，那块大内存该不该还回去？朴素做法是「长度低于容量的一半就减半」，而它有一个坑。

设容量 32、长度 17。连续两次 pop 之后长度 15，低于 16，缩容到 16 并复制 15 个元素；接着两次 push，长度 17 超过 16，扩容回 32 并复制 16 个元素。这个四步循环可以无限重复，每一轮都搬两次全表。这种在阈值两侧反复横跳的现象叫 thrashing。

图 4-1 · 先 push 到 17 再重复「两次 pop 加两次 push」，逐步记录容量变化与复制量。可改缩容阈值与缩容目标，对比阈值贴近扩容阈值与留出滞后区间两种口径。

实测这段循环 80 次操作：缩容阈值取 0.5 时触发 40 次重分配、复制 620 个元素；阈值降到 0.4 及以下，同一串操作一次重分配都没有。这一整段代价的开关就是那条阈值线的位置——扩容看满、缩容看 1/4，中间留出的那一大段什么都不做，就是滞后区间。

工程上更常见的做法是干脆不缩。Go 的 slice 只在 append 时增长，s = s[:0] 之后容量原样留着；Java 的 ArrayList.remove 从不减小 elementData 的长度；C++ 的 std::vector 把缩容做成显式请求 shrink_to_fit，而且标准只把它写成「非强制的请求」。Redis 的 SDS 走的也是这条路，它把 sdsclear 定义为只把长度归零、alloc 原样留着，具体见 SDS：Redis 的字符串 §4。

代价是使用方得知道这件事：装过一百万条的容器清空后仍占着一百万个槽，要真的还内存只能整个丢掉重建。

5 · 参考文献

Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed., §17.4 动态表). MIT Press.
Facebook. FBVector 设计说明. folly/docs/FBVector.md（1.5 倍增长与内存复用一节）。
ISO/IEC. (2020). ISO/IEC 14882:2020 Programming languages — C++, §22.3.11.3（vector 的容量操作与 shrink_to_fit）。
Evans, J. (2006). A scalable concurrent malloc(3) implementation for FreeBSD. Proceedings of BSDCan 2006.