为什么开始用一个初始容量的ArrayList？ [英] Why start an ArrayList with an initial capacity?

问题描述

的的ArrayList 常用的构造函数是：

ArrayList<?> list = new ArrayList<>();

但也有一个重载的构造与初始容量的参数：

But there is also an overloaded constructor with a parameter for its initial capacity:

ArrayList<?> list = new ArrayList<>(20);

为什么有用创建一个的ArrayList 用我们可以追加到它，因为我们请的初始容量？

Why is it useful to create an ArrayList with an initial capacity when we can append to it as we please?

推荐答案

如果你事先知道的ArrayList 将是规模，更高效指定的初始容量。如果你不这样做，内部数组将不得不被反复重新分配的名单不断增加。

If you know in advance what the size of the ArrayList is going to be, it is more efficient to specify the initial capacity. If you don't do this, the internal array will have to be repeatedly reallocated as the list grows.

较大的最终名单，更多的时候，你通过避免重新分配存储。

The larger the final list, the more time you save by avoiding the reallocations.

这是说，即使没有pre-分配，插入 N 在一个后面的元素的ArrayList 保证采取总 O（N）的时间。换言之，追加的元件是一个摊销固定时间操作。这是通过使每个再分配增加数组的大小按指数，典型地通过的一个因子达到1.5 。通过这种方法，总人数的操作的可以被证明是 O（N） 。

That said, even without pre-allocation, inserting n elements at the back of an ArrayList is guaranteed to take total O(n) time. In other words, appending an element is an amortized constant-time operation. This is achieved by having each reallocation increase the size of the array exponentially, typically by a factor of 1.5. With this approach, the total number of operations can be shown to be O(n).

这篇关于为什么开始用一个初始容量的ArrayList？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！