ArrayList 源码解析
原创
简介
ArrayList是一种变长的集合类，基于定长数组实现。ArrayList 允许空值和重复元素，当往 ArrayList 中添加的元素数量大于其底层数组容量时，其会通过扩容机制重新生成一个更大的数组。另外，由于 ArrayList 底层基于数组实现，所以其可以保证在O(1)复杂度下完成随机查找操作。其他方面，ArrayList 是非线程安全类，并发环境下，多个线程同时操作 ArrayList，会引发不可预知的错误。
ArrayList实现了List接口的所有方法，可以看成是“长度可调节的数组”，可以包含任何类型数据（包括null，可重复）。ArrayList大体和Vector一致，唯一区别是ArrayList非线程安全，Vector线程安全，但Vector线程安全的代价较大，推荐使用CopyOnWriteArrayList。
它基本属性包括以下几点：
关注 | 结论 |
|---|---|
是否为空 | 允许 |
是否重复数据 | 允许 |
是否有序 | 有序 |
是否线程安全 | 非线程安全 |
类结构
ArrayList类层级关系如下图所示：
ArrayList类主要包含如下两个成员变量：
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
// 数组默认初始化容量为10
private static final int DEFAULT_CAPACITY = 10;
// 表示空数组
private static final Object[] EMPTY_ELEMENTDATA = {};
// 也是空数组，和EMPTY_ELEMENTDATA区分开
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
transient Object[] elementData; // elementData为Object类型数组，用于存放ArrayList数据
private int size; // size表示数组元素个数（并非数组容量）
......
}方法解析
Arrays类的copyOf(U[] original, int newLength, Class<? extends T[]> newType)方法用于复制指定数组original到新数组，新数组的长度为newLength，新数组元素类型为newType。
- 如果新数组的长度大于旧数组，那么多出的那部分用null填充；
- 如果新数组的长度小于旧数组，那么少的那部分直接截取掉；
举两个例子：
Long[] array1 = new Long[]{1L, 2L, 3L};
Object[] array2 = Arrays.copyOf(array1, 5, Object[].class);
System.out.println(Arrays.toString(array2)); // [1, 2, 3, null, null]
Object[] array3 = Arrays.copyOf(array1, 1, Object[].class);
System.out.println(Arrays.toString(array3)); // [1]重载方法copyOf(T[] original, int newLength)用于复制指定数组original到新数组，新数组的长度为newLength，新数组元素类型和旧数组一致。
copyOf方法内部调用System类的native方法arraycopy(Object src, int srcPos,Object dest, int destPos, int length)：
public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> 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;
}
src：需要被拷贝的旧数组；
srcPos：旧数组开始拷贝的起始位置；
dest：拷贝目标数组；
destPos：目标数组的起始拷贝位置；
length：拷贝的长度。举个例子：
Long[] array1 = new Long[]{1L, 2L, 3L};
Object[] array2 = new Object[5];
System.arraycopy(array1, 0, array2, 0, 3);
System.out.println(Arrays.toString(array2)); // [1, 2, 3, null, null]
指定位置插入元素：
Long[] array1 = new Long[]{1L, 2L, 3L, null, null, null};
int index = 1;
System.arraycopy(array1, index, array1, index + 1, 3 - index);
array1[index] = 0L;
System.out.println(Arrays.toString(array1)); // [1, 0, 2, 3, null, null]构造函数
空参构造函数：public ArrayList()：
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}空参构造函数，elementData为DEFAULTCAPACITY_EMPTY_ELEMENTDATA，是一个大小为0的空数组。
有参构造函数：public 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);
}
}创建容量大小为initialCapacity的ArrayList，如果initialCapacity小于0，则抛出IllegalArgumentException异常；如果initialCapacity为0，则elementData为EMPTY_ELEMENTDATA，是一个大小为0的空数组。
上面的代码比较简单，两个构造方法做的事情并不复杂，目的都是初始化底层数组 elementData。区别在于无参构造方法会将 elementData 初始化一个空数组，插入元素时，扩容将会按默认值重新初始化数组。而有参的构造方法则会将 elementData 初始化为参数值大小（>= 0）的数组。一般情况下，我们用默认的构造方法即可。倘若在可知道将会向 ArrayList 插入多少元素的情况下，应该使用有参构造方法。按需分配，避免浪费。
有参构造函数：public ArrayList(Collection<? extends E> c)：
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
if ((size = elementData.length) != 0) {
// c.toArray might (incorrectly) not return Object[] (see 6260652)
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
// replace with empty array.
this.elementData = EMPTY_ELEMENTDATA;
}
}创建一个包含指定集合c数据的ArrayList。上面为什么要多此一举使用Arrays.copyOf(elementData, size, Object[].class)复制一遍数组呢？这是因为在某些情况下调用集合的toArray()方法返回的类型并不是Object[].class，比如：
举个例子：
Long[] array1 = {1L, 2L};
List<Long> list1 = Arrays.asList(array1);
Object[] array2 = list1.toArray();
System.out.println(array2.getClass() == Object[].class); // false
List<Long> list2 = new ArrayList<>();
System.out.println(list2.toArray().getClass() == Object[].class); // trueadd(E e)
add(E e)用于尾部添加元素：
public boolean add(E e) {
/**
* 添加一个元素时，做了如下两步操作
* 1.判断列表的capacity容量是否足够，是否需要扩容
* 2.真正将元素放在列表的元素数组里面
*/
// 检测是否需要扩容。（非原子操作）在多个线程进行add操作时可能会导致elementData数组越界
ensureCapacityInternal(size + 1);
// 将新元素插入序列尾部。（非原子操作）置值的操作同样会导致线程不安全
elementData[size++] = e;
return true;
}
对于在元素序列尾部插入，这种情况比较简单，只需两个步骤即可：
- 检测数组是否有足够的空间插入
- 将新元素插入至序列尾部
通过上面源码分析我们可以知道：
- 任何一个空的ArrayList在添加第一个元素时，内部数组容量将被扩容为10；
- 扩容时，newCapacity为oldCapacity的1.5倍；
- 数组容量最大为Integer.MAX_VALUE；
- 尾部添加元素不用移动任何元素，所以速度快。
add(int index, E element)
// 用于在指定位置添加元素：
add(int index, E element)
public void add(int index, E element) {
// 下标检查
rangeCheckForAdd(index);
// 确定数组容量，和上面add(E e)方法介绍的一致
ensureCapacityInternal(size + 1);
// 将原来index后面的所有元素往后面移动一个位置
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
// index处放入新元素
elementData[index] = element;
// size递增
size++;
}
private void rangeCheckForAdd(int index) {
// 下标比size大或者下标小于0，都会抛出下标越界异常
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
如果是在元素序列指定位置（假设该位置合理）插入，则情况稍微复杂一点，需要三个步骤：
- 检测数组是否有足够的空间
- 将 index 及其之后的所有元素向后移一位
- 将新元素插入至 index 处
将新元素插入至序列指定位置，需要先将该位置及其之后的元素都向后移动一位，为新元素腾出位置。这个操作的时间复杂度为O(N)，频繁移动元素可能会导致效率问题，特别是集合中元素数量较多时。在日常开发中，若非所需，我们应当尽量避免在大集合中调用第二个插入方法。
get(int index)
get(int index)获取指定位置元素：
public E get(int index) {
// 下标合法性检查
rangeCheck(index);
// 直接返回数组指定位置元素
return elementData(index);
}
E elementData(int index) {
return (E) elementData[index];
}get方法直接返回数组指定下标元素，速度非常快。
set(int index, E element)
set(int index, E element)设置指定位置元素为指定值：
public E set(int index, E element) {
// 下标合法性检查
rangeCheck(index);
// 根据下标获取旧值
E oldValue = elementData(index);
// 设置新值
elementData[index] = element;
// 返回旧值
return oldValue;
}set方法不涉及元素移动和遍历，所以速度快。直接用新值替换旧值，并返回旧值。
remove(int index)
删除指定位置元素：remove(int index)
public E remove(int index) {
rangeCheck(index);
modCount++;
// 获取指定位置元素（需要被删除的元素）
E oldValue = elementData(index);
int numMoved = size - index - 1;
if (numMoved > 0)
// 直接将index后面的元素往前移动一位，覆盖index处的元素
System.arraycopy(elementData, index+1, elementData, index, numMoved);
elementData[--size] = null; // clear to let GC do its work
// 返回被删除的元
return oldValue;
}上述方法涉及到元素移动，所以效率也不高。
上面的删除方法并不复杂，删除一个元素步骤如下：
- 获取指定位置 index 处的元素值
- 将 index + 1 及之后的元素向前移动一位
- 将最后一个元素置空，并将 size 值减 1
- 返回被删除值，完成删除操作
remove(Object o)
删除指定元素：remove(Object o)
// 遍历数组，找到第一个目标元素，然后删除
public boolean remove(Object o) {
if (o == 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);
return true;
}
}
return false;
}
// 逻辑和remove一致，都是将index后面的元素往前移动一位，覆盖index处的元素
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
}方法涉及到数组遍历和元素移动，效率也不高。
trimToSize()
描述：用于将数组容量调整为实际元素个数大小，当一个ArrayList元素个数不会发生改变时，可以调用该方法减少内存占用。
将数组容量缩小至元素数量：
public void trimToSize() {
modCount++;
if (size < elementData.length) {
elementData = (size == 0)
? EMPTY_ELEMENTDATA
: Arrays.copyOf(elementData, size);
}
}通过上面的方法，我们可以手动触发 ArrayList 的缩容机制。这样就可以释放多余的空间，提高空间利用率。
扩容机制
对于变长数据结构，当结构中没有空余空间可供使用时，就需要进行扩容。在 ArrayList 中，当空间用完，其会按照原数组空间的1.5倍进行扩容。相关源码如下：
/** 计算最小容量 */
private static int calculateCapacity(Object[] elementData, int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
// DEFAULT_CAPACITY=10，minCapacity=1，故返回10
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
/** 扩容的入口方法 */
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// minCapacity=10，elementData.length=0，所以调用grow方法扩容
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
/** 扩容的核心方法 */
private void grow(int minCapacity) {
// oldCapacity=0
int oldCapacity = elementData.length;
// newCapacity = oldCapacity + oldCapacity / 2 = oldCapacity * 1.5
// newCapacity为oldCapacity的1.5倍，这里为0
int newCapacity = oldCapacity + (oldCapacity >> 1);
// newCapacity=0，minCapacity=10，所以该条件成立
if (newCapacity - minCapacity < 0)
// newCapacity=10
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// 扩容
// 复制到新数组，数组容量为10
elementData = Arrays.copyOf(elementData, newCapacity);
}
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 - 8，通过
// 这段逻辑我们可以知道，ArrayList最大容量为Integer.MAX_VALUE
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}遍历
ArrayList 实现了 RandomAccess 接口（该接口是个标志性接口），表明它具有随机访问的能力。ArrayList 底层基于数组实现，所以它可在常数阶的时间内完成随机访问，效率很高。对 ArrayList 进行遍历时，一般情况下，我们喜欢使用 foreach 循环遍历，但这并不是推荐的遍历方式。ArrayList 具有随机访问的能力，如果在一些效率要求比较高的场景下，更推荐下面这种方式：
for (int i = 0; i < list.size(); i++) {
list.get(i);
}RandomAccess接口是一个空接口，不包含任何方法，只是作为一个标识：
package java.util;
public interface RandomAccess {
}实现该接口的类说明其支持快速随机访问，比如ArrayList实现了该接口，说明ArrayList支持快速随机访问。所谓快速随机访问指的是通过元素的下标即可快速获取元素对象，无需遍历，而LinkedList则没有这个特性，元素获取必须遍历链表。
在Collections类的binarySearch(List<? extends Comparable<? super T>> list, T key)方法中，可以看到RandomAccess的应用：
public static <T>
int binarySearch(List<? extends Comparable<? super T>> list, T key) {
if (list instanceof RandomAccess || list.size()<BINARYSEARCH_THRESHOLD)
return Collections.indexedBinarySearch(list, key);
else
return Collections.iteratorBinarySearch(list, key);
}当list实现了RandomAccess接口时，调用indexedBinarySearch方法，否则调用iteratorBinarySearch。所以当我们遍历集合时，如果集合实现了RandomAccess接口，优先选择普通for循环，其次foreach；遍历未实现RandomAccess的接口，优先选择iterator遍历。
快速失败机制
在 Java 集合框架中，很多类都实现了快速失败机制。该机制被触发时，会抛出并发修改异常ConcurrentModificationException，这个异常大家在平时开发中多多少少应该都碰到过。关于快速失败机制，ArrayList 的注释里对此做了解释，这里引用一下：
The iterators returned by this class’s iterator() and listIterator(int) methods are fail-fast if the list is structurally modified at any time after the iterator is created, in any way except through the iterator’s own ListIterator remove() or ListIterator add(Object) methods, the iterator will throw a ConcurrentModificationException. Thus, in the face of concurrent modification, the iterator fails quickly and cleanly, rather than risking arbitrary, non-deterministic behavior at an undetermined time in the future.
上面注释大致意思是，ArrayList 迭代器中的方法都是均具有快速失败的特性，当遇到并发修改的情况时，迭代器会快速失败，以避免程序在将来不确定的时间里出现不确定的行为。
遍历时删除
遍历时删除是一个不正确的操作，即使有时候代码不出现异常，但执行逻辑也会出现问题。关于这个问题，阿里巴巴 Java 开发手册里也有所提及。这里引用一下：
【强制】不要在 foreach 循环里进行元素的 remove/add 操作。remove 元素请使用 Iterator 方式，如果并发操作，需要对 Iterator 对象加锁。
相关代码（稍作修改）如下：
List<String> a = new ArrayList<String>();
a.add("1");
a.add("2");
for (String temp : a) {
System.out.println(temp);
if("1".equals(temp)){
a.remove(temp);
}
}
}相信有些朋友应该看过这个，并且也执行过上面的程序。上面的程序执行起来不会虽不会出现异常，但代码执行逻辑上却有问题，只不过这个问题隐藏的比较深。我们把 temp 变量打印出来，会发现只打印了数字1，2没打印出来。初看这个执行结果确实很让人诧异，不明原因。如果死抠上面的代码，我们很难找出原因，此时需要稍微转换一下思路。我们都知道 Java 中的 foreach 是个语法糖，编译成字节码后会被转成用迭代器遍历的方式。所以我们可以把上面的代码转换一下，等价于下面形式：
List<String> a = new ArrayList<>();
a.add("1");
a.add("2");
Iterator<String> it = a.iterator();
while (it.hasNext()) {
String temp = it.next();
System.out.println("temp: " + temp);
if("1".equals(temp)){
a.remove(temp);
}
}这个时候，我们再去分析一下 ArrayList 的迭代器源码就能找出原因。
private class Itr implements Iterator<E> {
int cursor; // index of next element to return
int lastRet = -1; // index of last element returned; -1 if no such
int expectedModCount = modCount;
public boolean hasNext() {
return cursor != size;
}
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;
return (E) elementData[lastRet = i];
}
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
// 省略不相关的代码
}我们一步一步执行一下上面的代码，第一次进入 while 循环时，一切正常，元素 1 也被删除了。但删除元素 1 后，就无法再进入 while 循环，此时 it.hasNext() 为 false。原因是删除元素 1 后，元素计数器 size = 1，而迭代器中的 cursor 也等于 1，从而导致 it.hasNext() 返回false。归根结底，上面的代码段没抛异常的原因是，循环提前结束，导致 next 方法没有机会抛异常。不信的话，大家可以把代码稍微修改一下，即可发现问题：
List<String> a = new ArrayList<>();
a.add("1");
a.add("2");
a.add("3");
Iterator<String> it = a.iterator();
while (it.hasNext()) {
String temp = it.next();
System.out.println("temp: " + temp);
if("1".equals(temp)){
a.remove(temp);
}
}我们要避免上面的做法。正确的做法使用迭代器提供的删除方法，而不是直接删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。