在 Java 中，ArrayList 是一个动态数组的实现，底层依赖于数组来存储元素。关于 ArrayList 的初始容量和扩容机制，下面是详细的说明：

1. 初始容量

  • ArrayList 的默认初始容量是 10，也就是说，当你创建一个空的 ArrayList 时，底层会创建一个包含 10 个元素的数组（这些元素默认是 null，直到被填充）。
ArrayList<String> list = new ArrayList<>();

这里，list 会有一个初始容量为 10 的底层数组。

你还可以通过构造函数指定初始容量：

ArrayList<String> list = new ArrayList<>(20);  // 初始容量为 20

2. 扩容机制

当 ArrayList 的元素数量超过当前容量时，会发生扩容。具体的扩容策略如下：

  • 扩容条件：当 ArrayList 添加一个新元素时，如果当前底层数组已满，就会触发扩容。
  • 扩容策略：ArrayList 会将容量扩大为原来的 1.5 倍（即原容量的 1.5 倍）。具体来说，新的容量为 (oldCapacity * 3) / 2 + 1。
  • 例子：如果当前数组容量是 10，当再添加第 11 个元素时，容量会扩展为 (10 * 3) / 2 + 1 = 16。
  • 注意：每次扩容都会创建一个新的更大的数组，并将旧数组中的元素复制到新数组中。这个过程是一个 O(n) 的操作（时间复杂度），其中 n 是当前数组的大小。

3. 扩容过程

扩容过程是通过创建一个新的、更大的数组，并将旧数组中的元素复制到新数组来实现的。具体的过程如下：

  • 假设原始数组容量为 n。
  • 当 ArrayList 中的元素数量达到 n 时，再次添加元素时就会触发扩容。
  • 创建一个新的数组，大小为 (n * 3) / 2 + 1（也就是 1.5 倍大小）。
  • 将原数组中的所有元素复制到新的数组中。
  • 更新 ArrayList 引用指向新数组。

例如：

// 假设 ArrayList 初始容量为 10
ArrayList<String> list = new ArrayList<>(10);// 假设当前 ArrayList 已经有 10 个元素
// 添加第 11 个元素，触发扩容
list.add("new element");
// 新的底层数组容量将是 16

在这个过程中，由于创建了一个新的数组并复制了所有元素，所以这个扩容过程的时间复杂度是 O(n)，其中 n 是当前容量。

4. 总结

  • 初始容量：默认是 10，可以通过构造函数设置。
  • 扩容机制：当容量不足时，ArrayList 会将容量扩大为原来的 1.5 倍，新的容量是 (oldCapacity * 3) / 2 + 1。
  • 扩容过程：通过创建一个更大的数组，并将旧数组的元素复制到新数组中，扩容是一个 O(n) 的操作。