arrays - 为什么通常的做法是在已满时将阵列容量加倍？

Question

我注意到实现动态数组是很常见的(尤其是在面试问题和家庭作业中)；通常，我认为问题的表述如下:

Implement an array which doubles in capacity when full

或者非常相似的东西。他们几乎总是(以我的经验)使用这个词 双明确的，而不是更一般的

Implement an array which increases in capacity when full

我的问题是，为什么要翻倍？我理解为什么使用常数值是一个坏主意(感谢 this question )，但似乎使用比两倍更大的倍数更有意义；为什么不将容量增加三倍、四倍或平方呢？

需要明确的是，我不是在问 怎么样要将数组的容量加倍，我在问 为什么加倍是惯例。

Answer 1

是的，这是常见的做法。

加倍是管理内存的好方法。堆管理算法通常基于经典的好友系统，这是处理寻址和合并以及其他挑战的一种简单方法。知道了这一点，在处理分配时坚持使用 2 的倍数是很好的(尽管有混合算法，如slab 分配器，以帮助处理碎片，所以它不像以前使用倍数那么重要)。

克努斯在他的一本书中介绍了它，我有但忘记了书名。

见 http://en.wikipedia.org/wiki/Buddy_memory_allocation

将数组大小加倍的另一个原因是增加成本。您不希望每个 Add() 操作都触发重新分配调用。如果你已经填满了 N 个插槽，那么无论如何你很有可能需要 N 的倍数，历史是 future 需求的一个很好的指标，所以对象需要“升级”到下一个竞技场大小。通过加倍，重新分配的频率呈对数下降 (Log N)。加倍只是最方便的倍数(作为最小的整数倍数，它比 3*N 或 4*N 的内存效率更高，而且它倾向于密切遵循堆内存管理模型)。