为什么使用不同的ArrayList构造函数会导致内部数组的增长率不同？

Question

我似乎偶然发现了一些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 = {};

---

创建ArrayList通孔时new ArrayList(0)- EMPTY_ELEMENTDATA将被使用。

创建ArrayList通孔时new 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实现，其中存储桶的数量几乎总是比您要求的要多。但之所以这样做是因为需要“两个”的存储桶，尽管这里不是这种情况。

所以问题是-有人可以向我解释这种差异吗？

Answer 1

即使在实现不同的旧版本中，您也可以准确地得到所需的内容，所指定的内容：

ArrayList()

构造一个初始容量为10的空列表。

ArrayList(int)

构造一个具有指定初始容量的空列表。

因此，ArrayList使用默认构造函数构造时ArrayList，初始容量为10，因此只要列表大小为10或更小，就不需要调整大小。

与此相反，在构造函数中int的参数将精确地使用某些特定能力，受到越来越多的政策，其被指定为

除了添加元素具有固定的摊销时间成本外，没有指定增长策略的详细信息。

即使您指定的初始容量为零，该规则也适用。

Java 8添加了以下优化：将十个元素数组的创建推迟到添加第一个元素之前。这专门用于解决ArrayList实例（使用默认容量创建）长时间或什至整个生存期都为空的常见情况。此外，当第一个实际操作addAll为时，它可能会跳过第一个数组调整大小操作。这不会影响具有明确初始容量的列表，因为通常会仔细选择这些列表。

如在此答案中所述：

根据我们的性能分析团队的说法，大约有85％的ArrayList实例是在默认大小下创建的，因此此优化将在绝大多数情况下有效。

这样做的动机是精确地优化这些方案，而不是触摸ArrayList创建时定义的指定默认容量。（尽管JDK 1.4是第一个明确指定它的）