为什么使用不同的 ArrayList 构造函数会导致内部数组的增长率不同？
Why does using different ArrayList constructors cause a different growth rate of the internal array?
我似乎在 ArrayList 实现中偶然发现了一些我无法理解的有趣的东西。这里有一些代码可以说明我的意思：
public class Sandbox {
private static final VarHandle VAR_HANDLE_ARRAY_LIST;
static {
try {
Lookup lookupArrayList = MethodHandles.privateLookupIn(ArrayList.class, MethodHandles.lookup());
VAR_HANDLE_ARRAY_LIST = lookupArrayList.findVarHandle(ArrayList.class, "elementData", Object[].class);
} catch (Exception e) {
e.printStackTrace();
throw new RuntimeException();
}
}
public static void main(String[] args) {
List<String> defaultConstructorList = new ArrayList<>();
defaultConstructorList.add("one");
Object[] elementData = (Object[]) VAR_HANDLE_ARRAY_LIST.get(defaultConstructorList);
System.out.println(elementData.length);
List<String> zeroConstructorList = new ArrayList<>(0);
zeroConstructorList.add("one");
elementData = (Object[]) VAR_HANDLE_ARRAY_LIST.get(zeroConstructorList);
System.out.println(elementData.length);
}
}
这个想法是，如果你创建一个 ArrayList 像这样：
List<String> defaultConstructorList = new ArrayList<>();
defaultConstructorList.add("one");
然后查看 elementData（Object[] 保留所有元素的地方），它将报告 10。因此，您添加一个元素 - 您会得到 9 个未使用的额外插槽。
另一方面，如果您这样做：
List<String> zeroConstructorList = new ArrayList<>(0);
zeroConstructorList.add("one");
你添加一个元素，space reserved 只是那个元素，仅此而已。
在内部这是通过两个字段实现的：
/**
* Shared empty array instance used for empty instances.
*/
private static final Object[] EMPTY_ELEMENTDATA = {};
/**
* Shared empty array instance used for default sized empty instances. We
* distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when
* first element is added.
*/
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
当您通过 new ArrayList(0) 创建 ArrayList 时 - EMPTY_ELEMENTDATA 将被使用。
当您通过 new Arraylist() 创建 ArrayList 时 - 使用 DEFAULTCAPACITY_EMPTY_ELEMENTDATA。
我内心的直觉部分 - 只是尖叫 "remove DEFAULTCAPACITY_EMPTY_ELEMENTDATA" 并让所有情况都用 EMPTY_ELEMENTDATA 处理；当然是代码注释：
We distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when first element is added
确实有道理，但为什么一个会膨胀到 10（比我要求的多很多）而另一个会膨胀到 1（完全符合我的要求）。
即使您使用 List<String> zeroConstructorList = new ArrayList<>(0)，并不断添加元素，最终您也会达到 elementData 大于请求的那个点：
List<String> zeroConstructorList = new ArrayList<>(0);
zeroConstructorList.add("one");
zeroConstructorList.add("two");
zeroConstructorList.add("three");
zeroConstructorList.add("four");
zeroConstructorList.add("five"); // elementData will report 6, though there are 5 elements only
但它的增长速度比默认构造函数的情况要小。
这让我想起了 HashMap 实现，其中桶的数量几乎总是比您要求的多；但这样做是因为需要 "power of two" 个桶，但这里不是这种情况。
所以问题是 - 谁能给我解释一下这个区别？
您的问题的简短答案是 Java 文档中的内容：我们有 两个 常量，因为我们现在需要能够区分 两个后面的不同初始化，见下文。
他们当然可以引入例如两个常数而不是两个常数。 ArrayList、private boolean initializedWithDefaultCapacity 中的布尔字段；但这将需要额外的内存每个实例，这似乎违背了节省几个字节内存的目标。
为什么我们需要区分这两者？
查看 ensureCapacity() 我们会看到 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 会发生什么：
public void ensureCapacity(int minCapacity) {
int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
// any size if not default element table
? 0
// larger than default for default empty table. It's already
// supposed to be at default size.
: DEFAULT_CAPACITY;
if (minCapacity > minExpand) {
ensureExplicitCapacity(minCapacity);
}
}
这样做似乎有点 'compatible' 旧实现的行为：
如果你用默认容量初始化列表，现在它实际上会用一个空数组初始化，但是，一旦插入第一个元素，它就会基本上恢复到与旧实现相同的行为，即添加第一个元素后，后备数组具有 DEFAULT_CAPACITY，从那时起，列表的行为与以前相同。
另一方面，如果您明确指定初始容量，则数组不会 'jump' 到 DEFAULT_CAPACITY，而是从您指定的初始容量相对增长。
我认为这个 'optimization' 的原因可能是您知道您将只在列表中存储一个或两个（即少于 DEFAULT_CAPACITY）元素并且您指定初始值的情况相应的容量；在这些情况下，例如对于 single-element 列表，您只会得到一个 single-element 数组，而不是 DEFAULT_CAPACITY 大小的数组。
不要问我保存九个引用类型的数组元素有什么实用好处。每个列表可能最多约 9*64 位 = 72 字节的 RAM。是的。 ;-)
这很可能是因为两个构造函数具有不同的感知默认用途。
默认（空）构造函数假定这将是一个 "typical ArrayList"。因此，数字 10 被选为一种启发式算法，又名 "what the typical average number of elements inserted will be that will not take up too much space but will not grow the array needlessly too"。另一方面，容量构造函数有"you know what you're doing"或"you know what you will be using the ArrayList for"的预设。因此，不存在这种类型的启发式方法。
如果使用默认构造函数，其思路是尽量平衡内存使用和重新分配。因此，使用较小的默认大小 (10) 应该适合大多数应用程序。
如果您使用具有显式大小的构造函数，则假定您知道自己在做什么。如果你用 0 初始化它，你实际上是在说：我很确定它要么保持为空，要么不会超出很少的元素。
现在，如果您查看 openjdk (link) 中 ensureCapacityInternal 的实现，您会发现只有在第一次添加项目时，这种差异才会发挥作用：
private void ensureCapacityInternal(int minCapacity) {
if (elementData == EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
如果使用默认构造函数，大小会增长到DEFAULT_CAPACITY (10)。这是为了防止在添加多个元素时进行过多的重新分配。但是，如果您显式创建了大小为 0 的 ArrayList，它只会在您添加的第一个元素上增长到大小 1。这是因为你告诉它你知道自己在做什么。
ensureExplicitCapacity 基本上只是调用 grow（有一些 range/overflow 检查），所以让我们看一下：
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}
如您所见，它并没有简单地增长到特定大小，而是试图变得聪明。数组越大，即使 minCapacity 只比当前容量大 1，它也会增长得更大。这背后的原因很简单：如果列表已经很大，则添加 lof 项的可能性更高，反之亦然。这也是为什么您会看到在第 5 个元素之后增长先增加 1 然后再增加 2 的原因。
默认构造函数的容量为 10，因为 the docs say so。它会被选为一个明智的折衷方案，既不会马上用完太多内存，又不会在添加前几个元素时不必执行大量数组复制。
零行为有点推测性，但我对我的推理很有信心：
这是因为如果你明确地初始化一个大小为零的ArrayList，然后向它添加一些东西，你说的是"I'm not expecting this list to hold much, if anything at all."因此缓慢地增长支持数组更有意义，就好像它是用值 1 初始化的，而不是将其视为没有指定初始值。所以它处理了将它增长到只有 1 个元素的特殊情况，然后照常进行。
然后完成图片，ArrayList 显式初始化为 1 的大小预计会比默认增长慢得多（直到它达到默认的“10 元素”大小）一个，否则没有理由首先用一个小值初始化它。
but why would one inflate to 10 (a lot more than I asked for) and the other one to 1 (exactly as much as I requested)
可能是因为大多数创建列表的人都希望在其中存储 多于 1 个元素。
你知道，当你只需要一个条目时，为什么不使用 Collections.singletonList() 例如。
换句话说，我认为答案是实用主义。当您使用默认构造函数时，典型 用例是您可能要快速添加少量元素。
含义："unknown"被解释为"a few"，而"exactly 0 (or 1)"被解释为"hmm, exactly 0 or 1"。
你得到的正是你所要求的，相应的指定的内容，即使在旧版本中，实现是不同的：
ArrayList()
Constructs an empty list with an initial capacity of ten.
ArrayList(int)
Constructs an empty list with the specified initial capacity.
因此，使用默认构造函数构造 ArrayList 将为您提供初始容量为 10 的 ArrayList，因此只要列表大小为 10 或更小，就不会进行调整大小操作永远需要。
相比之下，带有int参数的构造函数将精确地使用指定的容量，以growing policy为准
The details of the growth policy are not specified beyond the fact that adding an element has constant amortized time cost.
即使您将初始容量指定为零也适用。
Java 8 添加十元素数组的创建被推迟到第一个元素被添加的优化。这专门解决了 ArrayList 个实例（使用默认容量创建）长时间甚至整个生命周期都为空的常见情况。此外，当第一个实际操作是 addAll 时，它可能会跳过第一个数组调整大小操作。这不会影响具有明确初始容量的列表，因为通常会仔细选择这些列表。
如所述：
According to our performance analysis team, approximately 85% of ArrayList instances are created at default size so this optimization will be valid for an overwhelming majority of cases.
动机是精确优化这些场景，而不是触及指定的默认容量，这是在创建 ArrayList 时定义的。 （虽然 JDK 1.4 是第一个明确指定它的人）
我似乎在 ArrayList 实现中偶然发现了一些我无法理解的有趣的东西。这里有一些代码可以说明我的意思：
public class Sandbox {
private static final VarHandle VAR_HANDLE_ARRAY_LIST;
static {
try {
Lookup lookupArrayList = MethodHandles.privateLookupIn(ArrayList.class, MethodHandles.lookup());
VAR_HANDLE_ARRAY_LIST = lookupArrayList.findVarHandle(ArrayList.class, "elementData", Object[].class);
} catch (Exception e) {
e.printStackTrace();
throw new RuntimeException();
}
}
public static void main(String[] args) {
List<String> defaultConstructorList = new ArrayList<>();
defaultConstructorList.add("one");
Object[] elementData = (Object[]) VAR_HANDLE_ARRAY_LIST.get(defaultConstructorList);
System.out.println(elementData.length);
List<String> zeroConstructorList = new ArrayList<>(0);
zeroConstructorList.add("one");
elementData = (Object[]) VAR_HANDLE_ARRAY_LIST.get(zeroConstructorList);
System.out.println(elementData.length);
}
}
这个想法是，如果你创建一个 ArrayList 像这样：
List<String> defaultConstructorList = new ArrayList<>();
defaultConstructorList.add("one");
然后查看 elementData（Object[] 保留所有元素的地方），它将报告 10。因此，您添加一个元素 - 您会得到 9 个未使用的额外插槽。
另一方面，如果您这样做：
List<String> zeroConstructorList = new ArrayList<>(0);
zeroConstructorList.add("one");
你添加一个元素，space reserved 只是那个元素，仅此而已。
在内部这是通过两个字段实现的：
/**
* Shared empty array instance used for empty instances.
*/
private static final Object[] EMPTY_ELEMENTDATA = {};
/**
* Shared empty array instance used for default sized empty instances. We
* distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when
* first element is added.
*/
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
当您通过 new ArrayList(0) 创建 ArrayList 时 - EMPTY_ELEMENTDATA 将被使用。
当您通过 new Arraylist() 创建 ArrayList 时 - 使用 DEFAULTCAPACITY_EMPTY_ELEMENTDATA。
我内心的直觉部分 - 只是尖叫 "remove DEFAULTCAPACITY_EMPTY_ELEMENTDATA" 并让所有情况都用 EMPTY_ELEMENTDATA 处理；当然是代码注释：
We distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when first element is added
确实有道理，但为什么一个会膨胀到 10（比我要求的多很多）而另一个会膨胀到 1（完全符合我的要求）。
即使您使用 List<String> zeroConstructorList = new ArrayList<>(0)，并不断添加元素，最终您也会达到 elementData 大于请求的那个点：
List<String> zeroConstructorList = new ArrayList<>(0);
zeroConstructorList.add("one");
zeroConstructorList.add("two");
zeroConstructorList.add("three");
zeroConstructorList.add("four");
zeroConstructorList.add("five"); // elementData will report 6, though there are 5 elements only
但它的增长速度比默认构造函数的情况要小。
这让我想起了 HashMap 实现，其中桶的数量几乎总是比您要求的多；但这样做是因为需要 "power of two" 个桶，但这里不是这种情况。
所以问题是 - 谁能给我解释一下这个区别？
您的问题的简短答案是 Java 文档中的内容：我们有 两个 常量，因为我们现在需要能够区分 两个后面的不同初始化，见下文。
他们当然可以引入例如两个常数而不是两个常数。 ArrayList、private boolean initializedWithDefaultCapacity 中的布尔字段；但这将需要额外的内存每个实例，这似乎违背了节省几个字节内存的目标。
为什么我们需要区分这两者？
查看 ensureCapacity() 我们会看到 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 会发生什么：
public void ensureCapacity(int minCapacity) {
int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
// any size if not default element table
? 0
// larger than default for default empty table. It's already
// supposed to be at default size.
: DEFAULT_CAPACITY;
if (minCapacity > minExpand) {
ensureExplicitCapacity(minCapacity);
}
}
这样做似乎有点 'compatible' 旧实现的行为：
如果你用默认容量初始化列表，现在它实际上会用一个空数组初始化，但是，一旦插入第一个元素，它就会基本上恢复到与旧实现相同的行为，即添加第一个元素后，后备数组具有 DEFAULT_CAPACITY，从那时起，列表的行为与以前相同。
另一方面，如果您明确指定初始容量，则数组不会 'jump' 到 DEFAULT_CAPACITY，而是从您指定的初始容量相对增长。
我认为这个 'optimization' 的原因可能是您知道您将只在列表中存储一个或两个（即少于 DEFAULT_CAPACITY）元素并且您指定初始值的情况相应的容量；在这些情况下，例如对于 single-element 列表，您只会得到一个 single-element 数组，而不是 DEFAULT_CAPACITY 大小的数组。
不要问我保存九个引用类型的数组元素有什么实用好处。每个列表可能最多约 9*64 位 = 72 字节的 RAM。是的。 ;-)
这很可能是因为两个构造函数具有不同的感知默认用途。
默认（空）构造函数假定这将是一个 "typical ArrayList"。因此，数字 10 被选为一种启发式算法，又名 "what the typical average number of elements inserted will be that will not take up too much space but will not grow the array needlessly too"。另一方面，容量构造函数有"you know what you're doing"或"you know what you will be using the ArrayList for"的预设。因此，不存在这种类型的启发式方法。
如果使用默认构造函数，其思路是尽量平衡内存使用和重新分配。因此，使用较小的默认大小 (10) 应该适合大多数应用程序。
如果您使用具有显式大小的构造函数，则假定您知道自己在做什么。如果你用 0 初始化它，你实际上是在说：我很确定它要么保持为空，要么不会超出很少的元素。
现在，如果您查看 openjdk (link) 中 ensureCapacityInternal 的实现，您会发现只有在第一次添加项目时，这种差异才会发挥作用：
private void ensureCapacityInternal(int minCapacity) {
if (elementData == EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
如果使用默认构造函数，大小会增长到DEFAULT_CAPACITY (10)。这是为了防止在添加多个元素时进行过多的重新分配。但是，如果您显式创建了大小为 0 的 ArrayList，它只会在您添加的第一个元素上增长到大小 1。这是因为你告诉它你知道自己在做什么。
ensureExplicitCapacity 基本上只是调用 grow（有一些 range/overflow 检查），所以让我们看一下：
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}
如您所见，它并没有简单地增长到特定大小，而是试图变得聪明。数组越大，即使 minCapacity 只比当前容量大 1，它也会增长得更大。这背后的原因很简单：如果列表已经很大，则添加 lof 项的可能性更高，反之亦然。这也是为什么您会看到在第 5 个元素之后增长先增加 1 然后再增加 2 的原因。
默认构造函数的容量为 10，因为 the docs say so。它会被选为一个明智的折衷方案，既不会马上用完太多内存，又不会在添加前几个元素时不必执行大量数组复制。
零行为有点推测性，但我对我的推理很有信心：
这是因为如果你明确地初始化一个大小为零的ArrayList，然后向它添加一些东西，你说的是"I'm not expecting this list to hold much, if anything at all."因此缓慢地增长支持数组更有意义，就好像它是用值 1 初始化的，而不是将其视为没有指定初始值。所以它处理了将它增长到只有 1 个元素的特殊情况，然后照常进行。
然后完成图片，ArrayList 显式初始化为 1 的大小预计会比默认增长慢得多（直到它达到默认的“10 元素”大小）一个，否则没有理由首先用一个小值初始化它。
but why would one inflate to 10 (a lot more than I asked for) and the other one to 1 (exactly as much as I requested)
可能是因为大多数创建列表的人都希望在其中存储 多于 1 个元素。
你知道，当你只需要一个条目时，为什么不使用 Collections.singletonList() 例如。
换句话说，我认为答案是实用主义。当您使用默认构造函数时，典型 用例是您可能要快速添加少量元素。
含义："unknown"被解释为"a few"，而"exactly 0 (or 1)"被解释为"hmm, exactly 0 or 1"。
你得到的正是你所要求的，相应的指定的内容，即使在旧版本中，实现是不同的：
ArrayList()
Constructs an empty list with an initial capacity of ten.
ArrayList(int)
Constructs an empty list with the specified initial capacity.
因此，使用默认构造函数构造 ArrayList 将为您提供初始容量为 10 的 ArrayList，因此只要列表大小为 10 或更小，就不会进行调整大小操作永远需要。
相比之下，带有int参数的构造函数将精确地使用指定的容量，以growing policy为准
The details of the growth policy are not specified beyond the fact that adding an element has constant amortized time cost.
即使您将初始容量指定为零也适用。
Java 8 添加十元素数组的创建被推迟到第一个元素被添加的优化。这专门解决了 ArrayList 个实例（使用默认容量创建）长时间甚至整个生命周期都为空的常见情况。此外，当第一个实际操作是 addAll 时，它可能会跳过第一个数组调整大小操作。这不会影响具有明确初始容量的列表，因为通常会仔细选择这些列表。
如
According to our performance analysis team, approximately 85% of ArrayList instances are created at default size so this optimization will be valid for an overwhelming majority of cases.
动机是精确优化这些场景，而不是触及指定的默认容量，这是在创建 ArrayList 时定义的。 （虽然 JDK 1.4 是第一个明确指定它的人）