确保列表的容量

Question

我正在浏览如何创建自己的列表，并登陆这个网站，http://www.vogella.com/tutorials/JavaDatastructureList/article.html 他们有以下方法。

private void ensureCapa() {
    int newSize = elements.length * 2;
    elements = Arrays.copyOf(elements, newSize);
}

我在许多其他站点中发现了类似的方法，并了解了ensureCapacity的作用。但我不明白为什么长度乘以 2(elements.length * 2(。是否有特定原因或因数据类型而异？

提前谢谢。

Answer 1

当

列表已满时，将列表的容量加倍有几个原因。

正如@jheimbouch和@user3437460所说，这在直觉上有点有意义。您希望将其与列表的当前大小成一定比例地增加。每次在末尾添加一些固定元素最终可能会对一个大胖列表非常糟糕。

一般来说，它更有效率。如果您不太清楚列表的大小(例如在设计自己的基于数组的列表类以供常规使用时(，如果每次将列表的大小加倍，那么平均而言，在每大组插入中，每次插入将花费O(1)恒定时间(这称为摊销常量时间操作(。

想想看，调整数组大小的成本是n。因此，我们唯一可以调整的就是我们这样做的频率。我们这样做的频率越高，数组与实际数据大小的绑定就越紧密，因此我们消耗的内存就越少。我们这样做的频率越低，我们就可以节省 CPU 周期。

关于时间复杂度的证据比比皆是，但这里有一个我很快发现 http://anh.cs.luc.edu/363/notes/06A_Amortizing.html

长话短说，它在一般情况下在数学上是合理的，并且在内存消耗和处理时间之间取得了很好的平衡。

Answer 2

这是一种

常见的做法，因此不必一直复制数组。例如，如果它是elements.length + 1，则每次添加元素时，您都会复制到一个新数组。

所以简而言之，这是任意的，你可以通过你选择的任何方式增加大小。

Answer 3

但我不明白为什么长度乘以 2(elements.length * 2(。是否有特定原因或因数据类型而异？

您不希望将大小增加一个固定值，例如 5。通过根据您当前的元素数量将容量加倍以在一定程度上确保效率(这样您就不必一直执行阵列拷贝(。

想象一下，你有 1000 个元素，

现在它已经满了，把它加倍是合乎逻辑的，因为有可能再有 1000 个元素进来。但是，如果使用固定值添加容量，则可能会添加过多或过少的容量。

当你添加太多时，你会浪费内存，但如果你添加的很少，你可能需要过于频繁地执行数组的另一个复制，这是没有效率的，因为这意味着你更有可能在添加新元素时调整当前数组。