Java容器源码分析之ArrayList

ArrayList简介

ArrayList是一个使用数组实现的容器,与普通的数组相比,它能动态的扩容,ArrayList继承自AbstractList,实现了List、RandomAccess、Cloneable、Serializable接口。

ArrayList UML图如下:

ArrayList UML图

ArrayList不是一个线程安全的容器。

ArrayList源码分析

我们主要分析ArrayList的构造方法、add方法、get方法以及扩容方法

构造方法

ArrayList有三个构造方法,分别如下:

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
//构造一个指定长度的ArrayList对象,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);
}
}

//构造一个默认长度为0的ArrayList对象,JDK6以前默认长度为10
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

//从已有的一个容器创建一个ArrayList对象
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;
}
}

对于第三个构造方法,第22行注释,这是Java在jdk6时代的一个bug,官方文档在此;造成这个bug的原因是:当元素存在父类对象时,父类实例的具体类型,实际上是取决于在new时,我们所使用的子类类型。当不加以23行检测代码时,可能会造成将一个父类存进子类数组中,导致报错。

add方法

ArrayList中有两个add方法,如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
//在尾部添加一个元素
public boolean add(E e) {
//确定容量是否能够添加一个元素
ensureCapacityInternal(size + 1); // Increments modCount!!
//将元素放到size位置
elementData[size++] = e;
return true;
}

//在指定位置添加一个元素
public void add(int index, E element) {
//检查index是否溢出
rangeCheckForAdd(index);
//确定容量是否能够添加一个元素
ensureCapacityInternal(size + 1); // Increments modCount!!
//通过System.arraycopy将index+1到size位置的元素向后移一位
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
//设置index位置的元素
elementData[index] = element;
size++;
}

在两个add方法中都有调用检查容器空间是否足够的方法,下面看看ensureCapacityInternal是如何实现的;

ensureCapacityInternal:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

//返回当前长度和ArrayList默认长度中大的一个
private static int calculateCapacity(Object[] elementData, int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}

private void ensureExplicitCapacity(int minCapacity) {
//计数检查次数
modCount++;

//当需要长度已经大于此时ArrayList内部数组长度时,开始扩容
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}

具体的扩容代码,我们将在后面分析,我们先来看下get是怎么实现的

get方法

1
2
3
4
5
6
7
8
9
10
public E get(int index) {
rangeCheck(index);

return elementData(index);
}

private void rangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

get方法比较简单,首先检测index是否溢出,然后返回数组中第index个元素。

扩容方法

我们在分析add方法的时候,就已经知道ArrayList的扩容方法是grow()方法了,我们直接来看grow()方法源码

grow:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
//newCapacity = oldCapacity + 0.5 * oldCapacity
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
//如果新长度值还小于需要长度,那么新长度设置为需要长度
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
//当新长度大于Integer.MAX_VALUE - 8时,做一次检测
newCapacity = hugeCapacity(minCapacity);
//将旧数组中元素复制进新数组
elementData = Arrays.copyOf(elementData, newCapacity);
}

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

总结

ArrayList在jdk6以前,默认初始大小为10,jdk6以后采取了延迟为数组分配空间的策略默认初始大小为0,在第一次add元素的时候,会检测数组大小并初始化为默认大小10。

ArrayList扩容触发条件是当数组长度不足以容纳添加一个元素时扩容;扩容大小为原大小的1.5倍,具体算法为int newCapacity = oldCapacity + (oldCapacity >> 1)

本文首发于我在万达摆地摊's blog,转载请注明来源