详解ArrayList的扩容机制

下面是讲解ArrayList的扩容机制的完整攻略：

标准版答案

概述

ArrayList 是基于数组实现的，其内部有一个数组用于存放数据。它的扩容机制就是在插入数据时，判断数组已满，此时将数组扩容为原数组长度的1.5倍。

具体实现

ArrayList 的核心代码如下：

private Object[] elementData;
private int size;

public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // 判断数组是否需要扩容
    elementData[size++] = e;
    return true;
}

private void ensureCapacityInternal(int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    ensureExplicitCapacity(minCapacity);
}

private void ensureExplicitCapacity(int minCapacity) {
    modCount++;

    // 如果当前数组不足以容纳数据，则需要扩容
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);  // 新数组长度为原数组的1.5倍
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // 复制原数组
    elementData = Arrays.copyOf(elementData, newCapacity);
}

上面的代码中，add() 方法是向 ArrayList 中插入元素的方法，它先通过 ensureCapacityInternal() 方法来判断数组是否需要扩容，如果需要则调用 grow() 方法来进行扩容。

在 grow() 方法中，先根据原数组长度计算出新数组长度 newCapacity，然后将原数组中的数据复制到新数组中，最后将新数组赋给 elementData 属性。

示例说明

示例一：添加三个元素

假设 ArrayList 的初始容量为 5，首先添加三个元素：

ArrayList<Integer> list = new ArrayList<>(5); // 指定初始容量为 5
list.add(1);
list.add(2);
list.add(3);

此时，ArrayList 的 elementData 数组长度已经为 5，其中存放了三个元素。

当再次添加元素时（如添加数字 4），由于数组已满，需要进行扩容操作：

list.add(4);

此时，在执行 grow() 方法时，oldCapacity = 5，newCapacity = 7，elementData 数组被复制到了一个长度为 7 的新数组中。

示例二：手动设置容量大小并添加元素

假设想要手动指定 ArrayList 的容量大小，然后向其中添加元素。可以通过手动设置容量大小来触发扩容操作。

ArrayList<Integer> list = new ArrayList<>(5); // 指定初始容量为 5
list.ensureCapacity(10); // 手动将容量设置为 10
list.add(1);
list.add(2);
list.add(3);
list.add(4);
list.add(5);
list.add(6); // 此时 elementData 数组长度已满，需要进行扩容操作

在这个示例中，手动设置了 ArrayList 的容量大小为 10。向其中添加元素时，前 5 个元素不会触发扩容操作。当添加第 6 个元素时（数字 6），由于数组已满，需要进行扩容操作。

进阶版答案

概述

ArrayList 是一种基于数组实现的动态数组，如果内部数组大小不够，它会通过创建一个新数组来增加容量。该新数组是旧数组大小的1.5倍。在插入大量数据时，大量的数组复制操作可能会拖慢 ArrayList 的速度。当面对大量数据集合时，如果可以提前预测容量大小，那么在之后的数据插入中就可以减少扩容的机会，也降低了数组扩容操作的影响。

具体实现

ArrayList 内部数组的大小是其最基本的属性之一，通过调用以下构造函数可以在创建 ArrayList 时制定容量大小：

ArrayList(int initialCapacity);

在运行期间，还可以调用以下 ensureCapacity() 方法来增加 ArrayList 的容量大小：

public void ensureCapacity(int minCapacity);

如果你能够提前预测需要存储的数据量，我们可以使用该方法来避免大量数据复制操作，这样我们就可以减少在之后的插入操作中创建新数组的机会。

ArrayList<Integer> list = new ArrayList<>(); // 默认容量大小为 10
list.ensureCapacity(20); // 预先调整数组大小为 20
for (int i = 0; i < 20; ++i) {
    list.add(i);
}

在上面的代码中，我们调用 ensureCapacity() 方法预先调整 ArrayList 的大小为 20，然后我们向其中插入了 20 个整数。因为我们预先调整了大小，所以不会触发数组扩容操作。

示例说明

示例一：使用默认构造器创建 ArrayList

ArrayList<Integer> list = new ArrayList<>();
for (int i = 0; i < 20; ++i) {
    list.add(i);
}

在这个示例中，使用默认构造器创建 ArrayList，它的容量大小默认为 10。向其中插入 20 个整数后，当添加第 11 个元素时（数字 10），由于数组已满，需要进行扩容操作。接下来数组大小被扩大到 15，元素添加到了数组中。

示例二：利用 ensureCapacity() 方法提前设置容量大小

ArrayList<Integer> list = new ArrayList<>();
list.ensureCapacity(20);
for (int i = 0; i < 20; ++i) {
    list.add(i);
}

在这个示例中，我们调用 ensureCapacity() 方法提前设置容量大小为 20，然后再向其中插入 20 个整数。先预设容量大小，使得数组不会在插满 10 个元素时就进行扩容，再插入元素时避免了扩容操作，提升了程序的效率。