ArrayList是Java中常用的一个集合类，是List接口的一个实现类，而List接口继承自Collection接口，所以ArrayList是Collection的一个实现类。
本篇主要讨论一下ArrayList底层代码的实现。
核心的成员变量
先来看看ArrayList中几个核心的成员变量。
//初始化数组的大小，ArrayList底层是基于数组实现的
private static final int DEFAULT_CAPACITY = 10;
//一个空数组对象，用于无参数的情况下初始化数组
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
//底层存放数据的数组
transient Object[] elementData;
//已存放的元素数量
private int size;
//定义数组的最大容量，实际数组的大小可以扩大到Integer.MAX_VALUE的大小，该字段应该是预留字段
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
默认无参的构造函数
public ArrayList() {
//这里首先初始化用于存放数据的数组，默认数组的大小为空
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
add方法实现
//这里添加一个元素，添加成功后将size+1，并返回true
public boolean add(E e) {
//传入size+1，表示数组的容量应该满足最小的容量
ensureCapacityInternal(size + 1);
//将当前添加的元素存放到数组中
elementData[size++] = e;
return true;
}
//该方法用来确保当前数组的大小是否满足最小要求，并对数组扩容
private void ensureCapacityInternal(int minCapacity) {
//calculateCapacity方法传入存放数据的数组与该数组要求满足的最小容量，并返回设置的容量大小
//ensureExplicitCapacity会判断当前数组的是否需要扩容
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
private static int calculateCapacity(Object[] elementData, int minCapacity) {
//当数组的第一次使用时，返回初始化容量DEFAULT_CAPACITY=10
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
//判断当前数组的是否需要扩容
private void ensureExplicitCapacity(int minCapacity) {
//该变量为AbstractList中的成员变量，在用iterator迭代器获取数据的数据使用
modCount++;
//此处判断当前数组的容量是否满足要求
if (minCapacity - elementData.length > 0)
//调用该方法对数组进行扩容
grow(minCapacity);
}
//实际进行数组扩容拷贝操作
private void grow(int minCapacity) {
//当前数组的容量大小
int oldCapacity = elementData.length;
//新数组的容量大小，oldCapacity >> 1实际为oldCapacity/2
//这里也就是将数组的容量扩大1.5倍
int newCapacity = oldCapacity + (oldCapacity >> 1);
//由于第一次调用该方法时，数组的容量大小为0，所以这里会将默认数组大小赋予newCapacity
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
//当新数组的容量大小大于MAX_ARRAY_SIZE时，将数组的大小设置为Integer.MAX_VALUE
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
//最后，将数组进行拷贝扩容
elementData = Arrays.copyOf(elementData, newCapacity);
}
//该方法返回数组的最大容量大小
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
具体步骤如下：
- 当第一次调用add方法添加元素时，会对elementData数组进行扩容，默认大小为DEFAULT_CAPACITY=10；
- 之后每一次调用add方法时，会对elementData数组的大小进行判断，判断当前容量是否满足最小要求；
- 如果不满足，则调用grow方法，对数组的大小扩容为原来大小的1.5倍；
- 当elementData数组的容量大小大于MAX_ARRAY_SIZE（Integer.MAX_VALUE - 8）时，将数组的容量大小设置为Integer.MAX_VALUE；
- 添加成功后，对size加1，并对数组进行赋值数据，然后返回true；
带参数的构造函数
//传入初始化数组大小的参数
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
//初始化elementData数组大小
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
在add方法中，我们了解到，在添加元素的过程中，涉及到对元素进行扩容的操作，如果需要在数组中频繁添加大量元素，将会对elementData数组进行多次拷贝扩容操作，很消耗性能，所以，我们可以先预估数组的大小，并调用带参数的构造函数，传入初始化数组的大小的参数，可以避免在add元素的拷贝扩容操作，提升性能。
get方法实现
//传入要获取数据的索引下标，返回对应位置的数据
public E get(int index) {
//检查该索引下标是否越界
rangeCheck(index);
return elementData(index);
}
//判断当前索引下标是否大于当前数组存放数据的大小，如果索引下标越界，则报IndexOutOfBoundsException异常
private void rangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
//返回数组中对应索引下标位置的数据
E elementData(int index) {
return (E) elementData[index];
}
get方法实现比较简单，步骤如下：
- 首先对传入索引下标进行检查，如果下标越界，则抛出IndexOutOfBoundsException异常；
- 如果该索引下标合法，则返回对应索引下标位置的数据；
remove(int index)方法实现
//传入要删除的索引下标，并返回该索引下标元素，也就是删除了的元素
public E remove(int index) {
//检查索引下标是否合法
rangeCheck(index);
modCount++;
//取出该下标位置的元素
E oldValue = elementData(index);
//数组中要向前移动的元素的数量，删除指定索引元素时，会将该索引后面的元素向前移
int numMoved = size - index - 1;
if (numMoved > 0)
//将指定索引下标之后的元素向前移动
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
//因为数组向前移动了，所以将数组中最后一个元素的值设置为null
elementData[--size] = null;
//返回删除了的元素
return oldValue;
}
具体步骤如下：
- 检查指定索引下标是否合法，如不合法，抛出IndexOutOfBoundsException异常；
- 获取指定索引下标的元素数据，用于删除后返回；
- 删除数据是基于数组前移操作的，numMoved 为要前移元素的数量，假如当前数组为[1,2,3,4]，那么数组的size为4，当要删除的index=1时，这里计算出来的numMoved=2，所以实际调用的是System.arraycopy([1,2,3,4], 2, [1,2,3,4], 1, 2)，也就是从索引下标为2的位置开始后两个元素向前移动到下标为1的位置，移动后的结果为[1,3,4,4]；
- 将数组元素的最后一个值设置为null；
- 返回删除了的元素；
remove(Object o)方法实现
//删除某个元素，删除成功，返回true，否则返回false
public boolean remove(Object o) {
//如果要删除的对象为null，则删除数组第一个为null的元素
if (o == null) {
//遍历数组，获取出要删除的元素的下标
for (int index = 0; index < size; index++)
//查找出第一个元素为null的下标
if (elementData[index] == null) {
//执行按照索引删除元素，实现方法与remove(int index)类似
fastRemove(index);
return true;
}
} else {
//遍历数组，获取出要删除的元素的下标
for (int index = 0; index < size; index++)
//查找出要删除的元素的下标
if (o.equals(elementData[index])) {
//执行按照索引删除元素，实现方法与remove(int index)类似
fastRemove(index);
return true;
}
}
return false;
}
//删除指定索引的元素，与remove(int index)方法逻辑类似
private void fastRemove(int index) {
modCount++;
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // clear to let GC do its work
}
具体步骤：
- 判断要删除的元素是否为null，如果为null，则先遍历获取数组中第一个为null的索引下标，然后根据该索引下标删除元素，也就是删除数组中第一个为null的元素；
- 如果要删除的元素不为空，则遍历获取第一个出现在数组中的索引下标，然后根据索引下标删除该元素，也就是删除第一个与元素匹配的数据；
- 删除成功，返回true，否则，返回false;
适用场景
通过源码的分析，我们知道，arrayList底层是基于数组实现的，每个存储的元素，都拥有一个元素的下标，所以，当我们需要通过下标获取数据的时候，适合使用ArrayList来存取数据；而当在添加与删除元素的时候，可能会涉及到数组的扩容与拷贝，所以arrayList不适添加和删除比较多的场景。
