157

通常的构造函数ArrayList是：

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

但是还有一个重载的构造函数，它的初始容量带有一个参数：

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

ArrayList当我们可以随心所欲地附加到它时，为什么创建一个具有初始容量的有用？

4

11 回答 11

204

如果您事先知道 的大小将ArrayList是多少，则指定初始容量会更有效。如果你不这样做，随着列表的增长，内部数组将不得不重复重新分配。

最终列表越大，通过避免重新分配节省的时间就越多。

也就是说，即使没有预先分配，n在 an 的后面插入元素ArrayList也可以保证花费总O(n)时间。换句话说，附加一个元素是一个摊销的常数时间操作。这是通过让每个重新分配以指数方式增加数组的大小来实现的，通常是1.5. 使用这种方法，操作的总数可以显示为O(n)。

于 2013-03-15T10:41:57.250 回答
41

因为ArrayList是一个动态调整大小的数组数据结构，这意味着它被实现为一个具有初始（默认）固定大小的数组。当它被填满时，数组将被扩展为一个双倍大小的数组。此操作成本高昂，因此您希望尽可能少。

因此，如果您知道上限是 20 个项目，那么创建初始长度为 20 的数组比使用默认值（例如 15）更好，然后将其调整为15*2 = 30仅使用 20，同时浪费循环进行扩展。

PS - 正如 AmitG 所说，扩展因子是特定于实现的（在这种情况下(oldCapacity * 3)/2 + 1）

于 2013-03-15T10:47:03.330 回答
25

Arraylist 的默认大小为10。

/**
 * Constructs an empty list with an initial capacity of ten.
 */
public ArrayList() {
    this(10);
}

因此，如果您要添加 100 条或更多记录，您可以看到内存重新分配的开销。

ArrayList<?> list = new ArrayList<>();    
// same as  new ArrayList<>(10);

因此，如果您对将存储在 Arraylist 中的元素数量有任何想法，最好创建具有​​该大小的 Arraylist，而不是从 10 开始然后继续增加它。

于 2013-03-15T10:44:05.860 回答
17

实际上，我在 2 个月前就该主题写了一篇博文。这篇文章是针对 C# 的，List<T>但 Java 的ArrayList实现非常相似。由于ArrayList是使用动态数组实现的，因此它会按需增加大小。所以容量构造函数的原因是为了优化目的。

当这些调整大小操作之一发生时，ArrayList 将数组的内容复制到一个新数组中，该数组的容量是旧数组的两倍。此操作在O(n)时间内运行。

例子

这是一个如何ArrayList增加大小的示例：

10
16
25
38
58
... 17 resizes ...
198578
297868
446803
670205
1005308

所以列表以容量 开始10，当添加第 11 项时，它会增加50% + 1to 16。第 17 项ArrayList再次增加到25以此类推。现在考虑我们正在创建一个列表的示例，其中所需容量已被称为1000000. 创建ArrayList没有大小构造函数的将调用通常ArrayList.add 1000000需要O(1)或调整大小需要 O (n)的时间。

1000000 + 16 + 25 + ... + 670205 + 1005308 = 4015851 次操作

使用构造函数进行比较，然后调用ArrayList.add保证在O(1)中运行。

1000000 + 1000000 = 2000000 次操作

Java 与 C#

Java 如上所述，从 开始10并增加每次调整大小50% + 1。C# 从开始4并以更积极的方式增加，每次调整大小都会翻倍。上面 C#的1000000添加示例使用3097084操作。

参考

于 2013-03-16T05:44:04.843 回答
10

将 ArrayList 的初始大小设置为 ，例如ArrayList<>(100)，可以减少重新分配内部存储器的次数。

例子：

ArrayList example = new ArrayList<Integer>(3);
example.add(1); // size() == 1
example.add(2); // size() == 2, 
example.add(2); // size() == 3, example has been 'filled'
example.add(3); // size() == 4, example has been 'expanded' so that the fourth element can be added.

正如您在上面的示例中看到的 -ArrayList如果需要，可以扩展 an。这并没有向您显示 Arraylist 的大小通常会翻倍（尽管请注意，新大小取决于您的实现）。以下引自Oracle：

