一、前言
ArrayList是Java集合框架中List接口的一个实现类，底层用数组实现，相当于动态数组。是一种随机访问模式，实现RandomAccess接口，因此查找十分的块。ArrayList是线程不安全的，Vector是线程安全的，但是Vector比较古老，一般不建议使用。
ArrayList特点：
1、 基于数组实现的List类。
2、 动态的调整容量。
3、 有序的（输入输出顺序一致）。
4、 元素可以为null。
5、 不同步，非线程安全。
6、 增删慢，查询快。后面源码有提到，增删的时候实际上多了元素的复制操作，如果复制的元素比较多，则会耗性能。
7、 占用空间小。
二、源码阅读部分
1.声明
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
//其中后三个接口都是空接口，只是用来表明ArrayList支持随机访问模式，支持克隆和支持序列化的
//RandomAccess接口：如果一个数据集合实现了该接口，表明支持RandomAccess。
//按位置读取元素的平均时间复杂度为O1。
//实现了该接口的集合可以用for循环遍历，否则建议使用Iterator或者foreach遍历
2.用到的一些变量
private static final long serialVersionUID = 8683452581122892189L; //序列号
private static final int DEFAULT_CAPACITY = 10; //DEFAULT_CAPACITY：数组的初始大小为10
private static final Object[] EMPTY_ELEMENTDATA = {}; //空对象数组
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; //缺省空对象数组
transient Object[] elementData； //底层的数据结构：数组
private int size; //数组元素个数
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; //最大数组容量
前面有说过，ArrayList是支持序列化的，可是elementData又拿不序列化关键字transient修饰，这不是自相矛盾吗？ 答：其实不是，ArrayList底层重写了writeObject和readObject方法，ArrayList在序列化的时候会调用writeObject，直接将size和element写入ObjectOutputStream。反序列化的时候调用readObject，从ObjectOutputStream获取size和element，再恢复到elementData。这么做的原因是elementData是一个缓存数组，通常会预留一些容量，等容量不足再扩容，那么有些空间就没有元素，采用重写后的方法进行序列化可以保证只序列化实际存储的元素而不是整个数组，这样就节省了时间和空间。
3.构造方法
无参构造方法：
public ArrayList() {
//默认构造方法，初始化空数组，只有插入一条数据才会扩展到默认的10，实际上默认为空
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<? extends E> c) {
//将集合转换成数组，不然插不进去
elementData = c.toArray();
if ((size = elementData.length) != 0) {
//有种情况是c.toArray()不返回object，不过应该比较少
if (elementData.getClass() != Object[].class)
//使用Arrays.copyOf 将它拷贝成一个Object类型的数组
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
//如果这个集合转成数组长度为0，就创建空数组
this.elementData = EMPTY_ELEMENTDATA;
}
}
小结：如果只是以无参形式创建ArrayList，初始化一个空数组，容量就是0，当对数组进行添加元素时才分配容量，容量扩为10。有种说法是创建的时候指定容量效率会好一点，这样就不用ArrayList自己扩容了。
2.remove相关
参数是对象，返回值为boolean类型：
public boolean remove(Object o) {
//将原本ArrayList里的值赋给es，进行操作
final Object[] es = elementData;
final int size = this.size;
int i = 0;
found: {
if (o == null) {
//传入对象为空的话，就在该ArrayList里面找有没有空对象
//如果有的话就退出此代码块，没有就返回false
for (; i < size; i++)
if (es[i] == null)
break found;
} else {
//传入对象不为空，就在该ArrayList里面找该对象
//有的话就退出此代码块，没有就返回false
for (; i < size; i++)
if (o.equals(es[i]))
break found;
}
//找不到直接返回false
return false;
}
//调用快速删除方法删掉es[i]，也就是参数中的对象
fastRemove(es, i);
return true;
}
参数是int类型的角标，返回值为要删除的索引对应的值：
public E remove(int index) {
//首先判断index有没有越位
Objects.checkIndex(index, size);
final Object[] es = elementData;
//这个注解就是，如果前面没有出错的话，就执行。将原要删除的值赋给oldValue作为返回值
@SuppressWarnings("unchecked") E oldValue = (E) es[index];
//调用快速删除方法删掉index
fastRemove(es, index);
return oldValue;
}
前面说到的fastRemove方法：
private void fastRemove(Object[] es, int i) {
modCount++;
final int newSize;
//判断，因为只删除一个数，那么newSize理应等于size - 1并且要大于i，否则就抛出java.lang.IndexOutOfBoundsException异常
if ((newSize = size - 1) > i)
//这行代码的意思是，将从第es[i + 1]开始拷贝，覆盖掉es[i]这个值
//设ArrayList为：1,2,3,4,5,6 ，i为2。
//那么我们执行System.arraycopy(es, i + 1, es, i, newSize - i); 后就是1,2,4,5,6,6
System.arraycopy(es, i + 1, es, i, newSize - i);
//将最后一位设为元素null，因为是自己拷贝自己，数量是自己减一，所以最后一位是多出来的
es[size = newSize] = null;
}
clear方法：
public void clear() {
modCount++;
final Object[] es = elementData;
//先将0赋给size，让他的容量变为0，然后挨个将ArrayList中的值赋为null
for (int to = size, i = size = 0; i < to; i++)
es[i] = null;
}
小结：删除的时候会把指定下标到list的末尾的元素挨个向前移动一位，并且会将最后一个元素设置为null来方便GC。
3.add相关
allAll 顾名思义添加全部，即将一个任意类型集合全部添加到目标ArrayList中：
public boolean addAll(Collection<? extends E> c) {
Object[] a = c.toArray();
modCount++;
int numNew = a.length;
if (numNew == 0)
return false;
Object[] elementData;
final int s;
//如果要添加的集合长度大于原总长度（实际元素+剩余区域）减去原容量
//也就是添加的长度大于剩余区域了，开始扩容
if (numNew > (elementData = this.elementData).length - (s = size))
//扩容，参数为原长度+集合长度
elementData = grow(s + numNew);
//拷贝是将a全部拷贝到原数组中s的后面
System.arraycopy(a, 0, elementData, s, numNew);
//新的size 等于两个size之和
size = s + numNew;
return true;
}
双参addAll，在指定位置添加一个集合：
public boolean addAll(int index, Collection<? extends E> c) {
rangeCheckForAdd(index);
//将集合c给一object，方便操作
Object[] a = c.toArray();
modCount++;
int numNew = a.length;
//如果这个要插入的集合长度为0，直接返回false
if (numNew == 0)
return false;
Object[] elementData;
final int s;
//如果原ArrayList的长度加上新添加集合的长度大于缓冲区的话，就得扩容
if (numNew > (elementData = this.elementData).length - (s = size))
elementData = grow(s + numNew);
//numMoved就是原集合要移动的元素个数，两种情况：
//一种是index就是最后一位，这样一个元素也不移动，还有就是其他，原集合需要移动元素
int numMoved = s - index;
if (numMoved > 0)
//需要给插入集合腾位置，设被插入集合123456，插入集合789，index=3，numNew=3
//则numMoved=size-index=3，这行代码执行结果：123456456
System.arraycopy(elementData, index,
elementData, index + numNew,
numMoved);
//这行代码执行结果123789456
System.arraycopy(a, 0, elementData, index, numNew);
//新的size就是被插入size加上插入size
size = s + numNew;
return true;
}
三参数add 元素，原ArrayList缓冲区，add位置（还是插入集合的长度）。list本身是没有这个方法的，这个方法是一个辅助方法：
private void add(E e, Object[] elementData, int s) {
//判断add位置是否需要扩容
if (s == elementData.length)
elementData = grow();
elementData[s] = e;
size = s + 1;
}
单参add，意思是添加一个元素到该list末尾：
public boolean add(E e) {
modCount++;
//调用上面的，将e直接插入到ArrayList的最后面
add(e, elementData, size);
return true;
}
双参add，在指定位置添加一个元素：
public void add(int index, E element) {
//检查add位置是否合理
rangeCheckForAdd(index);
modCount++;
final int s;
Object[] elementData;
//当size=缓冲区的长度时，直接扩容
if ((s = size) == (elementData = this.elementData).length)
elementData = grow();
//数组copy方法，例如 123456，index=3，执行以下就是1234456，然后把第一个4换成element
System.arraycopy(elementData, index,
elementData, index + 1,
s - index);
elementData[index] = element;
size = s + 1;
}
检查add位置是否合法：
//最小0（插在第一个位置）最大是长度（直接插在最后面）
private void rangeCheckForAdd(int index) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
4.调整数组容量
//进行扩容操作
private Object[] grow(int minCapacity) {
return elementData = Arrays.copyOf(elementData,
newCapacity(minCapacity));
}
private Object[] grow() {
//直接将参数作为元素个数加一
return grow(size + 1);
}
private int newCapacity(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
//扩容，新容量为原来oldCapacity的1.5倍
int newCapacity = oldCapacity + (oldCapacity >> 1);
//校验新容量与之前容量的关系。
//下面代码可以看出，如果newCapacity小于minCapacity，则就返回minCapacity或者默认容量（10）
if (newCapacity - minCapacity <= 0) {
//这也就是说如果原ArrayList为空，就默认容量（10）和参数，谁大返回谁
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
return Math.max(DEFAULT_CAPACITY, minCapacity);
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
//以上两者都不是，直接返回参数就行，因为扩容了还不如参数呢
return minCapacity;
}
//对扩容后的长度与最大数组长度进行比较，如果比他小那就使用，比他大则固定为最大数组长度
//一个小细节就是源码中判断大小基本上都是一个减一个的形式，是为了防止溢出
return (newCapacity - MAX_ARRAY_SIZE <= 0)
? newCapacity
: hugeCapacity(minCapacity);
}
//上面的hugeCapacity方法，赋最大值
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
//如果当前参数大于MAX_ARRAY_SIZE，就直接以Integer.MAX_VALUE返回，否则返回MAX_ARRAY_SIZE
//其中Integer.MAX_VALUE = 2147483647 MAX_ARRAY_SIZE = 2147483639，
//一旦大于MAX_ARRAY_SIZE就把值赋为第一个，相当于两层保护
return (minCapacity > MAX_ARRAY_SIZE)
? Integer.MAX_VALUE
: MAX_ARRAY_SIZE;
}
小结扩容机制：首先创建一个空数组elementData，第一次插入数据的时候默认扩充至10，如果不够的话，就扩充为10的1.5倍，如果还不够，就使用需要的长度（即传进来的参数）作为elementData的长度。扩容的实质就是Arrays.copyOf方法。
5.插入大量数据：
在向ArrayList中插入大量数据的时候，有两种可行方案：
1、 直接在一开始就指定容量，使用ArrayList(int initialCapacity)这个有参构造，这样解决了频繁扩容而导致的时间损耗，不过缺点是可能会占用比较大的内存
2、 一开始不指定，而在插入前先使用ensureCapacity方法来指定容量，和上面的相比就是不占用内存，且拷贝的次数也大大减少了。
public class EnsureTest {
public static void main(String[] args) {
ArrayList<Object> list = new ArrayList<>();
final int N = 11111111;
long start = System.currentTimeMillis();
for (int i = 0; i < N; i++) {
list.add(i);
}
long end = System.currentTimeMillis();
System.out.println("不使用ensure" + (end - start));
long start1 = System.currentTimeMillis();
list = new ArrayList<>();
list.ensureCapacity(N);
for (int i = 0; i < N; i++) {
list.add(i);
}
long end1 = System.currentTimeMillis();
System.out.println("使用ensure" + (end1 - start1));
}
}
//输出结果：不使用ensure537 使用ensure358
//如果我们使用第一种直接指定，其实速度比ensure还慢一点。。
查看ensureCapacity源码：
public void ensureCapacity(int minCapacity) {
//判断条件：指定容量大于当前容量，且当前容量不等于空容量，参数大于10
//如果符合的话，就调用上面的扩容，这么做就扩容一次到位
if (minCapacity > elementData.length
&& !(elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
&& minCapacity <= DEFAULT_CAPACITY)) {
modCount++;
grow(minCapacity);
}
}
6.get方法
没什么说的，就是根据角标取数据，很简单
public E get(int index) {
//检查是否index合法
Objects.checkIndex(index, size);
return elementData(index);
}
7.set方法
public E set(int index, E element) {
//检查是否index合法
Objects.checkIndex(index, size);
//获得旧的value
E oldValue = elementData(index);
//赋新值
elementData[index] = element;
//返回旧的value
return oldValue;
}
8.检查位置Objects.checkIndex(index, size)
//上面的调用的这个方法
@ForceInline
public static
int checkIndex(int index, int length) {
return Preconditions.checkIndex(index, length, null);
}
//上面的调用的这个方法
@HotSpotIntrinsicCandidate
public static <X extends RuntimeException>
int checkIndex(int index, int length,
BiFunction<String, List<Integer>, X> oobef) {
//检查index位置是否合法
if (index < 0 || index >= length)
throw outOfBoundsCheckIndex(oobef, index, length);
return index;
}
//上面的return方法，用于返回元素
@SuppressWarnings("unchecked")
E elementData(int index) {
return (E) elementData[index];
}
jdk1.8的时候get是不会检查出来index是否小于0的，然而这个是基于jdk12的，他可以检查出小于0的。
9.indexOf相关方法
indexOf，从头开始判断是否存在指定元素，返回值为指定元素的索引：
public int indexOf(Object o) {
return indexOfRange(o, 0, size);
}
//上面的调用这个
int indexOfRange(Object o, int start, int end) {
//将原数组赋给es
Object[] es = elementData;
//判断要找的值是否为null值
if (o == null) {
for (int i = start; i < end; i++) {
//找到了直接返回null所在的索引
if (es[i] == null) {
return i;
}
}
} else {
//否则就找，看是否存在指定值，存在就返回索引
for (int i = start; i < end; i++) {
if (o.equals(es[i])) {
return i;
}
}
}
return -1;
}
返回列表中指定元素最后一次出现的索引：
public int lastIndexOf(Object o) {
return lastIndexOfRange(o, 0, size);
}
int lastIndexOfRange(Object o, int start, int end) {
Object[] es = elementData;
//跟前面很像，只不过这次是从后到前
if (o == null) {
for (int i = end - 1; i >= start; i--) {
if (es[i] == null) {
return i;
}
}
} else {
for (int i = end - 1; i >= start; i--) {
if (o.equals(es[i])) {
return i;
}
}
}
return -1;
}
小结：这两个方法也就表明，ArrayList里面是可以塞null的。
10.contains方法
没什么说的，判断list里是否有某元素，返回值为boolean类型：
public boolean contains(Object o) {
//调用上面的方法
//前面的返回的刚好就是个角标，只要看是否大于0就能判断有没有
return indexOf(o) >= 0;
}
11.toArray方法
以正确的顺序返回一个包含此list的所有元素的数组。返回的数组的运行时类型就是指定数组的运行时类型：
public Object[] toArray() {
return Arrays.copyOf(elementData, size);
}
@SuppressWarnings("unchecked")
public <T> T[] toArray(T[] a) {
//这个参数就是转换的目标类型数组
if (a.length < size)
// Make a new array of a's runtime type, but my contents:
return (T[]) Arrays.copyOf(elementData, size, a.getClass());
//如果给的数组大小小于list的size，则就直接返回list转成数组
System.arraycopy(elementData, 0, a, 0, size);
//如果给的数组大小大于list的size，则给后面的全部赋为null
if (a.length > size)
a[size] = null;
return a;
}
//这个方法的具体使用：
for (int i = 0; i < 10; i++) {
list.add(i);
}
Integer[] integers = list.toArray(new Integer[15]);
System.out.println(Arrays.toString(integers));
//输出结果：[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, null, null, null, null, null] 可以看出后面的全是null
3.多说一点之System.arraycopy()和Arrays.copyOf()
System.arraycopy()：
// src：源对象
// srcPos：源对象对象的起始位置
// dest：目标对象
// destPost：目标对象的起始位置
// length：从起始位置往后复制的长度。
// 复制src到dest，复制的位置是从src的srcPost开始，一共复制length个元素，复制到destPost上，从destPost开始
public static void arraycopy(Object src, int srcPos, Object dest, int destPos,
int length)
Arrays.copyOf()：
//copyOf即复制数组，返回值为T[]类型的数组。这两个参数是原来的数组，以及新数组的长度
public static <T> T[] copyOf(T[] original, int newLength) {
return (T[]) copyOf(original, newLength, original.getClass());
}
//复制指定的数组，如果有必要用0截取或者填充，使得副本具有指定长度。
//如果副本中有效而原数组中无效的所有索引，填充以0
//第三个参数为新的数组类型，因为要保证新的数组类型与原来的一样
public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
@SuppressWarnings("unchecked")
//申明一个T类型的 copy数组
T[] copy = ((Object)newType == (Object)Object[].class)
? (T[]) new Object[newLength]
: (T[]) Array.newInstance(newType.getComponentType(), newLength);
//将original的内容复制到copy中
System.arraycopy(original, 0, copy, 0,
Math.min(original.length, newLength));
return copy;
}
//测试Arrays.copyOf方法
int[] a = new int[3];
a[0] = 1;
a[1] = 2;
a[2] = 3;
int[] b = Arrays.copyOf(a, 11);
System.out.println(b.length);
System.out.println(Arrays.toString(b));
//输出 11 [1, 2, 3, 0, 0, 0, 0, 0, 0, 0, 0]
//可以看出，没有的用0来填充了
System.arraycopy与copyOf区别于联系： 联系：copyOf内部疯狂调用了arraycopy方法 区别：arraycopy参数就需要两个数组，而且是可以直接调用的那种，而copyOf返回值为copy好的数组，需要来一个数组对象来保存。如果不保存其实跟没反应一样。
写在最后：这篇基于jdk12的ArrayList源码阅读分析是本人的一些拙见，如果有误，还请各位大牛在评论区指出，也欢迎大家一起交流学习，十分感谢！