我注意到实现动态数组非常常见(特别是在面试问题和家庭作业中); 通常,我看到的问题是:
实现一个阵列,当满了时容量翻倍
或者非常相似的东西.他们几乎总是(根据我的经验)明确地使用双词,而不是更一般
实现一个阵列,在满员时增加容量
我的问题是,为什么加倍？我理解为什么使用常量值是个坏主意(感谢这个问题),但似乎使用更大的倍数而不是双倍更有意义; 为什么不将容量增加三倍,或者将容量增加四倍,或者将其平方？
要清楚,我不是要问如何将数组的容量加倍,我问为什么加倍是常规.
是的，这是常见的做法。
加倍是管理内存的好方法。堆管理算法通常基于经典的 Buddy System，这是处理寻址、合并和其他挑战的简单方法。知道了这一点，在处理分配时最好坚持使用 2 的倍数（尽管有一些混合算法，如平板分配器，可以帮助解决碎片问题，因此使用倍数并不像以前那么重要）。
高德纳在他的一本书中对此进行了介绍，我已经忘记了书名。
请参阅http://en.wikipedia.org/wiki/Buddy_memory_allocation
将数组大小加倍的另一个原因是增加成本。您不希望每个 Add() 操作都触发重新分配调用。如果你已经填满了 N 个槽位，那么你很有可能需要 N 的倍数，历史是未来需求的良好指标，因此该对象需要“毕业”到下一个竞技场大小。通过加倍，重新分配的频率呈对数下降 (Log N)。加倍只是最方便的倍数（作为最小的整体乘数，它比 3*N 或 4*N 的内存效率更高，而且它往往紧密遵循堆内存管理模型）。