java - 向 Java 列表添加/删除条目是否会重新分配内存？

Question

这是关于 Java 如何在 ArrayList 或其他类型的列表上执行 .add 和 .remove 的低级内存问题。我认为 Java 必须重新分配内存才能向列表添加/删除项目，但它可能会做一些我没有想到的事情来避免这种情况。有谁知道吗？

Answer 1

如果您所说的“常规列表”是指java.util.List，那么它就是一个接口(interface)。它没有指定任何关于是否或何时分配与添加或删除元素相关的内存的任何信息——这些是特定实现的细节。

特别是对于java.util.ArrayList，它的文档说:

Each ArrayList instance has a capacity. The capacity is the size of the array used to store the elements in the list. It is always at least as large as the list size. As elements are added to an ArrayList, its capacity grows automatically. The details of the growth policy are not specified beyond the fact that adding an element has constant amortized time cost.

换句话说，Java 并没有指定你的问题的答案。

如果我根据可用文档进行推测，我会猜测 java.util.ArrayList.remove() 永远不会执行任何内存分配或重新分配。从总体文档来看，java.util.ArrayList.add() 至少有时会分配额外的空间(以新的、更长的内部数组的形式)。然而，为了实现元素添加的恒定摊销成本，我不知道它如何在每个元素添加上重新分配。几乎可以肯定，它仅在容量不足时才重新分配，然后按一个常数因子缩放容量 - 例如加倍。