java - 保证List的容量

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。所以我们唯一可以调整的就是我们这样做的频率。我们这样做的次数越多，数组与实际数据大小的绑定(bind)就越紧密，因此我们使用的内存就越少。我们这样做的次数越少，我们就可以节省 CPU 周期。

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

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