ArrayList 源码分析与常见问题
ArrayList简介
在Java中，ArrayList 是 java.util 包下的一个实现 List 接口的类，相当于动态数组，与数组相比，它提供了容量动态增长的功能。
下面会简述ArrayList 和源码分析，内容基于JDK8（1.8.0_331）。
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
...
}ArraryList 直接父类为 AbstractList，并实现了 List，RandomAccess，Cloneable，java.io.Serializable 这些接口。
AbstractList：这个抽象类提供了一套实现 List 接口所需的基本方法，如 get, set, add, remove, indexOf, size 等。通过继承 AbstractList，ArrayList 可以复用这些基本实现，并专注于实现其特定的数组存储逻辑。
List：表明它是一个列表，支持添加，删除，查找，通过下标进行访问等功能。
RandomAccess：List实现使用的标记接口，表明此类支持快速随机访问。ArrayList中，可以通过元素的序号快速获取元素对象，这就是快速随机访问。
Cloneable：支持拷贝，可以进行深拷贝或浅拷贝。
Serializable ：支持序列化，也就是讲对象转为字节流进行持久化存储或网络传输。
构造函数
在 ArrayList 源码中定义了 elementData 为保存 ArrayList 数据的数组。
在不同的构造方法中，都是使用定义的空数组或参数指定的值，并未使用到默认初始容量10。
特别是无参构造方法中，直接创建了一个空数组，并未对容量进行分配。
实际当真正对数组进行添加元素操作时，才真正分配容量，并使用扩容机制。
/**
* 默认初始容量
*/
private static final int DEFAULT_CAPACITY = 10;
/**
* 空数组（用于空实例）。
*/
private static final Object[] EMPTY_ELEMENTDATA = {};
/**
* 用于默认大小空实例的共享空数组实例。
* 我们把它从EMPTY_ELEMENTDATA数组中区分出来，以知道在添加第一个元素时容量需要增加多少。
*/
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
/**
* 用于存储列表元素的实际数组。transient 关键字表示该字段不会被序列化。
*/
transient Object[] elementData;
/**
* 数组长度
* 在构造函数中，只有在ArrayList(Collection<? extends E> c)有可能会被赋值，其他时候初始都为0
*/
private int size;
/**
* 默认构造函数，构造一个初始容量为10的空列表
*/
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
/**
* 带初始容量参数的构造函数。（用户自己指定容量）
*/
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {//初始容量大于0
//创建initialCapacity大小的数组
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {//初始容量等于0
//创建空数组
this.elementData = EMPTY_ELEMENTDATA;
} else {//初始容量小于0，抛出异常
throw new IllegalArgumentException("Illegal Capacity: " + initialCapacity);
}
}
/**
*构造包含指定collection元素的列表，这些元素利用该集合的迭代器按顺序返回
*如果指定的集合为null，throws NullPointerException。
*/
public ArrayList(Collection<? extends E> c) {
// 将集合对象转为数组
Object[] a = c.toArray();
// 判断数组长度不为0
if ((size = a.length) != 0) {
// 判断参数c是否是ArrayList类型
// 需要判断的原因是其他继承Collection类重写的toArray方法不一定会返回Object[]类型
if (c.getClass() == ArrayList.class) {
elementData = a;
} else {
// 如果是其他集合类型则需要通过拷贝的方式
elementData = Arrays.copyOf(a, size, Object[].class);
}
} else {
// 用空数组代替
elementData = EMPTY_ELEMENTDATA;
}
}
// 将集合转数组
public Object[] toArray() {
return Arrays.copyOf(elementData, size);
}
扩容机制
创建的ArrayList是空数组时，为数组进行分配初始容量（10）或扩容数组都是发生在添加元素方法中，所以了解扩容机制可以从add()方法开始。
/**
* 默认初始容量
*/
private static final int DEFAULT_CAPACITY = 10;
/**
* 用于存储列表元素的实际数组。transient 关键字表示该字段不会被序列化。
*/
transient Object[] elementData;
/**
* 用于默认大小空实例的共享空数组实例。
* 我们把它从EMPTY_ELEMENTDATA数组中区分出来，以知道在添加第一个元素时容量需要增加多少。
*/
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
/**
* 数组长度
* 在构造函数中，只有在ArrayList(Collection<? extends E> c)有可能会被赋值，其他时候初始都为0
*/
private int size;
public boolean add(E e) {
// 添加元素前，调用ensureCapacityInternal方法校验是否需要扩容
ensureCapacityInternal(size + 1); // Increments modCount!!
// 这里代表着ArrayList添加元素实际就是数组赋值
elementData[size++] = e;
return true;
}
/**
* 校验是否需要扩容
* minCapacity为当前数组长度+1
*/
private void ensureCapacityInternal(int minCapacity) {
// 使用calculateCapacity()方法计算当前数组需要的最小容量值
// 使用ensureExplicitCapacity()方法进行扩容
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
/**
* 计算当前数组需要的最小容量值
* elementData 当前数组实例
* minCapacity 当前数组长度+1
*/
private static int calculateCapacity(Object[] elementData, int minCapacity) {
// 这里 == 比较的是内存地址，只有使用无参构造方法时，此判断才会成立
// 判断成功，代表着是刚刚创建的空数组
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
// 此时会返回DEFAULT_CAPACITY（10），也就是ArrayList的默认大小
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
// 返回最小值
return minCapacity;
}
/**
* 根据最小容量值判断是否需要扩容
* minCapacity 当前数组需要的最小容量值
*/
private void ensureExplicitCapacity(int minCapacity) {
// 父类AbstractList中的值，初始为0，记录着被修改的次数
modCount++;
// 最小容量值-当前数组长度>0，则需要进行扩容
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
/**
* ArrayList的扩容方法
* minCapacity 当前数组需要的最小容量值
*/
private void grow(int minCapacity) {
int oldCapacity = elementData.length;
// oldCapacity >> 1 为将oldCapacity转为2进制，并向右移1位，其效果为 oldCapacity/2 并向下取整
// oldCapacity + (oldCapacity >> 1)就确定了扩容1.5倍的新值
// 这里需要注意，因为>>位移符向下取整，所以是1.5倍左右，偶数才一定是1.5倍
int newCapacity = oldCapacity + (oldCapacity >> 1);
// 这里做了一次校验新容量大小是否够用
// 新容量 - 最小需要容量 < 0,那么最小容量值就会作为数组的新容量值
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
// MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
// 如果新容量值 大于 MAX_ARRAY_SIZE 会进入hugeCapacity()方法中确定数组最大值
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// 创建扩容后的新数组
elementData = Arrays.copyOf(elementData, newCapacity);
}
/**
* ArrayList的扩容到最大值的赋值方法
* 这个方法也代表了ArrayList容量的最大值是Int的最大值
*/
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
// 进来这里代表着计算出来的1.5倍扩容值已经超过了ArrayList的最大值
// 这里使用 需要的最小容量值进行比较，
// 如果大于ArrayList的最大值，则会使用Int最大值来作为扩容值
// 如果小于则会使用Int最大值 - 8 来作为扩容值
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}System.arraycopy()和Arrays.copyOf()方法
在源码中大量使用了这两种拷贝方法。
在此对比两种拷贝方法有何不同。
Arrays.copyOf()方法
/**
* 创建一个新数组，它是指定数组的副本。新数组的类型与指定数组元素的类型相同，长度为指定的新长度。
*
* @param original 被复制数组。
* @param newLength 新数组的长度。
* @param newType 新数组的类型。
* @return 一个新的数组，它是原始数组的副本，类型和长度符合指定。
*/
public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
// 创建一个新的数组实例，根据newType的类型和newLength的长度。
@SuppressWarnings("unchecked")
T[] copy = ((Object)newType == (Object)Object[].class)
? (T[]) new Object[newLength]
: (T[]) Array.newInstance(newType.getComponentType(), newLength);
// 将原始数组的内容复制到新数组中，都从索引0开始复制。
System.arraycopy(original, 0, copy, 0,
Math.min(original.length, newLength));
return copy;
}
System.arraycopy() 方法
/**
* 将源对象数组中指定范围的元素复制到目标对象数组的指定位置。
* arraycopy是一个native方法
*
* @param src 源对象数组，必须是数组类型。
* @param srcPos 源数组中开始复制的索引位置。
* @param dest 目标对象数组，必须是数组类型。
* @param destPos 目标数组中开始粘贴的索引位置。
* @param length 要复制的元素个数。
*/
public static native void arraycopy(Object src, int srcPos,
Object dest, int destPos,
int length);
从源码中可以发现 Arrays.copyOf() 也调用了 System.arraycopy() 来进行拷贝，而 System.arraycopy() 是浅拷贝，所以这两种方法都是浅拷贝。
区别
参数不同
Arrays.copyOf() 需要提供原数组，数组长度，数组类型。
System.arraycopy() 需要提供原数组，原数组起始位置，目标数组，目标数组起始位置，复制元素个数。
返回值不同
Arrays.copyOf() 返回一个新数组
Arrays.copyOf() 无返回值
总结
Arrays.copyOf() 与 System.arraycopy() 都用有复制的功能，但实际效果并不相同。
Arrays.copyOf()
使用了数组长度创建了新的数组，我认为是在复制的同时，完成了对数组的扩容。
System.arraycopy()
并没有创建新的数组，同时原数组与目标数组的索引选择，可以实现一些特定的操作。
比如在 ArrayList 源码中public void add(int index, E element) 方法是往数组指定的下标插入一位元素
就使用了 System.arraycopy() 方法让指定下标后的所有的元素都往后移动了一位，再通过数组下标的方式赋值元素。
Arrays.asList() 为什么不可以 add()？
使用 Arrays.asList() 创建出来的不支持 add() 与 remove() 方法
查看 Arrays 的源码可以发现，创建出来的 ArrayList 不是我们常用的 java.util.ArrayList，而是在 Arrays 的源码中有一个 ArrayList 内部类。
这个内部类并没有实现 add() ， remove()，clear()等会改变列表大小的方法。
Arrays.asList() 方法设置的初衷是让我们可以快速的创建一个List用于传递数据。
