ArrayList 的底层是数组队列，相当于动态数组。与 Java 中的数组相比，它的容量能动态增长。在添加大量元素前，我们可以使用 ensureCapacity() 方法来增加 ArrayList 实例的容量。这可以减少递增式再分配的数量。
ArrayList继承于 AbstractList ，实现了 List, RandomAccess, Cloneable, java.io.Serializable 这些接口。
public class ArrayListextends AbstractList implements List , RandomAccess, Cloneable, java.io.Serializable{ }
- RandomAccess 是一个标志接口，表明实现这个这个接口的 List 集合是支持快速随机访问的。在 ArrayList 中，我们即可以通过元素的索引快速获取元素对象，这就是快速随机访问。
- ArrayList 实现了 Cloneable 接口，即覆盖了函数clone()，能被克隆。
- ArrayList 实现了 java.io.Serializable接口，这意味着ArrayList支持序列化，能通过序列化去传输。
// 序列化 ID
private static final long serialVersionUID = 8683452581122892189L;
// 默认初始容量大小
private static final int DEFAULT_CAPACITY = 10;
// 空数组，用于空实例
private static final Object[] EMPTY_ELEMENTDATA = {};
// 用于默认大小空实例的共享空数组实例。
// 我们把它从 EMPTY_ELEMENTDATA 数组中区分出来，以知道在添加第一个元素时容量需要增加多少
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
// 保存数据的数组，所以说 ArrayList 的底层是数组，只不过能动态增长而已
transient Object[] elementData;
// 元素个数
private int size;
思考：transient Object[] elementData; 为啥要用 transient 关键字修饰？
答：我们知道用 transient 修饰的变量不会被序列化，这不就意味着序列化时，我们的数据丢失了吗？阅读其源码发现，ArrayList 提供了 writeObject() 和 readObject() 这两个方法，在进行序列化和反序列化时会调用这两个方法进行相关操作，不会造成数据丢失。
深入了解序列化writeObject、readObject、readResolve
// 进行序列化时会自动调用的方法
private void writeObject(java.io.ObjectOutputStream s)
throws java.io.IOException{
// Write out element count, and any hidden stuff
int expectedModCount = modCount;
s.defaultWriteObject();
// Write out size as capacity for behavioural compatibility with clone()
// 把元素个数写入到流中
s.writeInt(size);
// Write out all elements in the proper order.
for (int i=0; i 0) {
// be like clone(), allocate array based upon size not capacity
int capacity = calculateCapacity(elementData, size);
SharedSecrets.getJavaOISAccess().checkArray(s, Object[].class, capacity);
ensureCapacityInternal(size);
// a 和 elementData 指向的是同一块内存地址，修改 a 就相当于修改 elementData
Object[] a = elementData;
// Read in all elements in the proper order.
for (int i=0; i
2.2 构造函数分析
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_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(Collection c) {
Object[] a = c.toArray();
if ((size = a.length) != 0) {
// 判断是否与 ArrayList 的 class 对象一样
// 一样就直接赋值给 elementData 数组
if (c.getClass() == ArrayList.class) {
elementData = a;
} else {
elementData = Arrays.copyOf(a, size, Object[].class);
}
} else {
// replace with empty array.
elementData = EMPTY_ELEMENTDATA;
}
}
注意，调用空构造方法的时候我们发现，其实分配的是一个空数组，只有当真正添加元素的时候才会分配默认容量 10。
补充：JDK 1.6 new 无参构造的 ArrayList 对象时，直接创建了长度是 10 的 Object[] 数组 elementData 。
2.3 开始分析扩容机制
2.3.1 add 方法
public boolean add(E e) {
// 判断是否需要扩容方法，注意这里传的参数是 元素个数 + 1
// 1 代表的是新添加的元素
ensureCapacityInternal(size + 1); // Increments modCount!!
// 追加的数组的尾部
elementData[size++] = e;
return true;
}
2.3.2 ensureCapacityInternal 方法
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
private static int calculateCapacity(Object[] elementData, int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
当 add 进第一个元素时，minCapacity 为 1，DEFAULT_CAPACITY 为 10，10 > 1，所以返回 10
2.3.3 ensureExplicitCapacity 方法
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
// 如果原来的 elementData 数组长度 小于最小容量
// 则调用 grow() 方法进行扩容，反之不做任何操作
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
2.3.4 grow 方法
private void grow(int minCapacity) {
// overflow-conscious code
// 记录原来数组的长度
int oldCapacity = elementData.length;
// 新的容量就是原来数组长度的 1.5 倍，这里使用右移效率更高
int newCapacity = oldCapacity + (oldCapacity >> 1);
// 如果新的容量比最小容量小，就直接把最小容量赋值给新的容量
// 如果不是，就不用变化
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
// 如果超出临界值，就调用 hugeCapacity 方法
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);
}
// 临界值
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
2.3.5 hugeCapacity 方法
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.6 流程分析
分析一下这两行代码的流程：
List list = new ArrayList<>();
list.add("1");
1、第一行调用 ArrayList 的无参构造函数，直接赋值给 elementData 一个默认的空数组 {}，数组长度为 0。
2、第二行添加一个元素：
（1）进入 add 方法内，首先调用 ensureCapacityInternal 方法。
（2）进入 ensureCapacityInternal 方法内，调用 calculatCapacity 方法，然后再调用 ensureExplicitCapacity 方法。
（3）进入 calculatCapacity 方法内，这个方法主要是判断是否是空数组，如果是空数组，就比较默认容量 10 和 最小容量 的大小，取二者最大值；如果不是空数组，则直接返回最小容量，这里返回 10。
（4）进入 ensureExplicitCapacity 方法内，这个方法的主要作用是判断是否需要扩容，如果最小容量 - elementData 数组长度 > 0，说明最小容量大于数组长度，此时调用 grow方法进行扩容。很明显，这里的 最小容量为 10，数组长度为 0，需要调用 grow 方法进行扩容。
（5）进入 grow 方法内，这个方法就是实际上的扩容方法。新定义一个变量 oldCapacity 存储原来数组的长度，再定义一个变量 newCapacity = oldCapacity + (oldCapacity >> 1)，就是为原来数组长度的 1.5 倍，然后再判断 newCapacity - minCapacity 是否小于 0，小于 0 则说明 newCapacity 不够，就直接执行 newCapacity = minCapacity，然后再判断是否超过临界值，没超过就直接调用 elementData = Arrays.copy(elementData, newCapacity)；进行实际上的扩容！（注：临界值这里可以去看 hugeCapacity 方法）
（6）回到最开始的 add() 方法，执行 elementData[size++] = e; return true;
（7）执行完成。
3、其他方法源码解读
3.1 remove 方法
（1）根据索引删除元素
public E remove(int index) {
// 检查索引是否越界
rangeCheck(index);
// 记录 ArrayList 修改的次数
modCount++;
// 返回对应索引的元素
E oldValue = elementData(index);
// 计算索引位置
int numMoved = size - index - 1;
// 如果大于 0 说明索引在数组中间
if (numMoved > 0)
// 复制数组
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
// 数组元素个数 - 1，最后一个元素置为 null
elementData[--size] = null; // clear to let GC do its work
// 返回要删除索引的元素
return oldValue;
}
// 检查索引是否越界，如果越界则抛出异常
private void rangeCheck(int index) {
// 这里的界限是 size 的大小，不是数组的长度大小
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
// 异常信息
private String outOfBoundsMsg(int index) {
return "Index: "+index+", Size: "+size;
}
// 返回对应索引的元素
E elementData(int index) {
return (E) elementData[index];
}
（2）根据对象删除元素
public boolean remove(Object o) {
// 如果要删除的元素为 null，ArrayList 是允许元素为 null，而且可以重复
if (o == null) {
// 遍历数组
for (int index = 0; index < size; index++)
// 直接用 == 比较地址是否相等
if (elementData[index] == null) {
// 传递对应的索引进行删除操作
fastRemove(index);
return true;
}
// 如果不为 null，就需要使用对象的 equals() 方法进行比较
} else {
// 遍历数组
for (int index = 0; index < size; index++)
// 调用对象的 equals() 方法判断是否相等
if (o.equals(elementData[index])) {
// 传递对应的索引进行删除
fastRemove(index);
return true;
}
}
return false;
}
// 根据索引快速删除，同样是复制数组
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
}
3.2 System.arrayCopy 方法
public static native void arraycopy(Object src, int srcPos,
Object dest, int destPos,
int length);
3.3 Arrays.copyOf 方法
public static T[] copyOf(T[] original, int newLength) {
return (T[]) copyOf(original, newLength, original.getClass());
}
public static T[] copyOf(U[] original, int newLength, Class newType) {
@SuppressWarnings("unchecked")
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;
}
3.4 ensureCapacity 方法
这个方式也是一个扩容方法，我们可以自己调用，避免重复扩容。
public void ensureCapacity(int minCapacity) {
// 如果是空数组
int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
// any size if not default element table
? 0
// larger than default for default empty table. It's already
// supposed to be at default size.
: DEFAULT_CAPACITY;
if (minCapacity > minExpand) {
ensureExplicitCapacity(minCapacity);
}
}
