Java ArrayList 的扩容机制

Java 中的 ArrayList 是一个动态数组实现的可变大小的列表。当向 ArrayList 中添加元素，而其当前容量不足以容纳新的元素时，ArrayList 会自动进行扩容操作以增加自身的容量。

扩容机制如下：

  1. 初始容量：

    • 创建一个新的 ArrayList 时，默认初始容量为 10（在某些版本或实现中可能不同）。

  2. 扩容触发条件：

    • 当 ArrayList 的元素数量等于当前容量时，再尝试添加新元素时就会触发扩容操作。

  3. 扩容策略：

    • 扩容的具体策略是将现有容量翻倍，即新的容量等于旧容量的两倍加一（newCapacity = oldCapacity + (oldCapacity >> 1)），这样可以保证随着元素数量的增长，扩容操作发生的次数相对较少，从而提高性能。

  4. 拷贝元素：

    • 在扩容后，需要将原有数组中的所有元素复制到新的、更大容量的数组中。
    • 使用系统级的数组复制方法如 System.arraycopy() 来完成这个过程，这比逐个元素移动效率更高。

  5. 空间浪费：

    • 扩容操作可能导致一定的空间浪费，尤其是在元素数量与实际所需容量差距较大的情况下。可以通过设置合适的初始容量或通过构造函数指定容量来避免不必要的空间浪费。

例如，在代码层面，当你调用 add(E e) 或 add(int index, E element) 等方法时，如果内部数组已满，则会先调用 ensureCapacityInternal() 方法检查并调整容量，然后执行实际的添加操作。

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);
}

以上是对 ArrayList 扩容机制的基本描述，具体细节可能因 Java 版本和具体实现略有差异。