一文了解 ArrayList 的扩容机制

了解 ArrayList

在 Java 中常用集合类之间的关系如下图所示：

从图中可以看出 ArrayList 是实现了 List 接口，并是一个可扩容数组（动态数组），它的内部是基于数组实现的。它的源码定义如下：

public class ArrayList<E> extends AbstractList<E>implements List<E>, RandomAccess, Cloneable, java.io.Serializable{
}

• ArrayList 可以实现所有可选择的列表操作，允许所有的元素，包括空值。ArrayList 还提供了内部存储 List 的方法，它能够完全替代Vector，只有一点例外，ArrayList 不是线程安全的容器。

• ArrayList 有一个容量的概念，这个数组的容量（size）就是 List 用来存储元素的容量。

• ArrayList 不是线程安全的容器，如果多个线程中至少有两个线程修改了 ArrayList 的结构的话就会导致线程安全问题，作为替代条件可以使用线程安全的 List，应使用 Collections.synchronizedList

  List list = Collections.synchronizedList(new ArrayList<>());
  

• ArrayList 具有 fail-fast 快速失败机制，能够对 ArrayList 作出失败检测。当在迭代集合的过程中该集合在结构上发生改变的时候，就有可能会发生 fail-fast，即抛出ConcurrentModificationException异常。

通过源码分析 ArrayList 的扩容机制

当使用空参构造器进行创建 ArrayList 的时候，实际上给 elementData 初始化赋值的是一个空数组 {}：

//数组列表的大小（包含的元素数）,初始化为 0
private int size;
//存储数组列表元素的数组缓冲区。
transient Object[] elementData;
//默认初始化容量为10
private static final int DEFAULT_CAPACITY = 10;
//默认空数组
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
//使用空参构造器创建 ArrayList 时，实际上初始化赋值的是一个空数组
public ArrayList() {this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

当首次调用 add(E e) 方法进行添加第一个元素时，会首先调用 ensureCapacityInternal 方法，传入参数 1：

//将指定的元素追加到此列表的末尾
public boolean add(E e) {ensureCapacityInternal(size + 1);  // Increments modCount!!elementData[size++] = e;return true;
}

在 ensureCapacityInternal 方法中，会调用 calculateCapacity 方法，传入参数为 elementData,1：

private void ensureCapacityInternal(int minCapacity) {ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

在 calculateCapacity 方法中，判断 elementData 是否为空数组，由于是初始化赋值的是一个空数组 {}，所以符合 if 条件，返回 (DEFAULT_CAPACITY, minCapacity)【10,1】 中大的那个，此时返回 10 ：

private static int calculateCapacity(Object[] elementData, int minCapacity) {if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {return Math.max(DEFAULT_CAPACITY, minCapacity);}return minCapacity;
}

接着返回到 ensureCapacityInternal 方法中，继续调用 ensureExplicitCapacity 方法验证是否需要扩容，传入参数 10 ，此时 minCapacity=10,elementData.length=0 ，相减小于0，执行 grow 方法扩容，传入参数 10，当添加第2-10个元素时，不会执行 grow 方法，一直到数组已经满元素时才执行 grow 方法扩容：

private void ensureExplicitCapacity(int minCapacity) {modCount++;// overflow-conscious codeif (minCapacity - elementData.length > 0)grow(minCapacity);
}

在 grow 方法中，此时 minCapacity=10,oldCapacity=0,newCapacity=0 ，符合 newCapacity - minCapacity < 0 条件，执行 newCapacity = minCapacity; 不满足 newCapacity - MAX_ARRAY_SIZE > 0 ，执行 Arrays.copyOf() 方法将 elementData 指向的数组中的元素复制到新的数组中，新的数组长度为 10，并让 elementData 指向新的数组，int newCapacity = oldCapacity + (oldCapacity >> 1) 完成1.5倍扩容。

private void grow(int minCapacity) {// overflow-conscious codeint 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);
}