ArrayList的底层其实就是一个数组，只不过这个数组的大小可以动态变化。在Java中使用数组，通常是用int[] array = new int[10];，数组array在定义之后大小就不会发生变化，而ArrayList类就是提供了一个可以动态调节大小的数组，并且添加了几种方便操作数组的方法。
1. 简单了解
1.1 为什么说ArrayList底层是数组？
因为ArrayList有一个属性是Object数组，添加进来的所有元素都存放在该数组中
// 代码全都基于jdk1.8
transient Object[] elementData;
1.2 为什么ArrayList的数组大小是动态的？
ArrayList每次添加元素时，都会判断是否超过当前数组的容量，如果超过了就会将当前数组的内容拷贝到一个更大的数组中去。例如，初始化一个容量为6的ArrayList，当添加第7个元素时，会创建一个容量9的数组，将之前的6个值拷贝过来，然后将第7个元素添加到新数组中。
为什么创建的数组容量是9？因为ArrayList每次扩容都是变为当前的1.5倍，源码中grow()方法有下面两句
int oldCapacity = elementData.length; // 当前数组的容量
int newCapacity = oldCapacity + (oldCapacity >> 1); // 新数组的容量
每次容量都会增加当前容量的一半，所以，ArrayList每次扩容是1.5倍。
1.3 几个简单的API
ArrayList继承List接口，所以也实现了相关方法
boolean add(E e); // 结尾添加元素
void add(int index, E element); // 指定位置添加元素
boolean contains(Object o); // 查看是否包含目标元素
E set(int index, E element); // 替换下标index处的元素，返回原来的值
有了这些方法可以更方便的对数组进行一些操作，ArrayList可以看做是对数组的一个封装，提供了各种方法便于去操作数组。
2. 深入了解
2.1 ArrayList 构造器
ArrayList另外提供了两个Object数组，用于应对不同的初始化情况。
private static final int DEFAULT_CAPACITY = 10; // 默认容量
private static final Object[] EMPTY_ELEMENTDATA = {}; // 空数组
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; // 默认容量的空数组
transient Object[] elementData; // 实际保存元素的数组
有个要注意的地方是，前两个数组已经完成初始化，elementData只是声明，意味着elementData需要指向其中一个或者指向一个新的数组。
2.1.1 无参构造器
public ArrayList() {
// elementData指向默认容量的空数组
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
2.1.2 初始化容量的构造器
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity]; // elementData指向新数组
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA; // elementData指向空数组
} else {
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
2.1.3 参数为集合的构造器
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
if ((size = elementData.length) != 0) {
// elementData类型应为Object数组，c.toArray()返回的可能不是Object数组，
// 若不是，需要重新指定为Object数组
if (elementData.getClass() != Object[].class)
// elementData指向了创建的一个数组
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
// 传入的集合元素个数为0，elementData指向空数组
this.elementData = EMPTY_ELEMENTDATA;
}
}
这里有两个需要注意的地方，
-
size和elementData.length
size指已经存入数组中元素的个数，elementData.length指的是数组的容量，比如初始化时定义了一个容量为10的数组，elementData.length为10，此时还未添加元素，所以size是0。前两个构造器方法没有操作size，为初始值0，而第三个构造器中size为集合c的元素个数。 -
DEFAULTCAPACITY_EMPTY_ELEMENTDATA和EMPTY_ELEMENTDATA
两个都是空数组，有什么区别？两个数组在扩容机制上不同，当添加第一个元素时，因为两个数组容量都为0，需要扩容，
EMPTY_ELEMENTDATA扩容按照扩容规则，每次扩充1.5倍，容量从0到1，2，3，4，6，9......，而DEFAULTCAPACITY_EMPTY_ELEMENTDATA，第一次扩容后容量直接变为10，相关代码如下，它是有一个默认容量的，之后再扩容就按照扩容机制来，比如第二次扩容新数组容量为15，详细的扩容机制在后面介绍。可能会疑问按照扩容规则容量0扩容后还是0，怎么变成1的？扩容还有一条规则，扩容后的容量要大于等于最小需求容量，当添加第一个元素时，0*1.5还是0，但最小需求容量是1，即容量至少为1，此时扩容的容量按照最小需求容量来。
private static int calculateCapacity(Object[] elementData, int minCapacity) { if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { return Math.max(DEFAULT_CAPACITY, minCapacity); } return minCapacity; }
下面用几张图讲解三种不同创建ArrayList的方式，给定容量的情况下，初始化时即创建了容量为6的数组，当添加的元素超过6个时才会扩容。
若是指定容量为0，初始化时指向EMPTY_ELEMENTDATA空数组，第一次添加元素时，最小需求容量为1，需要扩容，第二次添加元素时，最小需求容量为2，依旧需要扩容。
若是无参构造器，初始化时指向DEFAULTCAPACITY_EMPTY_ELEMENTDATA空数组，第一次添加元素时，直接扩容为默认容量10，知道元素个数超过10再继续扩容。
2.2 扩容机制
扩容机制主要从add方法说起
public boolean add(E e) {
ensureCapacityInternal(size + 1); // 判断是否需要扩容
elementData[size++] = e; // 结尾添加元素
return true;
}
每次执行add首先调用ensureCapacityInternal方法，判断添加之后元素的数目有没有超过数组容量，如果有则进行扩容。calculateCapacity用来计算最小需求容量，ensureExplicitCapacity判断是否需要扩容
private void ensureCapacityInternal(int minCapacity) {
// minCapacity:最小需求容量
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
private static int calculateCapacity(Object[] elementData, int minCapacity) {
// 如果是使用无参构造器初始化时，第一次使用add(E e)方法，传入的minCapacity为1，
// 小于DEFAULT_CAPACITY(10)，直接扩容到10;如果是addAll()方法，
// minCapacity可能超过10，这时候就按照minCapacity进行扩容
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
进入ensureExplicitCapacity判断最小需求容量是否大于当前数组容量，是则调用gorw()进行扩容
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// 如果最小需求容量大于当前数组容量，进行扩容
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
gorw()是扩容机制的核心，每次扩容都会在原数组长度的基础上增加一半，这里使用的是右移操作符，比除法效率更高，原数组长度为奇数的情况下，则会忽略计算得到的小数，所以 ArrayList 扩容后容量变为原来的 1.5 倍左右。
private void grow(int minCapacity) {
// 当前数组容量oldCapacity
int oldCapacity = elementData.length;
// 新数组容量newCapacity，在oldCapacity基础上增加oldCapacity/2，右移一位相当于除以2
int newCapacity = oldCapacity + (oldCapacity >> 1);
// 如果是addAll方法，最小需求容量可能会超过newCapacity，
// 这时候使用最小需求容量作为新数组的容;另一种情况就是初始化容量为0，
// 第一、二次扩容时，得到的newCapacity依旧是0和1，需要使用minCapacity
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
// 如果newCapacity超过了定义的最大数组容量MAX_ARRAY_SIZE，newCapacity则为
// Integer.MAX_VALUE(其实就比MAX_ARRAY_SIZE大8)。因为newCapacity为int型，如果比
// Integer.MAX_VALUE还大，此时newCapacity就是负数了，溢出，会抛出异常
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
// 创建一个容量为newCapacity的数组，并将elementData拷贝过去
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;
}
2.3 扩容的本质是数组的拷贝
因为一个数组的大小是无法改变的，所以扩容其实就是创建一个更大的数组然后将原来的复制过来，这个过程就是通过grow()方法中的Arrays.copyOf()实现的，
Arrays.copyOf()只有一句话，调用它的重载方法，为啥不直接用重载方法呢，我猜是怕你看不懂反射，而用一个重载函数去做一次封装，这样去调用的时候就不用关注反射可以直接看懂copyOf()的含义。还有一个区别是T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType)是个泛型方法，有T和U两个类，作用是创建一个T[]数组，并将U[]数组的内容拷贝到T[]中并返回T[]。而下面第一个方法的作用限定了T和U是同一种类型。ArrayList扩容拷贝数组都是Object[]。
完成了新数组的创建，接下来就是数组内容的拷贝，使用的是System.arraycopy()，该方法需要原数组和目标数组，同时需要指定两个数组的拷贝起点和长度，原数组和目标数组可以是同一个。
public static <T> T[] copyOf(T[] original, int newLength) {
return (T[]) copyOf(original, newLength, original.getClass());
}
public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
@SuppressWarnings("unchecked")
// 如果newType是Object[]，则直接创建一个Object数组，否则使用反射创建T[]
// newType.getComponentType()是获取数组中元素的Class对象，
// 然后通过newArray()返回一个新的数组
T[] copy = ((Object)newType == (Object)Object[].class)
? (T[]) new Object[newLength]
: (T[]) Array.newInstance(newType.getComponentType(), newLength);
System.arraycopy(original, 0, copy, 0,
Math.min(original.length, newLength));
return copy;
}
public static native void arraycopy(Object src, int srcPos,
Object dest, int destPos,
int length);
Array.newInstance简单用法如下
// 创建一个长度10的Integer数组
Integer[] array = (Integer[]) Array.newInstance(Integer.class, 10);
2.4 几个常用方法的源码
2.4.1 add()
public boolean add(E e) {
// 判断是否需要扩容;modCount指ArrayList对象结构变化的次数，
// 每次运行ensureCapacityInternal都会使modCount加一，
// 而每次添加元素也会执行一次ensureCapacityInternal，所以每次添加元素都会使modCount加一
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e; // 将元素添加到末尾
return true;
}
public void add(int index, E element) {
rangeCheckForAdd(index); // 判断index是否超出边界
ensureCapacityInternal(size + 1); // Increments modCount!!
// 数组拷贝，目标数组即是原数组
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}
2.4.2 get()
public E get(int index) {
rangeCheck(index); // 检查索引
return elementData(index); // 返回索引对应的元素
}
2.4.3 remove()
public E remove(int index) {
rangeCheck(index); // 检查索引
modCount++; // 每次remove元素也会导致modCount加一
E oldValue = elementData(index); // 得到需要返回的元素
int numMoved = size - index - 1; // 计算数组需要移动的长度
if (numMoved > 0) // 数组拷贝
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // 数组最后一个元素还在，但却永远不会访问到了，清楚
return oldValue;
}
public boolean remove(Object o) { // 移除第一个检索到的元素
if (o == null) { // 如果是null也可以remove
for (int index = 0; index < size; index++)
if (elementData[index] == null) {
fastRemove(index); // 调用fastRemove()
return true;
}
} else {
// null无法使用equals()方法，所以要区分o是否为null
for (int index = 0; index < size; index++)
if (o.equals(elementData[index])) {
fastRemove(index); // 调用fastRemove()
return true;
}
}
return false;
}
// 和remove相同，只不过不需要返回删除的元素
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
}
2.4.4 set()
public E set(int index, E element) {
rangeCheck(index); // 检查索引
E oldValue = elementData(index); // 得到需要返回的元素
elementData[index] = element; // 替换元素
return oldValue;
}
2.4.5 toArray()
public Object[] toArray() {
return Arrays.copyOf(elementData, size); // 创建一个新数组，拷贝，返回
}
public <T> T[] toArray(T[] a) {
// 这是一个泛型方法，将ArrayList的数组内容拷贝到a中
if (a.length < size)
// 如果a的长度比size小，直接创建一个新数组，拷贝，返回
return (T[]) Arrays.copyOf(elementData, size, a.getClass());
// 否则将elementData的内容拷贝到a中
System.arraycopy(elementData, 0, a, 0, size);
if (a.length > size)
// 如果a的长度大于size，拷贝后的下标size对应的元素赋值为null，
// 感觉是为了和a后面的元素区分
a[size] = null;
return a;
}
3. 总结
ArrayList 底层是一个容量可以动态变化的数组，扩容机制即是将容量扩充为原始容量的 1.5 倍。每次扩容都是数组的拷贝，比较耗时，应在定义时选取合适的容量，减少扩容次数。文章第一部分简单介绍ArrayList的底层原理和扩容机制，可以对ArrayList有个大概的了解，毕竟不是每个人都需要掌握源码的，第二部分则对ArrayList的源码进行详细的分析，掌握这些能够对ArrayList创建、添加/删除元素时究竟发生了什么有更细致的了解。
