JDK源码解读（二）：ArrayList、Vector
更新日期:
JDK容器类的线性表主要分两种：一种是以ArrayList为代表的顺序存储线性表；另一种是以LinkedList为代表的链式存储线性表。
List
上篇提到过List接口在Collection的基础之上增加了大量的方法，主要用来支持在序列中间插入和删除元素。下面列出List接口的定义。1
2
3
4
5
6
7
8
9
10
11
12
13public interface List<E> extends Collection<E> {
// 此处省略Collection中定义的方法
E get(int index);
E set(int index, E element);
void add(int index, E element);
E remove(int index);
int indexOf(Object o);
int lastIndexOf(Object o);
ListIterator<E> listIterator();
ListIterator<E> listIterator(int index);
List<E> subList(int fromIndex, int toIndex);
// 此处省略其他方法
}
AbstractList
AbstractList继承自AbstractCollection父类，并且实现了List接口。
equals方法
AbstractList重写了equals方法，List判断equals的标准是遍历每一个元素，依次调用对象的equals方法判断，代码如下所示1
2
3
4
5
6
7
8
9
10
11
12
13
14
15public boolean equals(Object o) {
if (o == this)
return true;
if (!(o instanceof List))
return false;
ListIterator<E> e1 = listIterator();
ListIterator<?> e2 = ((List<?>) o).listIterator();
while (e1.hasNext() && e2.hasNext()) {
E o1 = e1.next();
Object o2 = e2.next();
if (!(o1==null ? o2==null : o1.equals(o2)))
return false;
}
return !(e1.hasNext() || e2.hasNext());
}
hashCode方法
AbstractList重写了hashCode方法，hashcode的计算公式为：
1
2
3
4
5
6public int hashCode() {
int hashCode = 1;
for (E e : this)
hashCode = 31*hashCode + (e==null ? 0 : e.hashCode());
return hashCode;
}
ArrayList
定义
首先看ArrayList的定义，其继承自AbstractList，实现了List、RandomAccess、Cloneable、Serializable接口。1
2public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
- RandomAccess是一个标识接口，用来表明其支持快速（通常是固定时间）随机访问。此接口的主要目的是允许一般的算法更改其行为，从而在将其应用到随机或连续访问列表时能提供良好的性能。
- Cloneable接口，实现了此接口的类，可以调用Object.clone完成对象的浅复制。
- Serializable也是一个标识接口，实现了此接口的类，支持对象的序列化。
构造器
前面提到，ArrayList基于数组实现。ArrayList中只有两个私有属性，如下：1
2transient Object[] elementData; // 使用一个对象数组来保存，transient意味着不被序列化
private int size; // 记录当前的长度
在ArrayList初始化的时候，如果没有指定长度，默认为一个空数组。1
2
3
4
5
6
7
8
9
10
11
12private static final Object[] EMPTY_ELEMENTDATA = {}; // 空ArrayList共享此数组
public ArrayList(int initialCapacity) { // 指定长度的初始化
super();
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+initialCapacity);
this.elementData = new Object[initialCapacity];
}
public ArrayList() {
super();
// 默认为空数组
this.elementData = EMPTY_ELEMENTDATA;
}
动态扩增
当数组长度不够的时候，ArrayList会调用grow方法先以1.5倍速度扩增数组，然后再将数据拷贝到新的数组中。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37// 调用者可以通过此方法，主动增大数组的长度
public void ensureCapacity(int minCapacity) {
// 当初始化为空数组情况时，返回默认长度10
int minExpand = (elementData != EMPTY_ELEMENTDATA) ? 0 : DEFAULT_CAPACITY;
if (minCapacity > minExpand) {
ensureExplicitCapacity(minCapacity);
}
}
// 在ArrayList的add、addAll等方法中，都会调用此方法检查数组容量是否足够。
private void ensureCapacityInternal(int minCapacity) {
if (elementData == EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
// 最终都会调用此方法，以1.5倍速度扩增数组
private void grow(int minCapacity) {
int oldCapacity = elementData.length;
// newCapacity = oldCapacity * 1.5，1.5倍速度扩增
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
elementData = Arrays.copyOf(elementData, newCapacity); // 调用Arrays.copyOf方法拷贝数组
}
// 此方法定义可以看出，list的最大长度（数组的最大长度）为Integer.MAX_VALUE
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;
}
数组拷贝使用了工具类Arrays的copyOf方法，追踪源码1
2
3
4
5
6
7
8
9
10
11
12
13
14// java.util.Arrays#copyOf
public static <T,U> T[] copyOf(U[] original, int newLength,
Class<? extends T[]> newType) {
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)); // 调用了System.arraycopy进行拷贝
return copy;
}
// java.lang.System#arraycopy
public static native void arraycopy(Object src,
int srcPos,Object dest, int destPos, int length);
可以看到最终调用了System.arraycopy方法完成数组的拷贝。这是一个native方法，意味着虚拟机已经使用C++实现了数组拷贝的功能。设计者考虑到数组拷贝是个相当频繁的操作，采用了此种方式实现是为了提高拷贝的效率。
add方法
1 | public boolean add(E e) { |
add的总体思路：1）检查是否越界；2）检查容量是否足够；3）插入位置后面元素后移；4）插入位置赋值插入对象。
remove方法
1 | public E remove(int index) { |
remove的思路：1）检查是否越界；2）修改modCount；3）删除位置后面元素前移；4）末尾置null。此处只列出了E remove(int index)方法的实现，其余remove方法如boolean remove(Object o)、boolean removeAll(Collection<?> c)思路类似。需要注意的是所有的remove方法都修改了modCount值，下面会讲到此值的作用！
迭代器
所有的Collection都提供了迭代器的实现，用于遍历访问Collection的元素。List额外支持双向迭代ListIterator。
ArrayList的迭代器结构如上图所示，典型的迭代器模式。迭代器实现类Itr和ListItr为ArrayList的内部类。
ArrayList的迭代遵循fail-fast机制。当迭代遍历过程中，如果使用其他方法如remove改变List结构，就会抛出ConcurrentModificationException，从源码可以看出这种安全检查基于之前提到的modCount。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38private class Itr implements Iterator<E> {
int cursor; // 遍历用指针
int lastRet = -1;
// 初始化迭代器时，用expectedModCount记录当前modCount
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];
}
public void remove() {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification(); // 检查是否有并发修改
try {
ArrayList.this.remove(lastRet);
cursor = lastRet;
lastRet = -1;
expectedModCount = modCount; // 更改expectedModCount值以保证安全
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
final void checkForComodification() {
// 通过比较modCount和expectedModCount，判断是否存在并发修改，如果有的话抛出异常
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}
- 其他Collection的迭代器模式实现均类似于ArrayList
- 其他Collection的迭代器fast-fail机制均类似于ArrayList
Collections的同步方法
Collections工具类为集合提供了各种工具方法，其中synchronizedXxx()方法用于把各种线程不安全的容器变为线程安全的。以List为例，这种实现如下所示：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39public static <T> List<T> synchronizedList(List<T> list) {
return (list instanceof RandomAccess ?
new SynchronizedRandomAccessList<>(list) :
new SynchronizedList<>(list));
}
static class SynchronizedList<E>
extends SynchronizedCollection<E> implements List<E> {
final List<E> list;
SynchronizedList(List<E> list) {
super(list);
this.list = list;
}
SynchronizedList(List<E> list, Object mutex) {
super(list, mutex);
this.list = list;
}
public E get(int index) {
synchronized (mutex) {return list.get(index);}
}
public E set(int index, E element) {
synchronized (mutex) {return list.set(index, element);}
}
public void add(int index, E element) {
synchronized (mutex) {list.add(index, element);}
}
public E remove(int index) {
synchronized (mutex) {return list.remove(index);}
}
public int indexOf(Object o) {
synchronized (mutex) {return list.indexOf(o);}
}
public int lastIndexOf(Object o) {
synchronized (mutex) {return list.lastIndexOf(o);}
}
public boolean addAll(int index, Collection<? extends E> c) {
synchronized (mutex) {return list.addAll(index, c);}
}
// 此处省略其他方法
}
可以看出来，synchronizedList方法构造的线程安全容器，仅仅是对每个线程不安全的方法使用synchronized关键字修饰。其线程安全的原理同Vector。
- 其他Collections中的同步方法原理均类似于List
Vector
Vector是JDK早期版本的基于数组实现的线性表。
定义
1 | public class Vector<E> |
从定义来看，Vector和ArrayList完全一样，继承自AbstractList，实现了List、RandomAccess、Cloneable、Serializable接口。
构造器
1 | protected Object[] elementData; // 用Object数组保存对象 |
动态扩增
1 | private void grow(int minCapacity) { |
Vector的自动扩增策略与ArrayList稍有不同。ArrayList每次以1.5倍速度扩增；Vector如果初始化时指定了capacityIncrement，则每次以该变量值为单位扩增，否则每次扩增为原来长度的2倍。
线程安全性
Vector和ArrayList最大的区别是Vector本身是线程安全的。从源码可以很清楚的看到Vector如何实现线程安全的，即用synchronized修饰所有可能造成不安全访问的方法。1
2
3
4
5
6
7
8public synchronized int capacity() {...}
public synchronized boolean isEmpty() {...}
public synchronized int indexOf(Object o, int index) {...}
public synchronized E get(int index) {...}
public synchronized E set(int index, E element) {...}
public synchronized E remove(int index) {...}
public void add(int index, E element) {...}
// 此处省略其他方法
Vector的迭代器实现及fail-fast机制同ArrayList。
Stack
Stack也是JDK早期版本基于Vector实现的栈。Stack继承自Vector，额外提供了以下用于栈的访问方法。1
2
3
4
5public E push(E item) {...}
public synchronized E pop() {...}
public synchronized E peek() {...}
public boolean empty() {...}
public synchronized int search(Object o) {...}
Stack基于Vector实现，因此Stack也是线程安全的。
总结
- ArrayList和Vector都是基于数组实现的线性表，支持以一定策略动态扩增。
- ArrayList和Vector的迭代器采用标准迭代器模式实现，遵循fast-fail机制。
- 在单线程环境中，由于不存在并发访问的问题，使用Stack或者Vector会降低访问效率。推荐使用ArrayList和后面会提到的LinkedList。
源码解读基于JDK-8