1.简介
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
ArrayList的底层基于数组来实现，故具备一些数组的基本特性，例如：
- 获取元素效率较高：可以直接通过索引查找
- 插入元素效率较低：节点后的数据都需要往后移动
关于数组的更多解释，你可以参考这篇文章：数组的底层原理
1.1 类图
在IDEA中按下ctrl + alt + u的组合键，我们可以查看到ArrayList的类图。
这里对UML图形做简单介绍：
实线三角箭头：继承（图中，蓝色为类的继承，绿色为接口的继承）
虚线三角箭头：实现
关于继承和实现此处不做过多的解释，现在我们描述下直接节点的几个含义：
-
RandomAccess
标志接口，表明实现这个接口的 List 集合是支持快速随机访问的，数组特性决定可以快速访问。
-
Cloneable
覆盖了函数
clone()，能被克隆。 -
Serializable
支持序列化，能通过序列化去传输。
1.2 属性
private static final long serialVersionUID = 8683452581122892189L;
/**
* 默认初始容量大小
*/
private static final int DEFAULT_CAPACITY = 10;
/**
* 空数组（用于空实例）。
*/
private static final Object[] EMPTY_ELEMENTDATA = {};
/**
* 空数组
*/
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
/**
* 保存ArrayList数据
*/
transient Object[] elementData; // non-private to simplify nested class access
/**
* 所包含的元素个数
*/
private int size;
2.基础知识
我们知道，List和Array的特性都是数据能有序存放，但与数组不同的是，List还可以动态扩容。
在ArrayList中，数据是通过内部的Object[]数组来存放的。
2.1 System.arraycopy()
public static native void arraycopy(Object 源数组, int 源数组复制的起始位置；, Object 目的数组, int 目的数组放置的起始位置, int 复制的长度);
这是一个native方法，存放于java.lang包下，看名字我们应该能猜到，它能实现数组的复制，例如：
public static void main(String[] args) {
int[] arrA = {0, 1, 2};
int[] arrB = {3, 4, 5, 6, 7, 8};
System.arraycopy(arrA, 1, arrB, 2, 2);
System.out.println(Arrays.toString(arrB));
}
将arrA数组1号位开始的2个元素，复制到arrB数组2号位。
程序输出：
[3, 4, 1, 2, 7, 8]
通过这个native方法，我们可以实现数组的扩容，比如现在我想把一个数组扩容到原来的两倍。
public static void main(String[] args) {
int[] arrA = {7, 8, 9};
int[] arrB = new int[arrA.length * 2];
System.arraycopy(arrA,0,arrB,0,arrA.length);
System.out.println(Arrays.toString(arrB));
}
程序输出：
[7, 8, 9, 0, 0, 0]
2.2 Arrays.copyOf()
以char为例，下面是源代码。
public static char[] copyOf(char[] original, int newLength) {
char[] copy = new char[newLength];
System.arraycopy(original, 0, copy, 0, Math.min(original.length, newLength));
return copy;
}
该方法其实就是调用了上面的native方法，返回了复制过后的数组。
其实实现模式跟我们自己写的一样，只不过它用的是复制的长度做了判断。
// 源数组和新数组中的较小值,即:可以扩容,也可以缩容.
Math.min(original.length, newLength)
下面是一个示例：
public static void main(String[] args) {
int[] arrC = {6, 8, 9};
// newLength为5
int[] charNew = Arrays.copyOf(arrC, 5);
System.out.println(Arrays.toString(charNew));
// newLength为2
charNew = Arrays.copyOf(arrC, 2);
System.out.println(Arrays.toString(charNew));
}
程序输出：
[6, 8, 9, 0, 0]
[6, 8]
3.构造方法
查看源码可以知道，我们在new ArrayList()的时候，是不会执行扩容操作的。
3.1 ArrayList()
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
3.2 ArrayList(int initialCapacity)
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);
}
}
3.3 ArrayList(Collection<? extends E> c)
public ArrayList(Collection<? extends E> c) {
Object[] a = c.toArray();
// 注意此处的size = a.length,更新了当前ArrayList对象的size值.
if ((size = a.length) != 0) {
if (c.getClass() == ArrayList.class) {
elementData = a;
} else {
elementData = Arrays.copyOf(a, size, Object[].class);
}
} else {
elementData = EMPTY_ELEMENTDATA;
}
}
3.4 总结
通过构造方法可以看到，我们在new ArrayList()时，是不会触发扩容操作的。
构造时，无非就是给内部的elementData这个对象数组（属性）赋值。不必困扰transient关键字，就是当前字段不参与序列化的标识。
transient Object[] elementData;
放张小图，红色部分代表数据值被修改（write），绿色值代表数据值被使用（read）。
如何配置可以参考我这篇文章：IDEA中高亮显示变量的使用位置和赋值位置
4.扩容条件
ArrayList的扩容操作是在add()时进行触发的，我们可以查看add方法的源码。
public boolean add(E e) {
ensureCapacityInternal(size + 1);
elementData[size++] = e;
return true;
}
在add开始前，会执行ensureCapacityInternal(size + 1)和elementData[size++] = e两个操作，然后返回true。
4.1 void ensureCapacityInternal(int minCapacity)
确保内部容量不小于minCapacity
ensureCapacityInternal方法又关联了ensureExplicitCapacity和calculateCapacity两个方法。
private static int calculateCapacity(Object[] elementData, int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
我们先对calculateCapacity方法做解释。
4.2 int calculateCapacity(Object[] elementData, int minCapacity)
计算所需容量
该方法用于计算容量，传入一个数组和int值。
private static int calculateCapacity(Object[] elementData, int minCapacity) {
// 若传入的elementData为默认的空数组
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
// 则返回默认容量DEFAULT_CAPACITY(10) 和 minCapacity 中的较大值.
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
// 否则返回 minCapacity
return minCapacity;
}
什么时候会是空数组DEFAULTCAPACITY_EMPTY_ELEMENTDATA呢？返回上面的构造方法处可以看到是在无参构造中使用到了。
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
- elementData是无参构造器初始化的，返回值是minCapacity或者默认容量10。
- elementData不是无参构造器初始化的，返回值是minCapacity。
4.3 void ensureExplicitCapacity(int minCapacity)
确保显示容量不小于minCapacity
private void ensureExplicitCapacity(int minCapacity) {
// 记录arrayList被处理的次数,暂时可以忽略.
modCount++;
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
从上面4.1处可以看到，这个方法中形参的值（int minCapacity）是由calculateCapacity()方法计算来的。
如果，所需要的容量大于当前对象数组的长度，就执行扩容操作。
4.4 总结
现在我们把3个方法串起来，在进行add()操作时，必然会触发首行的ensureCapacityInternal()方法，传递的参数值是size+1。
size是什么？size就是当前arrayList对象的元素个数，我们不是经常使用list.size()吗？在arrayList的源码中，它什么也没做，就是一个简单的get方法。
public int size() {
return size;
}
所以，在add()操作时，ensureCapacityInternal()方法传入了当前元素个数+1的值进去。
add()操作又是干嘛的？将元素添加到list的末尾。
我们要放元素到末尾，那么必须得先确保size+1这个节点是可用的，即用来存放数据的对象数组最小容量是size+1。
现在，我们需要根据这个最小容量minCapacity做后续操作，即ensureExplicitCapacity()方法。
if (minCapacity - elementData.length > 0)
grow(minCapacity);
如果当前对象数组的长度小于所需最小容量，则执行扩容操作。
5.扩容操作
扩容操作是通过grow(minCapacity)方法完成的。
private void grow(int minCapacity) {
// 旧容量
int oldCapacity = elementData.length;
// oldCapacity >> 1,位运算,8>>1=4,11>>1=5
// 新容量: 约为原始容量的1.5倍,10->15,15->22
int newCapacity = oldCapacity + (oldCapacity >> 1);
// 如果计算出的新容量比所需的最小minCapacity小,扩容到所需最小容量就行了.
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
// 如果计算出的新容量比MAX_ARRAY_SIZE还要大,执行hugeCapacity()
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// 实际扩容操作,将elementData对象数组扩容到newCapacity,见2.2节.
elementData = Arrays.copyOf(elementData, newCapacity);
}
private static int hugeCapacity(int minCapacity) {
// OOM
if (minCapacity < 0) throw new OutOfMemoryError();
// Integer.MAX_VALUE = 0x7fffffff = 214,748,3647.
return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;
}