如何定义ArrayList中容量的概念？

Question

据我所知，容量是 ArrayList 中可能包含也可能不包含引用对象的值的元素或可用空间的数量。我正在尝试更多地了解容量的概念。

所以我有三个问题：

1）从内存的角度来看，有哪些好的方法来定义容量代表什么？

...分配给 ArrayList 的（连续？）内存？

...ArrayLists 在（堆？）上的内存占用？

2）那么如果上述情况成立，改变容量需要某种方式的内存管理开销？

3）有人有一个例子，其中#2是或可能是性能问题吗？除了可能不断调整其容量的大量大型 ArrayList 之外？

Answer 1

1. 该类称为 ArrayList，因为它基于数组。容量是数组的大小，需要一块连续的堆内存。但是，请注意，数组本身仅包含对元素的引用，这些元素是堆上的单独对象。
2. 增加容量需要分配一个更大的新数组，并将旧数组中的所有引用复制到新数组，之后旧数组就可以进行垃圾回收。
3. 您引用了性能可能成为问题的主要案例。在实践中，我从未见过它真正成为问题，因为元素对象通常比列表占用更多的内存（可能还有 CPU 时间）。

Answer 2

ArrayList 的实现方式如下：

class ArrayList {
  private Object[] elements;
}

容量是该数组的大小。

现在，如果你的容量是 10，并且你要添加第 11 个元素，ArrayList 会执行以下操作：

Object[] newElements = new Object[capacity * 1.5];
System.arraycopy(this.elements, newElements);
this.elements = newElements;

因此，如果你从较小的容量开始，ArrayList 最终将创建一堆数组并为你复制内容。不断添加元素，这不好。

另一方面，如果您指定 1,000,000 的容量并仅向 ArrayList 添加 3 个元素，这也有点糟糕。

经验法则：如果您知道容量，请指定它。如果您不确定但知道上限，请指定。如果您不确定，请使用默认值。

Answer 3

容量正如您所描述的那样——分配给 ArrayList 用于存储值的连续内存。 ArrayList 将所有值存储在数组中，并自动为您调整数组的大小。调整大小时这会产生内存管理开销。

如果我没记错的话，当您尝试添加一个超出容量的元素时，Java 会将 ArrayList 的支持数组的大小从大小 N 增加到大小 2N + 2。我不知道当您使用 insert 方法（或类似方法）在超出容量末尾的特定位置插入时，它会增加到什么大小，甚至不知道它是否允许这样做。

这是一个帮助您思考其工作原理的示例。将 | 之间的每个空格想象为后备数组中的一个单元格：

| | |

大小 = 0（不包含任何元素），容量 = 2（可以包含 2 个元素）。

|1| |

大小 = 1（包含 1 个元素），容量 = 2（可以包含 2 个元素）。

|1|2|

size = 2，capacity = 2。添加另一个元素：

|1|2|3| | | |

size 增加 1，capacity 增加到 6 (2 * 2 + 2)。对于大型数组来说，这可能会很昂贵，因为分配一个大的连续内存区域可能需要一些工作（与分配许多小块内存的 LinkedList 相反），因为 JVM 需要搜索适当的位置，并且可能需要向操作系统请求更多内存。将大量值从一个地方复制到另一个地方的成本也很高，一旦找到这样的区域就会完成这一操作。

我的经验法则是：如果您知道所需的容量，请使用 ArrayList，因为只有一次分配，并且访问速度非常快。如果您不知道所需的容量，请使用 LinkedList，因为添加新值始终需要相同的工作量，并且不涉及复制。

Answer 4

1) 从内存的角度定义容量代表什么有哪些好方法？

...分配给 ArrayList 的（连续？）内存？

是的，ArrayList 是由数组支持，代表内部数组大小。

...ArrayList 在（堆？）上的内存占用？

是的，数组容量越大，ArrayList 使用的内存就越多。

2）如果上述情况成立，更改容量需要某种形式的内存管理开销？

是的。当列表增长到足够大时，会分配一个更大的数组并复制内容。先前的数组可能会被丢弃并标记为垃圾回收。

3) 有人有一个例子，其中 #2 是或可能是性能问题吗？除了可能不断调整容量的大量大型 ArrayList 之外？

是的，如果您创建初始容量为 1 的 ArrayList（例如），并且列表的增长远远超出了该容量。如果您预先知道要存储的元素数量，则最好请求该大小的初始容量。

但是我认为这在你的优先级列表中应该是较低的，虽然数组复制可能经常发生，但它从Java的早期阶段就已经被优化了，不应该成为一个问题。我认为更好的是选择正确的算法。请记住：过早优化是万恶之源

另请参阅：何时使用 LinkedList 而不是 ArrayList