java - 为什么使用不同的 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（所有元素都保存在哪里）。因此，您添加了一个元素 - 您将获得 9 个未使用的额外插槽。Object[]10

另一方面，如果您这样做：

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 = {};

当你创建一个ArrayListvia 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实现，桶的数量几乎总是比你要求的多；但是这样做是因为需要“两个的力量”桶，但这里的情况并非如此。

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

标签： javaarraylistcollectionsjava-8java-12

解决方案

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

ArrayList()

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

ArrayList(int)

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

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

相反，带有int参数的构造函数将精确地使用指定的容量，受制于指定为的增长策略

除了添加一个元素具有恒定的摊销时间成本这一事实之外，没有指定增长策略的细节。

即使您指定初始容量为零，它也适用。

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

如本答案所述：

根据我们的性能分析团队的说法，大约 85% 的 ArrayList 实例是以默认大小创建的，因此这种优化对于绝大多数情况都是有效的。

其动机是精确优化这些场景，而不是触及指定的默认容量，这是在ArrayList创建时定义的。（虽然JDK 1.4是第一个明确指定它的）

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

问题描述

解决方案

推荐阅读