Java容器系列-ArrayList源码分析

ArrayList 是使用的最为广泛的一个容器。ArrayList 的类的继承层次图如下:

ArrayList 实现了 CollectionList 接口,同时也实现了 CloneableRandomAccess,所以 ArrayList 可以被拷贝以及具有随机访问的特性。

本文基于 JDK1.8

成员变量

在 ArrayList 类的头部,定义了以下几个成员变量。

1
2
3
4
5
private static final int DEFAULT_CAPACITY = 10;
private static final Object[] EMPTY_ELEMENTDATA = {};
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
transient Object[] elementData;
private int size;

这几个变量构成了 ArrayList 的基础。

DEFAULT_CAPACITY 表示 ArrayList 的初始容量。elementData 是存储具体数据的数组,也就是是说,ArrayList 底层数据结构就是一个数组,size 表示 ArrayList 中元素的个数。EMPTY_ELEMENTDATA 表示一个空的 ArrayList 对象,但 ArrayList 中没有数据时,elementData 指向的就是这个数组对象。DEFAULTCAPACITY_EMPTY_ELEMENTDATA 也表示空的 ArrayList,它只会在实例化一个不带参数的 ArrayList 的时候被使用一次:

1
ArrayList list = new ArrayList(); // 此时 elementData 指向的就是 DEFAULTCAPACITY_EMPTY_ELEMENTDATA

这些变量中需要注意的是 elementData 是不带访问修饰符的,这是为了让 ArrayList 的内部类可以方便的访问它,ArrayList 的内部类后面会讲到。elementData 变量是使用 transient 来修饰的,这表示在序列化的时候 elementData 是不会被序列化的,具体的序列化方式后面再讲。

初始化过程

在上面说到 DEFAULT_CAPACITY 是 ArrayList 的默认容量,值是10,但是需要注意的是,默认容量不一定用的上,在实例化 ArrayList 的时候分三种情况,第一种不给构造函数传参,但是此时会新建一个长度为 10 的对象数组。而是在添加第一个元素的时才会创建一个长度为 10 的数组,并把第一个元素添加进去。第二种情况会给构造参数传值 n,如果 n 大于0,那么就会直接创建一个长度为 n 的对象数组,如果 n 等于 0,那么就会把 EMPTY_ELEMENTDATA 赋值给 elementData。

第三种实例化特殊一点,是直接传入另一个容器对象 c 来初始化 ArrayList 对象,此时会先检查 c 的长度,如果 c 容器里面没有元素,直接把 EMPTY_ELEMENTDATA 赋值给 elementData,如果 c 不为空,就会 c 中的元素拷贝到 elementData 中。

扩容过程

扩容的过程可以用以下的流程图来表示:

扩容对 ArrayList 来说是一个很重要的过程,这也是为什么它比数组好用的原因。

ArrayList 的扩容有两种方式,一个是自动扩容,一种是手动扩容。自动扩容每次会把当前容器的大小扩大 1.5 倍,手动扩容需要指定大小。既然已经有了自动扩容,那为什么还需要手动扩容呢?设想一个场景,实例化一个 ArrayList 之后,你大概知道会填充一万个元素,如果这个时候自动扩容的话要经过多次扩容才能装下这么多元素,但是手动指定容器大小的话只需要一次就可以了。

具体把 ArrayList 扩容到多大是由下面这段代码决定的:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
private int newCapacity(int minCapacity) {
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity <= 0) {
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);
}

private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE)
? Integer.MAX_VALUE
: MAX_ARRAY_SIZE;
}

newCapacity 是根据当前的元素的个数计算出来的,右移一位代表除以2,所以 newCapacity 为当前容量的 1.5 倍。然后这个值会与传入的值 minCapacity 进行对比,两个值哪个大就用哪个。

为什么每次自动扩容都能为当前大小的 1.5 倍呢?那是因为自动扩容的时候传入的 minCapacity 都只比当前的容量大 1,所以肯定小于 newCapacity。而 newCapacity 就是 当前容量大小的 1.5 倍。

