为什么使用不同的ArrayList构造函数会导致内部数组的增长率不同？
我似乎在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");您添加了一个元素，保留的空间仅用于该元素，没有其他内容。
在内部，这是通过两个字段实现的：
/**
* 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。
来自我内心的直观部分-简单地尖叫“删除DEFAULTCAPACITY_EMPTY_ELEMENTDATA”，让所有的情况都由EMPTY_ELEMENTDATA处理；当然是代码注释：
我们将其与EMPTY_ELEMENTDATA区分开来，以便了解在添加第一个元素时要膨胀多少
确实有道理，但为什么一个会膨胀到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实现，其中存储桶的数量几乎总是比您所要求的要多；但这样做是因为需要“2的幂”存储桶，而不是这里的情况。
所以问题是--有没有人能给我解释一下这种区别？
回答 6
Stack Overflow用户
发布于 2019-06-18 19:23:00
即使在实现不同的旧版本中，您也可以准确地得到您要求的内容，分别指定的内容：
构造了一个初始容量为10的空列表。
会构造一个具有指定初始容量的空列表。
因此，使用默认构造函数构造ArrayList将得到一个初始容量为10的ArrayList，因此，只要列表大小为10或更小，就不需要任何调整大小的操作。
相反，带有int参数的构造函数将精确地使用指定的容量，但受growing policy的限制，该as指定为
除了添加元素具有恒定摊销时间成本这一事实之外，没有指定增长策略的详细信息。
即使您将初始容量指定为零，这也适用。
Java-8增加了优化，将十个元素数组的创建推迟到添加第一个元素。这是专门针对ArrayList实例(使用默认容量创建)长时间甚至整个生命周期都是空的这一常见情况。此外，当第一个实际操作是addAll时，它可能会跳过第一个调整数组大小的操作。这不会影响具有显式初始容量的列表，因为这些列表通常是仔细选择的。
如this answer中所述
根据我们的性能分析团队，大约85%的ArrayList实例是在默认大小下创建的，因此这种优化将适用于绝大多数情况。
其动机是精确地优化这些场景，而不是触及指定的默认容量，这是在创建ArrayList时定义的。(通过JDK 1.4
Stack Overflow用户
发布于 2019-06-18 19:05:25
如果您使用默认构造函数，则其想法是尝试平衡内存使用和重新分配。因此，使用一个较小的默认大小(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 (带有一些范围/溢出检查)，所以让我们来看一下：
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，它也会增长得越大。这背后的原因很简单:如果列表已经很大，则添加大量项目的概率更高，反之亦然。这也是为什么在第五个元素之后，您会看到增长增量为1，然后是2。
Stack Overflow用户
发布于 2019-06-18 18:59:17
对您的问题的简短回答是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);
}
}似乎这样做是为了在某种程度上“兼容”旧实现的行为：
如果你用默认的容量初始化了list，现在它实际上是用一个空数组初始化的，但是，一旦插入了第一个元素，它基本上会恢复到与旧实现相同的行为，即在添加第一个元素后，支持的数组具有DEFAULT_CAPACITY，从那时起，list的行为与以前相同。
另一方面，如果您显式指定了初始容量，则数组不会“跳转”到DEFAULT_CAPACITY，而是相对地从您指定的初始容量增长。
我认为这种“优化”的原因可能是当你知道你只能在列表中存储一个或两个(即少于DEFAULT_CAPACITY)元素，并且你相应地指定了初始容量；在这些情况下，例如对于一个单元素列表，你只得到一个单元素数组，而不是DEFAULT_CAPACITY-sized。
不要问我保存引用类型的九个数组元素的实际好处是什么。每个列表可能高达约9*64位= 72字节的RAM。是啊。;-)
https://stackoverflow.com/questions/56647032
复制相似问题
腾讯云开发者
