为什么要以初始容量启动 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.

也就是说，即使没有预分配，在 ArrayList 后面插入 n 个元素也保证占用 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屋！