为什么用初始容量启动数组列表？

小开

最佳答案

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

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

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

小开

将 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可以扩展，如果需要的话。这并没有告诉您数组列表的大小通常会加倍(尽管注意新的大小取决于您的实现)。以下引自神使:

”每个 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 存储的元素数量有任何想法，最好创建这样大小的数组列表，而不是从10开始，然后继续增加。

小开

我认为每个 ArrayList 都是以“10”的 init 容量值创建的。无论如何，如果你创建一个 ArrayList 而没有在构造函数中设置容量，那么它将被创建为一个默认值。

小开

ArrayList 可以包含许多值，当执行大的初始插入时，您可以告诉 ArrayList 分配一个更大的存储空间，以便在尝试为下一项分配更多空间时不会浪费 CPU 周期。因此在开始时分配一些空间是更有效的。

小开

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

要拥有一个清单，其中包含您需要调用 ()的项目数

小开

因为 ArrayList是动态调整数组大小数据结构，这意味着它实现为一个初始(默认)固定大小的数组。当这个数组被填满时，数组将被扩展为双倍大小的数组。这个手术费用很高，所以你想要尽可能少的手术。

所以，如果你知道你的上限是20个项目，那么创建一个初始长度为20的数组比使用默认的，比如说，15，然后调整它的大小为 15*2 = 30，只使用20而浪费了展开的周期要好。

P.S.-正如 AmitG 所说，扩展因素是特定于实现的(在本例中为 (oldCapacity * 3)/2 + 1)

小开

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

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

在内部创建 new Object[]。在数组列表中添加元素时，JVM 需要努力创建 new Object[]。如果你没有上面的代码(任何你认为的算法)来重新分配，那么每次当你调用 arraylist.add()时，就必须创建 new Object[]，这是毫无意义的，我们正在浪费时间为每个要添加的对象增加1的大小。因此，按照以下公式增加 Object[]的粒径效果较好。
(JSL 使用下面给出的预测公式对动态增长的数组表进行预测，而不是每次增长1。因为它的增长需要 JVM 的努力)

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

小开

事实上，两个月前我就这个话题写了一篇博客文章。本文针对的是 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% + 1增加到 16。在第17个项目的 ArrayList再次增加到 25等等。现在考虑这个例子，我们正在创建一个列表，其中所需的容量已经被称为 1000000。创建没有大小构造函数的 ArrayList将调用 ArrayList.add1000000次，这通常需要 O (1)或者调整大小时需要 50% + 10。

1000000 + 16 + 25 + ... + 670205 + 1005308 = 4015851行动

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

1000000 + 1000000 = 2000000业务

Java VS C #

Java 和上面一样，从 10开始，在 50% + 1增加每次调整的大小。C # 从 4开始，增长更加迅猛，每次调整大小都会增加一倍。1000000为 C # 使用 3097084操作增加了上面的例子。

参考文献

小开

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

小开

我已经测试了数组列表有和没有初始容量，我得到了令人惊讶的结果
当我将 LOOP _ NUMBER 设置为100,000或更少时，结果是设置 initialScale 是有效的。

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上进行了测试