“每个 ArrayList 实例都有一个容量。容量是用于存储列表中元素的数组的大小。它始终至少与列表大小一样大。随着元素被添加到 ArrayList，它的容量会自动增长。除了添加一个元素具有恒定的摊销时间成本这一事实之外，没有具体说明增长政策的细节。”

显然，如果你不知道你将持有什么样的范围，设置大小可能不是一个好主意 - 但是，如果你确实有一个特定的范围，设置一个初始容量将提高内存效率.

于 2013-03-15T10:42:43.160 回答
3

ArrayList 可以包含许多值，并且在进行大量初始插入时，您可以告诉 ArrayList 在开始时分配更大的存储空间，以免在尝试为下一项分配更多空间时浪费 CPU 周期。因此，在开始时分配一些空间更有效。

于 2013-03-15T10:45:51.457 回答
3

这是为了避免为每个对象重新分配可能的努力。

int newCapacity = (oldCapacity * 3)/2 + 1;

内部new Object[]创建。当您在 arraylist 中添加元素时，
JVM 需要努力创建 。new Object[]如果您没有上述代码（您认为的任何算法）进行重新分配，那么每次调用arraylist.add()then时new Object[]都必须创建，这是没有意义的，我们正在浪费时间将每个要添加的对象的大小增加 1。所以最好Object[]用下面的公式来增加大小。
（JSL 使用下面给出的预测公式来动态增长 arraylist，而不是每次增长 1。因为增长需要 JVM 的努力）

int newCapacity = (oldCapacity * 3)/2 + 1;
于 2013-03-15T12:09:46.930 回答
2

我认为每个 ArrayList 的初始容量值为“10”。所以无论如何，如果您创建一个 ArrayList 而不在构造函数中设置容量，它将使用默认值创建。

于 2013-03-15T10:44:14.300 回答
2

我会说它是一种优化。没有初始容量的 ArrayList 将有大约 10 个空行，并且会在您进行添加时扩展。

要获得一个包含您需要调用trimToSize()的项目数量的列表

于 2013-03-15T10:46:23.040 回答
0

根据我的经验ArrayList，提供初始容量是避免重新分配成本的好方法。但它有一个警告。上面提到的所有建议都说，只有在知道元素数量的粗略估计时才应该提供初始容量。但是当我们试图在不知道任何想法的情况下给出初始容量时，保留和未使用的内存量将是一种浪费，因为一旦列表填充到所需数量的元素，它可能永远不需要。我的意思是，我们可以在分配容量时一开始就务实，然后找到一种聪明的方法来了解运行时所需的最小容量。ArrayList 提供了一个名为ensureCapacity(int minCapacity). 但后来，人们找到了一个聪明的方法......

于 2013-04-13T07:31:39.347 回答
0

我已经测试了有和没有 initialCapacity 的 ArrayList，我得到了令人惊讶的结果
当我将 LOOP_NUMBER 设置为 100,000 或更少时，结果是设置 initialCapacity 是有效的。 

list1Sttop-list1Start = 14
list2Sttop-list2Start = 10


但是当我将 LOOP_NUMBER 设置为 1,000,000 时，结果变为： 

list1Stop-list1Start = 40
list2Stop-list2Start = 66


最后，我无法弄清楚它是如何工作的？！
示例代码：

 public static final int LOOP_NUMBER = 100000;

public static void main(String[] args) {

    long list1Start = System.currentTimeMillis();
    List<Integer> list1 = new ArrayList();
    for (int i = 0; i < LOOP_NUMBER; i++) {
        list1.add(i);
    }
    long list1Stop = System.currentTimeMillis();
    System.out.println("list1Stop-list1Start = " + String.valueOf(list1Stop - list1Start));

    long list2Start = System.currentTimeMillis();
    List<Integer> list2 = new ArrayList(LOOP_NUMBER);
    for (int i = 0; i < LOOP_NUMBER; i++) {
        list2.add(i);
    }
    long list2Stop = System.currentTimeMillis();
    System.out.println("list2Stop-list2Start = " + String.valueOf(list2Stop - list2Start));
}

我在 windows8.1 和 jdk1.7.0_80 上测试过

于 2016-06-04T13:56:17.973 回答