1. ArrayList继承关系介绍
1.1 ArrayList继承关系图
1.2 ArrayList的父类及接口介绍
（1）Iterable：实现该接口后可使用迭代器和增强for循环
（2）Collection：集合体系结构的顶级接口
（3）List：有序(插入顺序)、可通过索引访问、允许存在重复元素、允许添加null元素
（4）AbstractCollection：Collection的骨架实现
（5）AbstractList：List的一个"骨架"实现
（6）RandomAccess：一种标记接口，实现了该接口，就表示该实现支持随机访问，进行某些操作时底层会判断是否实现该接口来选择相应的算法
（7）Cloneable：一种标记接口，若不实现该接口，用Object.clone会报错
（8）Serializable：一种标记接口，只要需要将对象转换为字节形式，如进行网络传输或持久化时，就需要实现该接口
2. 源码分析前的一些说明
2.1 数组的创建和拷贝
ArrayList底层数组的动态扩容是通过调用Arrays.copyOf来完成数组的创建和拷贝，拷贝工作实际是由System.arraycopy完成，Arrays.copyOf的重载方法很多，但功能类似，下面仅对其中一个进行说明：
public static int[] copyOf(int[] original, int newLength) {
// 新建一个长度为newLength的数组
int[] copy = new int[newLength];
// System.arraycopy是本都方法，其方法签名是：System.arraycopy(Object src, int srcPos, Object dest, int destPos, int length)
// 对应到这里，就是将original的内容拷贝到copy中，起始位置都是0，拷贝的长度为Math.min(original.length, newLength)
System.arraycopy(original, 0, copy, 0, Math.min(original.length, newLength));
return copy;
}
2.2 溢出问题
举个极端的例子，对x、y是两个类型为int的变量，当x为-2，y为Integer.MAX_VALUE时，x<y的结果为true，而x-y<0的结果为false，因为x-y发生了数据溢出，x-y溢出后的值为Integer.MAX_VALUE。ArrayList底层扩容时会用x-y的形式考虑溢出的情况，这里只要知道x<y与x-y<0不一样即可，不再细究。
2.3 modCount
在ArrayList中多处用到modCount，modCount是AbstractList中的字段，用于并发情况下检测各线程操作是否正确的一种机制。
3. ArrayList源码分析
3.1 ArrayList中的字段
// 序列化id
private static final long serialVersionUID = 8683452581122892189L;
// 默认初始容量
private static final int DEFAULT_CAPACITY = 10;
// 共享(因为static)的空Object数组
private static final Object[] EMPTY_ELEMENTDATA = {};
// 共享的空Object数组，用于空构造器中(即用在ArrayList()中)对elementData进行初始化
// 当添加第一个元素进行扩容时，会进行判断，若elementData就是这个空数组，
// 则初始容量为DEFAULT_CAPACITY，相比于EMPTY_ELEMENTDATA，可实现快速扩容
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
// ArrayList的底层Object数组
// 被transient修饰，意味着不会被序列化
// ArrayList自定义了writeObject/readObject，elementData会在这两个方法中被处理(后面会介绍)
transient Object[] elementData; // non-private to simplify nested class access
// 代表数组中元素的个数，elementData.length是数组的实际大小
// size+1就是下面扩容时的最小容量(minCapacity)
private int size;
3.2 三种构造器
// 无参构造器，用DEFAULTCAPACITY_EMPTY_ELEMENTDATA初始化elementData后，
// 第一次添加元素时，会将容量初始化为10
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
// 创建指定大小的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);
}
}
// 用c初始化elementData
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray(); // 将c转换为数组类型
if ((size = elementData.length) != 0) {
// 若elementData中的元素(即c中的元素类型)不是Object类型
if (elementData.getClass() != Object[].class)
// 则对数组进行拷贝，拷贝后的数组大小为size(即当前元素个数)，类型为Object[]
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
// 元素个数为0，则用EMPTY_ELEMENTDATA进行初始化
this.elementData = EMPTY_ELEMENTDATA;
}
}
3.3 增加元素
（1）add(E e)及扩容
// 将元素添加到末尾
public boolean add(E e) {
// 进行扩容
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
// ensureCapacityInternal在内部扩容时调用
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
// 该方法与ensureCapacity方法的作用类似，但是它是被private修饰的
private static int calculateCapacity(Object[] elementData, int minCapacity) {
// 当用无参构造器实例化且第一次调用时，elementData总是会被初始化为10
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code(考虑了溢出的情况)
if (minCapacity - elementData.length > 0) // 需要的最小容量是否超过当前elementData的容量
grow(minCapacity); // 超过则扩容
}
private void grow(int minCapacity) {
// overflow-conscious code (考虑了溢出的情况)
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1); // 每次扩容为原来的1.5倍
if (newCapacity - minCapacity < 0) // 扩容1.5倍后仍无法满足最小容量
newCapacity = minCapacity; // 那么就用该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();
// 我的机器到这种容量会报错：OutOfMemoryError: Java heap space
// 或者OutOfMemoryError: Requested array size exceeds VM limit
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
（2）外部扩容用ensureCapacity
//该方法被public修饰，如果将要添加很大数量的元素，可提前调用该函数以减少扩容次数
public void ensureCapacity(int minCapacity) {
int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) ? 0 : DEFAULT_CAPACITY;
if (minCapacity > minExpand) {
ensureExplicitCapacity(minCapacity);
}
}
（3）其他添加元素的方法
// 在指定索引处插入元素
public void add(int index, E element) {
rangeCheckForAdd(index); // 边界检查(注意这里index可以等于size)
// 进行扩容
ensureCapacityInternal(size + 1);
// 将目前index处和它后面的元素整体后移一个位置
System.arraycopy(elementData, index, elementData, index + 1, size - index);
elementData[index] = element; // 更新该索引处的值
size++; // 更新size
}
// 将c中所有元素按顺序添加到elementData末尾
public boolean addAll(Collection<? extends E> c) {
Object[] a = c.toArray();
int numNew = a.length;
// 进行扩容
ensureCapacityInternal(size + numNew);
System.arraycopy(a, 0, elementData, size, numNew);
size += numNew;
return numNew != 0; // 注意一下返回值
}
// 在指定索引处开始，按序添加c中的元素，与addAll(Collection<? extends E> c)类似
public boolean addAll(int index, Collection<? extends E> c) {
rangeCheckForAdd(index);
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(size + numNew);
int numMoved = size - index;
if (numMoved > 0)
System.arraycopy(elementData, index, elementData, index + numNew,
numMoved);
System.arraycopy(a, 0, elementData, index, numNew);
size += numNew;
return numNew != 0;
}
3.4 删除元素
（1）删除单个元素
// 删除指定索引处的元素
public E remove(int index) {
rangeCheck(index); // index不小于size则抛异常
modCount++;
E oldValue = elementData(index); // 获取elementData[index]
int numMoved = size - index - 1; // 计算移除该元素后，需要移动的元素个数(就是该元素后的所有元素的个数)
if (numMoved > 0) // 进行移动(注意一下源数组和目的数组拷贝的起始位置)
System.arraycopy(elementData, index+1, elementData, index, numMoved);
elementData[--size] = null; // 将最后一个元素置为null
return oldValue; // 返回被删除元素的值
}
// 删除指定元素
public boolean remove(Object o) {
if (o == null) { // ArrayList中允许添加为null的元素
// 遍历并删除第一个为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); // 该方法与remove(int index)类似，仅仅少了边界检查且没有返回值
return true;
}
}
// 未找到与o匹配的元素，返回false
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）删除多个元素
// 删除指定索引范围的元素
protected void removeRange(int fromIndex, int toIndex) {
modCount++;
int numMoved = size - toIndex; // 删除后需要移动的元素个数
// 直接拷贝，会覆盖指定范围内的元素(部分或全部)
System.arraycopy(elementData, toIndex, elementData, fromIndex, numMoved);
// clear to let GC do its work
int newSize = size - (toIndex-fromIndex);
// 将后面的元素设置为null
for (int i = newSize; i < size; i++) {
elementData[i] = null;
}
size = newSize;
}
// 移除当前链表所有不包含在c中的元素
public boolean removeAll(Collection<?> c) {
// c为null则抛异常
Objects.requireNonNull(c);
// 批量移除
return batchRemove(c, false);
}
// 保留当前链表所有包含在c中的元素(与removeAll互补)
public boolean retainAll(Collection<?> c) {
Objects.requireNonNull(c);
return batchRemove(c, true);
}
// complement为true表示保留包含在c中的，为false表示移除包含在c中
private boolean batchRemove(Collection<?> c, boolean complement) {
final Object[] elementData = this.elementData;
int r = 0, w = 0;
boolean modified = false;
try {
for (; r < size; r++)
// 依据complement为true/false，保留/移除包含在c中的元素
if (c.contains(elementData[r]) == complement)
elementData[w++] = elementData[r]; // 进行移动
} finally {
// Preserve behavioral compatibility(兼容性) with AbstractCollection,
// even if c.contains() throws.
if (r != size) { // 若 r != size 成立证明抛异常了
System.arraycopy(elementData, r,
elementData, w,
size - r);
w += size - r;
}
if (w != size) {
// 将索引为 w ~ size-1 的元素设置为null
for (int i = w; i < size; i++)
elementData[i] = null;
// 更新相关字段
modCount += size - w;
size = w;
modified = true;
}
}
return modified;
}
（3）清空元素
// 将elementData中所有元素设置为null
public void clear() {
modCount++;
// clear to let GC do its work
for (int i = 0; i < size; i++)
elementData[i] = null;
size = 0;
}
3.5 修改元素值
（1）修改单个元素的值
public E set(int index, E element) {
rangeCheck(index); // 边界检查
E oldValue = elementData(index); //取出旧值
elementData[index] = element; // 替换旧值
return oldValue; // 返回旧值
}
（2）替换所有元素的值
// 对所有值按照传入的operator进行处理并替换原值
public void replaceAll(UnaryOperator<E> operator) {
Objects.requireNonNull(operator);
final int expectedModCount = modCount;
final int size = this.size;
// 对elementData的所有元素进行替换
for (int i=0; modCount == expectedModCount && i < size; i++) {
elementData[i] = operator.apply((E) elementData[i]);
}
if (modCount != expectedModCount) { // 替换期间若当前链表被修改则抛异常
throw new ConcurrentModificationException();
}
modCount++;
}
3.6 查看元素值
public E get(int index) {
rangeCheck(index); // 边界检查
return elementData(index); // 返回元素值
}
// 获取指定元素
E elementData(int index) {
return (E) elementData[index];
}
3.7 序列化和反序列化
ArrayList中的elementData是被transient修饰的，表示不被序列化，因为该数组的后面可能存在很多为null的元素，因此ArrayList(其他集合也是如此)中对序列化和反序列化进行了自定义。要进行自定义，除了实现Serializable接口，其次就是要重写方法头为private void writeObject(java.io.ObjectOutputStream s)和private void readObject(java.io.ObjectInputStream s)的两个方法，在序列化/反序列化时，底层会判断是否存在writeObject/readObject，存在的话会通过反射调用这两个方法。下面对这两个方法进行介绍：
// 序列化时调用
private void writeObject(java.io.ObjectOutputStream s)
throws java.io.IOException{
int expectedModCount = modCount;
s.defaultWriteObject(); // 将当前类中non-static、non-transient字段写入流中
s.writeInt(size); // 将elementData的元素个数写入流中
// 仅写入elementData中的前size个元素，忽略后面为null的元素
for (int i=0; i<size; i++) {
s.writeObject(elementData[i]);
}
if (modCount != expectedModCount) { // 写入期间如果被修改则抛异常
throw new ConcurrentModificationException();
}
}
// 反序列化时调用
private void readObject(java.io.ObjectInputStream s)
throws java.io.IOException, ClassNotFoundException {
elementData = EMPTY_ELEMENTDATA;
// 从流中读取当前类中non-static、non-transient的字段
s.defaultReadObject();
s.readInt(); // 可忽略
// 进行扩容并读取所有元素
if (size > 0) {
// 进行扩容
int capacity = calculateCapacity(elementData, size);
SharedSecrets.getJavaOISAccess().checkArray(s, Object[].class, capacity);
ensureCapacityInternal(size);
Object[] a = elementData;
// 从流中按序读取所有元素
for (int i=0; i<size; i++) {
a[i] = s.readObject();
}
}
}
3.8 其他方法
（1）sort
// 底层会调用合适的算法，按照条件c对elementData进行排序
public void sort(Comparator<? super E> c) {
final int expectedModCount = modCount;
Arrays.sort((E[]) elementData, 0, size, c);
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
modCount++;
}
（2）trimToSize
// "修剪"elementData，使得elementData的容量与其中的元素个数
// 相等(也就是使得elementData.length与size相等)
public void trimToSize() {
modCount++;
if (size < elementData.length) {
elementData = (size == 0)
? EMPTY_ELEMENTDATA
: Arrays.copyOf(elementData, size);
}
（3）toArray
public <T> T[] toArray(T[] a) {
if (a.length < size)
// 创建大小为size，类型为a.getClass()的数组，再将该数组转化为T[]类型，
// 并拷贝elementData中的现有元素到该数组中
return (T[]) Arrays.copyOf(elementData, size, a.getClass());
// a.length >= size，直接拷贝
System.arraycopy(elementData, 0, a, 0, size);
if (a.length > size)
a[size] = null;
return a;
}
public Object[] toArray() {
return Arrays.copyOf(elementData, size);
}
（4）indexOf和lastIndexOf
// 找到第一个匹配的元素，并返回其索引，未找到则返回-1(与remove(Object o)类似)
public int indexOf(Object o) {
if (o == null) {
for (int i = 0; i < size; i++)
if (elementData[i]==null)
return i;
} else {
for (int i = 0; i < size; i++)
if (o.equals(elementData[i]))
return i;
}
return -1;
}
// 与indexOf类似，找到最后一个匹配的元素，并返回其索引，未找到则返回-1
public int lastIndexOf(Object o) {
if (o == null) {
for (int i = size-1; i >= 0; i--)
if (elementData[i]==null)
return i;
} else {
for (int i = size-1; i >= 0; i--)
if (o.equals(elementData[i]))
return i;
}
return -1;
}
3.7 内部类
Java中Iterator是用于对Collection(的实现)进行迭代的，它为ArrayList、LinkedList、HashSet等Collection的实现提供了以相同方式迭代、操作元素的机制。Iterator对Enumeration进行了优化和扩充，用于代替Enumeration。Itr、ListItr是ArrayList中的内部类，都用于对元素的迭代，不同点是Itr只能单向迭代，而ListItr可进行双向迭代，下面仅对Itr进行说明：
// ArrayList对AbstractList.Itr进行了优化
private class Itr implements Iterator<E> {
int cursor; // 下一个元素的索引
int lastRet = -1; // 最后返回的元素对应的索引，若该元素不存在了(如调用remove后)，则为-1
int expectedModCount = modCount;
public boolean hasNext() {
return cursor != size;
}
// 一次获取一个
@SuppressWarnings("unchecked")
public E next() {
checkForComodification();
int i = cursor;
if (i >= size)
throw new NoSuchElementException();
Object[] elementData = ArrayList.this.elementData;
if (i >= elementData.length)
throw new ConcurrentModificationException();
cursor = i + 1; // 更新cursor
return (E) elementData[lastRet = i]; // 更新lastRet
}
// 调用remove前需先调用next
public void remove() {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();
try {
ArrayList.this.remove(lastRet);
cursor = lastRet;
lastRet = -1; // 最后一个元素被删除，将lastRet设置为-1
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
// 调用Consumer.accept对每一个"留下"的元素进行处理
@Override
@SuppressWarnings("unchecked")
public void forEachRemaining(Consumer<? super E> consumer) {
Objects.requireNonNull(consumer);
final int size = ArrayList.this.size;
int i = cursor;
if (i >= size) {
return;
}
final Object[] elementData = ArrayList.this.elementData;
if (i >= elementData.length) {
throw new ConcurrentModificationException();
}
while (i != size && modCount == expectedModCount) {
consumer.accept((E) elementData[i++]);
}
// update once at end of iteration to reduce heap write traffic
cursor = i;
lastRet = i - 1;
checkForComodification();
}
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}
