ArrayList 源码解析
今天就来说说我们开发中常用的ArrayList源码
ArrayList几个重要的成员变量
和String源码解析开篇一样，我们还是先来看看ArrayList类的基本结构。
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
// 数组第一个 add 时候的长度，默认是 10，；
private static final int DEFAULT_CAPACITY = 10;
//表示当前数组的长度；
private int size;
// 保存集合数据的数组
transient Object[] elementData; // non-private to simplify nested class access
// 这个集合修改结构的次数
protected transient int modCount = 0;
}这里来说说这几个成员变量具体代表什么意思。
DEFAULT_CAPACITY: 数组的初始大小
size: 当前数组的大小（实时），类型 int，没有使用 volatile 修饰，非线程安全的
elementData: 用来保存集合数据的数组，从这个成员变量我们就可以看出来ArrayList的本质就是一个数组。
modCount: 数组结构发生改变的次数。比如说：扩容
如果ArrayList的本质是一个数组，数组结果一旦被创建之后就不能被改变了，那么ArrayList是怎么实现动态扩容的
从上文的分析可以得到ArrayList的本质就是一个数组，初始为空数组，当第一次add 的时候会变成一个长度为10 的数组，那么我们可以得到下图的ArrayList结构图示。
ArrayList的类注释
要看一个类的源码，就必须的先看看这个类的类注释。由于ArrayList的类注释很长，且都是英文的，为了节省大家的时间，我将其翻译成英文并提取出重要信息如下。
- ArrayList继承自List接口，且可以存储
null值，可自动扩容； - size、isEmpty、get、set、iterator和listIterator几个方法的时间复杂度都是O(1)；
- ArrayList不是线程安全的，推荐使用线程安全类：Collections#synchronizedList；
- 增强 for 循环，或者使用迭代器迭代过程中，如果数组大小被改变，会快速失败，抛出异常。
ArrayList类注释大概的意思就是上述的几条，后续涉及的我们在后面详细讲解。
初始化 ArrayList
ArrayList 类有三个重载构造函数:
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
// 默认构造器， 直接初始化， 默认大小为空
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
// 使用已存在的集合初始化ArrayList
public ArrayList(Collection<? extends E> c) {
// elementData 是保存数组的容器，默认为 null
elementData = c.toArray();
// 给定的集合 c 有值
if ((size = elementData.length) != 0) {
// c.toArray might (incorrectly) not return Object[] (see 6260652)
// 如果给定的集合不是 Object 类型， 我们会转成 Object
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
// 给定集合无值，则默认空数组
this.elementData = EMPTY_ELEMENTDATA;
}
}
// 指定 ArrayList 初始长度
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);
}
}构造函数说明
- 默认构造函数初始化的时候，会指定 ArrayList 的长度为0， 也就是说初始时候的数组是空数组，而不是10， 10 是第一次 add 的时候数组的长度。
- 第 12 行的时候，有一行注释。这行注释表示这里有一个bug，大致的意思就是。当给定集合内的元素不是 Object 类型时，我们会转化成 Object 的类型。一般情况下都不会触发此 bug，只有在下列场景下才会触发：ArrayList 初始化之后（ArrayList 元素非 Object 类型），再次调用 toArray 方法，得到 Object 数组，并且往 Object 数组赋值时，才会触发此 bug，代码和原因如图：
15行的地方打印出了String[], 说明这个 arr的泛型是 String。
官方查看文档地址：https://bugs.java.com/bugdatabase/view_bug.do?bug_id=6260652，问题在 Java 9 中被解决。
ArrayList 的 add 方法和 扩容
新增有两步：
- 确保数组的长度是否足够，如果不够，则需要扩容至原先长度的1.5倍
- 新增数据到数组
这两步我们可以直接从下面源码中体现。
public boolean add(E e) {
// 确保数组长度足够, size 是数组的长度
ensureCapacityInternal(size + 1); // Increments modCount!!
// 数组新增数据
elementData[size++] = e;
return true;
}注重来看第一步，这一步主要是一个方法 ensureCapacityInternal(size)，我们现在来看看这个方法。
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}看到这里主要使用了两个方法calculateCapacity 和ensureExplicitCapacity。calculateCapacity方法是获当前数组的容量；ensureExplicitCapacity方法是确保数组的容量足够。
private static int calculateCapacity(Object[] elementData, int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}calculateCapacity方法比较简单，如果是空集合的时候，我们会将容量设定为DEFAULT_CAPACITY也就是10。构造就直接返回minCapacity, 也就是当前数组大小 size + 1。minCapacity 的意思是 当前数组的最小容量。
下面来看 ensureExplicitCapacity 这个方法，这个方法的作用是确保数组容量足够。
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// 如果期望的最小容量小于目前数组的长度，就需要扩容
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}由于是对数组的容量做修改，这里modCount会加1，modCount 的作用主要是记录数组被修改，在类的其他方法中也会有用处。
接下来的操作就是grow(minCapacity)方法，这个方法的作用就是扩容，我们接下来来看看 grow方法。
// 扩容数组，扩容至原先容量的 1.5 倍
private void grow(int minCapacity) {
// 原先的容量
int oldCapacity = elementData.length;
// 新容量
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
elementData = Arrays.copyOf(elementData, newCapacity);
}
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0)
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}˙这个方法还是很简单的，主要分为下面几步：
- 得到当前数组的容量
- 计算出新的容量，
oldCapacity + (oldCapacity >> 1)这句话的意思是扩容至当前容量的1.5倍。oldCapacity >> 1表示右移一位，也就是除以2的意思。 - 如果扩容后的容量 < 我们期望的最小的容量，那么扩容后的值就是期望的最小容量
- 如果扩容后的容量 > jvm 所能分配的数组的最大值，就使用 Integer 的最大值。
- 最后我们将原数组的值 copy 到新数组。
虽然代码很简单，但是这里有几点需要注意的。
- 扩容后的容量是原先容量的
1.5倍，也就是原先容量大小 + 原先容量大小的一半。 - 扩容后的数组数据其实是复制了原先数组数据，也就是说前后的数组并不是同一个数组。也可以说
Arrays.copyOf就是扩容的本质。 - ArrayList 允许 null 值
- ArrayList 最大容量是
Integer.MAX_VALUE - add 方法并不是线程安全的。
ArrayList 的 remove 方法
ArrayList 的删除方法实现有两个重载方法，一个根据索引删除（remove(index)），一个根据值删除（remove(Object)）。我们只讲其中一个方法的源码来分析，我们讲解根据值删除方法。
public boolean remove(Object o) {
if (o == null) {
for (int index = 0; index < size; index++)
if (elementData[index] == null) {
fastRemove(index);
return true;
}
} else {
for (int index = 0; index < size; index++)
if (o.equals(elementData[index])) {
fastRemove(index);
return true;
}
}
return false;
}这里的 remove 方法主要分为两块，一个是值为 null 的时候，和值不为 null 的时候。
o == null 的时候
- 遍历整个数组，找到第一个值为null 的下标
- 调用
fastRemove方法删除 下标值，然后返回true - 找不到就返回 false
o != null 的时候
- 遍历整个数组，找到满足
o.equals(elementData[index])的下标 - 调用
fastRemove方法删除 下标值，然后返回true - 找不到就返回 false
fastRemove方法
上面两种情况都调用了 fastRemove 方法，下面我就来看看这个方法.
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
}- 第一步呢，这里还是
modCount++， 说明结构发生了改变 - numMoved 表示删除 index 位置的元素后，需要从 index 后移动多少个元素到前面去。减 1 的原因，是因为 size 从 1 开始算起，index 从 0开始算起。
- 调用
System.arraycopy从 index +1 位置开始被拷贝，拷贝的起始位置是 index，长度是 numMoved - 最后一步，数组最后一个位置赋值 null，帮助 GC
以上的步骤可以总结为下面的动态图，
简单总结一下，ArrayList有三个构造函数，通过这三个构造函数，使用者可以灵活初始化一个数组容器。在使用默认构造器初始化的数组的时候，数组是一个空数组。只有在第一次add的时候，才会见数组容量变为10。add 方法的本质是调用了 Arrays.copyOf() 方法。不管是 add 还是 remove 每次改变数组结构之前，都有一个变量 modCount 记录改变的次数。ArrayList可以运行null值且最大长度为 Integer.MAX_VALUE。
迭代器
如果要自己实现迭代器，实现 java.util.Iterator 类就好了，ArrayList 也是这样做的，我们来看下迭代器的几个总要的参数：
int cursor;// 迭代过程中，下一个元素的位置，默认从 0 开始。
int lastRet = -1; // 新增场景：表示上一次迭代过程中，索引的位置；删除场景：为 -1。
int expectedModCount = modCount;// expectedModCount 表示迭代过程中，期望的版本号；modCount 表示数组实际的版本号。迭代器一般来说有三个方法：
- hasNext 还有没有值可以迭代
- next 如果有值可以迭代，迭代的值是多少
- remove 删除当前迭代的值
我们来分别看下三个方法的源码：
###hasNext
public boolean hasNext() {
return cursor != size;
}cursor 表示下一个元素的位置，size 表示实际大小，如果两者相等，说明已经没有元素可以迭代了，如果不等，说明还可以迭代
next
public E next() {
//迭代过程中，判断版本号有无被修改，有被修改，抛 ConcurrentModificationException 异常
checkForComodification();
//本次迭代过程中，元素的索引位置
int i = cursor;
if (i >= size)
throw new NoSuchElementException();
Object[] elementData = ArrayList.this.elementData;
if (i >= elementData.length)
hrow new ConcurrentModificationException();
// 下一次迭代时，元素的位置，为下一次迭代做准备
cursor = i + 1;
return (E) elementData[lastRet = i];
}
// 版本号比较
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}看到这里，我们更能理解 cursor的含义了，就是一个计数器，指向下一个元素的位置。可以通过JVM 的程序计数器来类比，当然了，这里的含义更简单。
remove
public void remove() {
// 如果上一次操作时，数组的位置已经小于 0 了，说明数组已经被删除完了
if (lastRet < 0)
throw new IllegalStateException();
//迭代过程中，判断版本号有无被修改，有被修改，抛 ConcurrentModificationException 异常
checkForComodification();
try {
ArrayList.this.remove(lastRet);
cursor = lastRet;
// -1 表示元素已经被删除，这里也防止重复删除
lastRet = -1;
// 删除元素时 modCount 的值已经发生变化，在此赋值给 expectedModCount
// 这样下次迭代时，两者的值是一致的了
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}删除元素成功，数组当前 modCount 就会发生变化，这里会把 expectedModCount 重新赋值，下次迭代时两者的值就会一致了。
写到最后
ArrayList 并不是线程安全的，如果想要使用线程安全的 ArrayList ，可以使用开篇提到的 Collections#synchronizedList。我们来看看他的 add源码：
public void add(int index, E element) {
synchronized (mutex) {list.add(index, element);}
}以上就是 ArrayList 的几个基础类和迭代器，由于篇幅问题，并没有深入说明 ArrayList 的使用。但我也相信大家已经能很熟练的使用 ArrayList 了。