今天来看一下 ArrayList 原理。本文解析的 ArrayList 源代码基于 JDK 1.8 。
ArrayList是List接口的的实现，ArrayList底层是动态数组，其容量能自动增长。根据数组的特性， arraylist的查询效率较高，而增删效率较低。常用在查询较多的场景中。(ArrayList中可以存放null元素的)
下面看一下ArrayList的继承关系
通过图可以看到ArrayList继承自AbstractList，并且实现了List<E>, RandomAccess, Cloneable, Serializable接口，而AbstractList实现了Collection接口，则ArrayList具有Collection的所有方法，而且能够进行clone,序列化，下面开始开始对ArrayList的源码进行分析。
构造方法
ArrayList 有两个构造方法，一个是无参，另一个需传入初始容量值。大家平时最常用的是无参构造方法，相关代码如下：
private static final int DEFAULT_CAPACITY = 10;
private static final Object[] EMPTY_ELEMENTDATA = {};
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
transient Object[] elementData;
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
两个构造方法做的事情并不复杂，目的都是初始化底层数组 elementData。区别在于无参构造方法会将 elementData 初始化一个空数组，插入元素时，扩容将会按默认值重新初始化数组。而有参的构造方法则会将 elementData 初始化为参数值大小（>= 0）的数组。一般情况下，我们用默认的构造方法即可。倘若在可知道将会向 ArrayList 插入多少元素的情况下，应该使用有参构造方法。按需分配，避免浪费。
add()办法
// 确保数组的容量，保证可以添加该元素
ensureCapacityInternal(size + 1); // Increments modCount!!
// 将该元素放入数组中
elementData[size++] = e;
return true;
}
发现在 add() 方法中，代码很简短。可以看出之前的预操作都放入了 ensureCapacityInternal 方法中，这个方法会去确保该元素在数组中有位置可以放入。
那么我们来看看这个方法：
private void ensureCapacityInternal(int minCapacity) {
// 如果数组是空的，那么会初始化该数组
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
// DEFAULT_CAPACITY 为 10 ，所以调用无参默认 ArrayList 构造方法初始化的话，默认的数组容量为 10
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// 确保数组的容量，如果不够的话，调用 grow 方法扩容
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
扩容是在 grow 方法中完成的，所以我们接着跟进。
private void grow(int minCapacity) {
// 当前数组的容量
int oldCapacity = elementData.length;
// 新数组扩容为原来容量的 1.5 倍
int newCapacity = oldCapacity + (oldCapacity >> 1);
// 如果新数组扩容容量还是比最少需要的容量还要小的话，就设置扩充容量为最小需要的容量
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
//判断新数组容量是否已经超出最大数组范围，MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8
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);
}
扩容方法其实就是新创建一个数组，然后将旧数组的元素都复制到新数组里面。
当然，add 还有一个重载的方法 add(int index, E element) ，顺便我们也来看一下。
public void add(int index, E element) {
// 判断 index 有没有超出索引的范围
rangeCheckForAdd(index);
// 和之前的操作是一样的，都是保证数组的容量足够
ensureCapacityInternal(size + 1); // Increments modCount!!
// 将指定位置及其后面数据向后移动一位
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
// 将该元素添加到指定的数组位置
elementData[index] = element;
// ArrayList 的大小改变
size++;
}
remove()办法
ArrayList支持两种删除方式：
1、按照下标删除
2、按照元素删除，这会删除ArrayList中与指定要删除的元素匹配的第一个元素
对于ArrayList来说，这两种删除的方法差不多，都是调用的下面一段代码：
public E remove(int index) {
// 检查 index 有没有超出索引的范围
rangeCheck(index);
modCount++;
// 保存一下需要删除的数据
E oldValue = elementData(index);
// 让指定删除的位置后面的数据，向前移动一位
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
// 方便 gc 释放内存
elementData[--size] = null; // clear to let GC do its work
// 返回旧值
return oldValue;
}
同样，remove 还有一个重载的方法 remove(Object o) 。
if (o == null) {
// 如果有元素的值为 null 的话，移除该元素，fastRemove 的操作和上面的 remove(int index) 是类似的
for (int index = 0; index < size; index++)
if (elementData[index] == null) {
fastRemove(index);
return true;
}
} else {
// 如果有元素的值等于 o 的话，移除该元素
for (int index = 0; index < size; index++)
if (o.equals(elementData[index])) {
fastRemove(index);
return true;
}
}
return false;
}
clear()办法
clear 方法无非就是遍历数组，然后把所有的值都置为 null 。
modCount++;
// clear to let GC do its work
for (int i = 0; i < size; i++)
elementData[i] = null;
size = 0;
}
ArrayList和Vector的区别
ArrayList是线程非安全的，这很明显，因为ArrayList中所有的方法都不是同步的，在并发下一定会出现线程安全问题。那么我们想要使用ArrayList并且让它线程安全怎么办？一个方法是用Collections.synchronizedList方法把你的ArrayList变成一个线程安全的List，比如：
synchronizedList.add("aaa");
synchronizedList.add("bbb");
for (int i = 0; i < synchronizedList.size(); i++)
{
System.out.println(synchronizedList.get(i));
}
ArrayList的优缺点
从上面的几个过程总结一下ArrayList的优缺点。ArrayList的优点如下：
1、ArrayList底层以数组实现，是一种随机访问模式，再加上它实现了RandomAccess接口，因此查找也就是get的时候非常快
2、ArrayList在顺序添加一个元素的时候非常方便，只是往数组里面添加了一个元素而已
不过ArrayList的缺点也十分明显：
1、删除元素的时候，涉及到一次元素复制，如果要复制的元素很多，那么就会比较耗费性能
2、插入元素的时候，涉及到一次元素复制，如果要复制的元素很多，那么就会比较耗费性能
因此，ArrayList比较适合顺序添加、随机访问的场景。
