通过源码⼀步⼀步分析 ArrayList 扩容机制

ArrayList 是 Java 中常用的集合类，它底层实现是基于数组的。为了处理元素的动态增加，ArrayList 会在容量不足时进行扩容。以下是通过源码逐步分析 ArrayList 扩容机制的过程。

1. ArrayList 类的基本结构

ArrayList 继承自 AbstractList，实现了 List 接口。其底层数据结构是一个数组，初始时，ArrayList 会为其元素分配一个初始容量。ArrayList 还包含一个成员变量 elementData，它是一个数组，用来存储集合中的元素。

public class ArrayList<E> extends AbstractList<E> implements List<E> {private Object[] elementData;private int size;private static final int DEFAULT_CAPACITY = 10;  // 默认容量private static final Object[] EMPTY_ELEMENTDATA = {};  // 空数组public ArrayList() {this.elementData = EMPTY_ELEMENTDATA;  // 初始为空数组}public ArrayList(int initialCapacity) {if (initialCapacity > 0) {this.elementData = new Object[initialCapacity];  // 根据传入的初始容量创建数组} else if (initialCapacity == 0) {this.elementData = EMPTY_ELEMENTDATA;  // 如果容量为0，使用空数组} else {throw new IllegalArgumentException("Illegal Capacity: " + initialCapacity);}}// 省略其他构造函数和方法
}

2. 添加元素时的扩容逻辑

ArrayList 中的元素是通过 add(E e) 方法添加的。当元素的数量超过当前数组的容量时，ArrayList 会触发扩容。我们可以从 add 方法的源码分析其扩容的实现。

public boolean add(E e) {ensureCapacityInternal(size + 1);  // 确保容量足够elementData[size++] = e;  // 将元素添加到数组中，并更新sizereturn true;
}

3. ensureCapacityInternal 方法

ensureCapacityInternal 方法是扩容的关键。它首先检查当前数组容量是否足够，如果不足，就会进行扩容。源码如下：

private void ensureCapacityInternal(int minCapacity) {// 如果elementData为空（即初次初始化），则使用默认容量if (elementData == EMPTY_ELEMENTDATA) {minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);}// 如果当前容量不足以容纳更多元素，则进行扩容if (minCapacity - elementData.length > 0)grow(minCapacity);
}private void grow(int minCapacity) {// 获取当前数组的容量int oldCapacity = elementData.length;// 扩容时的默认增长策略为当前容量的1.5倍int newCapacity = oldCapacity + (oldCapacity >> 1); // oldCapacity + oldCapacity / 2// 如果扩容后容量不足，使用最小的扩容容量if (newCapacity - minCapacity < 0)newCapacity = minCapacity;// 如果新容量为0，意味着容量已超出限制，抛出异常if (newCapacity - MAX_ARRAY_SIZE > 0)newCapacity = hugeCapacity(minCapacity);// 扩容：创建一个新的数组并将旧数组元素复制过去elementData = Arrays.copyOf(elementData, newCapacity);
}private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;private static int hugeCapacity(int minCapacity) {// 如果容量超出最大值，抛出异常if (minCapacity < 0) // overflowthrow new OutOfMemoryError();return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;
}

4. 扩容的逻辑解析

• 初始容量处理：当 ArrayList 创建时，初始容量为 0 或者通过构造函数指定的容量。如果容量为 0，则 elementData 为空数组。
• 容量不够时扩容：
  • 当 elementData 容量不够时，ensureCapacityInternal 会调用 grow 方法进行扩容。
  • 扩容时，新数组的容量是旧数组容量的 1.5 倍。
  • 如果扩容后的容量仍然不足以容纳新元素，容量会直接增长到满足最小需求的大小。
  • 如果容量增长到达 Integer.MAX_VALUE 限制，会使用 hugeCapacity 方法，确保不会超过 Java 数组的最大长度。

5. 扩容过程的影响

• 性能影响：每次扩容时，ArrayList 需要创建一个新的数组并将旧数组的元素复制过去。这是一个 O(n) 的操作，其中 n 是当前数组的大小。
• 内存利用率：通过 1.5 倍扩容，ArrayList 保证了增长的合理性，避免了频繁的扩容带来的性能开销，但也可能导致一定程度的内存浪费，尤其是在扩容多次时。

总结

ArrayList 的扩容机制主要由以下几个步骤组成：

1. 容量检查：每次添加元素时，先检查当前数组是否有足够的容量。
2. 扩容计算：如果容量不足，则按照 1.5 倍的增长策略进行扩容。
3. 数组复制：扩容时，通过 Arrays.copyOf 将旧数组的数据复制到新数组中。
4. 容量上限：当容量超出最大限制时，抛出 OutOfMemoryError。

这个机制可以确保 ArrayList 在动态扩展时既高效又不会造成过多的内存浪费。