当然有一个情况例外,那就是如果在实例化 ArrayList 没有指定大小的话,ArrayList 会至少扩容到 10。这一机制是靠以下代码实现的:

1
2
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
return Math.max(DEFAULT_CAPACITY, minCapacity);

扩容的时候,都是使用 Arrays.copyOf 将元素拷贝到新的容器中。所以基本都是 $O(N)$ 的时间复杂度,代价很大。所以尽可能减少扩容的次数。

注意:ArrayList 没有缩容的过程。

具体实现

ArrayList 中有了很多的方法,这些方法核心都是围绕 elementData 操作的。

siez()isEmpty() 方法想着简单,一个用来返回容器中的元素的数量,一个用来判断容器是否为空。

clone()toArray()toArray(T[] a) 这三个方法本质上都是对容器当前的元素做一个备份,都用到了 Arrays.copyOf() 方法。但是需要注意的是 toArray(T[] a) 的实现:

1
2
3
4
5
6
7
8
9
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());
System.arraycopy(elementData, 0, a, 0, size);
if (a.length > size)
a[size] = null;
return a;
}

在这个方法中除了使用 Arrays.copyOf() 还用到了 System.arraycopy(),其实 Arrays.copyOf() 底层就是使用 System.arraycopy() 方法实现的。但是区别在于前者会返回一个一个新的数组,后者则是直接在原数组上进行操作。

ArrayList 中的 add()get()set()remove() 等方法用于元素的增删改查,实现并不复杂,只是在操作元素之前需要对容器的 size 进行检查,如果不满足操作要求,就会报出异常。

euqal() 类的方法主要都是对比每个元素的类型、顺序和值是否一致。

在 JDK1.8 以后,出现了 removeIf() 方法,这个方法使得从容器中删除元素变得很简单。

迭代器

ArrayList 中有两个内部类 ItrListItr,主要方法如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
private class Itr implements Iterator<E> {
Itr() {}

public boolean hasNext() {
}

public E next() {

}

public void remove() {
}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
private class ListItr extends Itr implements ListIterator<E> {
ListItr(int index) {
super();
cursor = index;
}

public boolean hasPrevious() {
}

public int nextIndex() {
}

public int previousIndex() {
}

public E previous() {
}

public void set(E e) {
}

public void add(E e) {
}
}

ListItr 继承了 Itr,这两个内部类都实现了迭代器模式,用于遍历 ArrayList 的元素。从上面的方法可知,Itr 和 ListItr 最大的区别在于 ListItr 可以从两个方向对容器的元素进行遍历。而 Itr 只能使用顺着一个方向进行遍历。

在 JDK1.8 以后,ArrayList 中有一个 ArrayListSpliterator 内部类,这个类用于分割容器。用于提升多线程环境中的处理效率:

1
2
3
4
5
6
7
8
ArrayList<Integer> list = new ArrayList<>();
for (int i = 0; i < 10; i++) {
list.add(i);
}
Spliterator<Integer> s0 = list.spliterator();
System.out.println(s0.estimateSize()); // 5
Spliterator<Integer> s1 = s0.trySplit();
System.out.println(s1.estimateSize()); // 5

s0 中有 10 个元素,在调用 s0.trySplit() 方法之后,s0 和 s1 中各有 5 个元素。然后可以对分割开的元素进行处理:

1
s0.forEachRemaining(i -> System.out.println(i));

SubList

ArrayList 中还有一个内部类 SubList。SubList 用于返回 ArrayList 的一部分元素,内部的操作方法与 ArrayList 基本一致,但是需要注意的是,对 SubList 的操作会直接影响到原 ArrarList。

fail-fast 机制

在 ArrayList 中,checkForComodification()ConcurrentModificationException() 使用的频率很高。这个和 fail-fast 机制有关。

ArrayList 不是线程安全的,所以在对容器操作的过程中,容器的元素倍其他的操作或者线程修改之后,就会出现 ConcurrentModificationException 异常。checkForComodification() 方法就是用来检查元素是否被修改。这个机制就称之为 fail-fast

后续会有其他的文章来介绍 fail-fast

(完)

微信公众号

© 2018 ray