ArrayList扩容分析

ArrayList可以实现容量的自适应的增加(As elements are added to an ArrayList,
its capacity grows automatically)。通过JDK1.8中ArrayList的源码来分析:

ArrayList的相关定义

ArrayList底层采用Object类型的数组实现。

首先,定义默认初始容量,为10

1
private static final int DEFAULT_CAPACITY = 10;

再有,定义用于空实例的空数组实例

1
private static final Object[] EMPTY_ELEMENTDATA = {};

再有,定义空数组实例,用于默认大小的空实例

1
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

再有,定义了一个未被序列化的数组elementData,用来存储ArrayList对象列表

1
2
3
4
/**
* The capacity of the ArrayList is the length of this array buffer.
*/
transient Object[] elementData;

再有,定义了ArrayList的size变量

1
2
3
4
/**
* The size of the ArrayList (the number of elements it contains).
*/
private int size;

为了实现ArrayList的自动扩容机制,java引进了capacity和size概念,以区别数组的length。capacity是底层数组的长度(length),size是存储的列表对象的数量,被设置为private的。

ArrayList的初始化

ArrayList有三种方式来初始化,构造方法源码如下:

1.用指定的初始容量构造一个空列表

1
2
3
4
5
6
7
8
9
10
11
12
13
/**
* Constructs an empty list with the specified initial capacity.
*/
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);
}
}

2.使用初始容量10构造一个空列表(无参数构造)

1
2
3
4
5
6
/**
* Constructs an empty list with an initial capacity of ten.
*/
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

3.构造包含指定collection元素的列表,这些元素利用该集合的迭代器按顺序返回

如果指定的集合为null,throws NullPointerException。

1
2
3
4
5
6
7
8
9
10
11
12
public ArrayList(Collection<? extends E> c) {

elementData = c.toArray();//用Collection初始化数组elementData
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;
}
}

ArrayList扩容

以无参数构造为例,初始数组容量为10。当真正对数组进行添加时,才真正分配容量。即向数组中添加第一个元素时,数组容量扩为10。

1.以add(E e)方法为入口分析

1
2
3
4
5
6
public boolean add(E e) {
//添加元素之前,先调用ensureCapacityInternal方法
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;//添加对象时,自增size
return true;
}

2.进入到ensureCapacityInternal方法

ensureCapacityInternal(“确保内部容量”)。

1
2
3
4
5
6
7
8
9
10
private void ensureCapacityInternal(int minCapacity) {
//先判断数组是否为空
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
//如果数组为空,将DEFAULT_CAPACITY(为10)和minCapacity中较大的一个赋值给minCapacity
//则minCapaciy至少为10
}
ensureExplicitCapacity(minCapacity);
//执行ensureExplicitCapacity方法
}

当空列表add()第1个元素时,调试可知:原本minCapacity为1,在Math.max()方法比较后,minCapacity为10。

但当add()第2个元素时,数组非空,直接进入ensureExplicitCapacity(minCapacity)(此时minCapacity为2)。

3.进入ensureExplicitCapacity方法

无论数组是否为空,都会进入ensureExplicitCapacity方法。

1
2
3
4
5
6
7
private void ensureExplicitCapacity(int minCapacity) {
modCount++;//定义于ArrayList的父类AbstractList,用于存储结构修改次数
// overflow-conscious code
if (minCapacity - elementData.length > 0)
//如果数组的长度(elementData.length)小于最小需要的容量(minCapacity),就扩容
grow(minCapacity);
}

当要add第1个元素时,这时elementData.length(为0,因为此时还是空列表)是要比minCapacity(为10)小的,会进入grow(minCapacity)方法(minCapacity为10)。

当add第2个元素时,调试可知:minCapacity为2,此时elementData.length(即是容量)在添加第一个元素后扩容成10了,比minCapacity大,不会去执行grow方法 。数组容量仍为10。

所以当添加第3、4···到第10个元素时,依然不会执行grow方法,数组容量都为10。

直到添加第11个元素,minCapacity(为11)比elementData.length(为10)要大。进入grow方法进行扩容。

4.进入grow方法进行扩容

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
//用来分配数组的size最大值
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
//右移一位相当于原数除以2,位运算的计算方式更快
//所以新容量扩大为原容量的1.5倍
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
//从minCapacity和这个newCapacity中取较大值作为扩容后的新数组长度(新容量)。
//这主要是针对添加第1个元素。1.5倍oldCapacity为0,所以newCapacity为最小容量10
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
//如果新容量大于数组的最大size,进入hugeCapacity方法
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
//最后,将原来数组的数据复制到新的数组中。

}

当add第1个元素时,oldCapacity为0,经比较后第一个if判断成立,newCapacity = minCapacity(为10)。但是第二个if判断不会成立,即newCapacity 不比 MAX_ARRAY_SIZE大,则不会进入hugeCapacity方法。数组容量为10,add方法中return true,size增为1。

当add第11个元素进入grow方法时,newCapacity为15,比minCapacity(为11)大,第一个if判断不成立。新容量没有大于数组最大size,不会进入hugeCapacity方法。数组容量扩为15,add方法中return true,size增为11。

以此类推······

5.如果新容量大于MAX_ARRAY_SIZE,进入hugeCapacity方法

1
2
3
4
5
6
7
8
9
10
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
//对minCapacity和MAX_ARRAY_SIZE进行比较
//若minCapacity大,将Integer.MAX_VALUE作为新数组的大小
//若MAX_ARRAY_SIZE大,将MAX_ARRAY_SIZE作为新数组的大小
}

所以,像ArrayList添加对象时,在确定好新数组的大小后,会调用Arrays.copyOf()方法,以适当长度(newCapacity)新建一个原数组的拷贝,并修改原数组,指向这个新建数组。java垃圾回收机制会自动回收原数组。这样会消耗一定的资源。

因此,在初始化ArrayList时,最好可以估算一个初始大小。

7.最好在add大量元素之前用ensureCapacity方法,以减少增量从新分配的次数。 源码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
* <p>An application can increase the capacity of an <tt>ArrayList</tt> instance
* before adding a large number of elements using the <tt>ensureCapacity</tt>
* operation. This may reduce the amount of incremental reallocation.
*/

public void ensureCapacity(int minCapacity) {
int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
// any size if not default element table
? 0
// larger than default for default empty table. It's already
// supposed to be at default size.
: DEFAULT_CAPACITY;

if (minCapacity > minExpand) {
ensureExplicitCapacity(minCapacity);
}
}

参考:

ArrayList自动扩容解析