ArrayList扩容机制
¶ArrayList的构造函数
¶默认参数
//默认初始容量大小
private static final int DEFAULT_CAPACITY = 10;
//指定该ArrayList数组容量为零时返回该对象数组
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
¶默认构造函数
以无参数构造方法创建 ArrayList 时,实际上初始化赋值的是一个空数组。当真正对数组进行添加元素操作时,才真正分配容量。即向数组中添加第一个元素时,数组容量扩为10。
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
¶ArrayList的扩容机制
¶1.add()
方法
public boolean add(E e) {
//添加元素之前,先调用ensureCapacityInternal方法
ensureCapacityInternal(size + 1); // Increments modCount!!
//这里看到ArrayList添加元素的实质就相当于为数组赋值
elementData[size++] = e;
return true;
}
注意 :JDK11 移除了
ensureCapacityInternal()
和ensureExplicitCapacity()
方法
¶2. ensureCapacityInternal()
方法
add
方法 首先调用了ensureCapacityInternal(size + 1)
//进行容量检查,决定扩容的想要的最小容量
private void ensureCapacityInternal(int minCapacity) {
//判断当前数组是否是默认构造方法生成的空数组,如果是的话minCapacity=10,反之则根据原来的值传入下一个方法去完成下一步的扩容判断
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
// 获取默认的容量和传入参数的较大值
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
- 当add进第1个元素时,minCapacity的值为
size+1
,即为1,在Math.max()
方法比较后,minCapacity 为10。 - 当add进第2个元素时,minCapacity的值为size+1=2,当前数组非空,不会进入if判断,保留为2。
¶3. ensureExplicitCapacity()
方法
如果调用 ensureCapacityInternal()
方法就一定会进过(执行)这个方法,下面我们来研究一下这个方法的源码!
//判断是否需要扩容
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
//调用grow方法进行扩容
grow(minCapacity);
}
- 当add第1个元素到 ArrayList时,minCapacity=size+1=1经过ensureCapacityInternal()方法后
minCapacity=10
,elementData.length=0
(因为还是一个空的 list 。此时,minCapacity - elementData.length > 0
成立,所以会进入grow(minCapacity)
方法进行扩容。 - 当add第2个元素时,
minCapacity=size+1=2
,由于在添加第一个元素时进行了扩容,elementData.length=10
。此时,minCapacity - elementData.length < 0
,所以不会进入grow(minCapacity)
方法。 - 一直到add第10个元素时,此时
minCapacity=size+1=10
,elementData.length=10
,if条件不成立,依然不会执行grow方法,数组容量elementData.length都为10。 - 直到添加第11个元素,
minCapacity=size+1=11
,elementData.length=10
,minCapacity - elementData.length > 0
成立,所以会再次进入grow(minCapacity)
方法进行扩容。
¶4. grow()
方法
//要分配的最大数组大小
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
private void grow(int minCapacity) {
// oldCapacity为旧容量,newCapacity为新容量,新容量更新为旧容量的1.5倍
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
//然后检查新容量是否大于最小需要容量,若还是小于最小需要容量,那么就把最小需要容量当作数组的新容量,
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
//如果新容量大于数组最大容量值,进入hugeCapacity()方法来比较 minCapacity 和 MAX_ARRAY_SIZE,
//如果minCapacity大于数组最大容量,则使用整数最大值作为新容量,否则使用数组最大容量作为新容量,即为Integer.MAX_VALUE - 8。
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}
int newCapacity = oldCapacity + (oldCapacity >> 1),所以 ArrayList 每次扩容之后容量都会变为原来的 1.5 倍左右(oldCapacity为偶数就是1.5倍,否则是1.5倍左右)! 奇偶不同,比如 :10+10/2 = 15, 33+33/2=49。如果是奇数的话会丢掉小数.
- 当add第1个元素时,
oldCapacity=0
,minCapacity=10
,经比较后第一个if判断成立,newCapacity = minCapacity=10
。但是第二个if判断不成立。数组容量为10,add方法中 return true,size增为1。 - 当add第11个元素进入grow方法时,
oldCapacity=10
,minCapacity=11
,所以newCapacity=1.5oldCapacity=15
。第一个if判断不成立,两个if判断都不成立。数组容量扩为15,add方法中return true,size增为11。 - 以此类推······
¶5. hugeCapacity()
方法。
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
//对minCapacity和MAX_ARRAY_SIZE进行比较
//若minCapacity大,将Integer.MAX_VALUE作为新数组的大小
//若MAX_ARRAY_SIZE大,将MAX_ARRAY_SIZE作为新数组的大小
//MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
¶System.arraycopy()
和 Arrays.copyOf()
方法
发现 ArrayList 中大量调用了这两个方法。比如上面的扩容操作以及add(int index, E element)
、toArray()
等方法中都用到了该方法!
¶两者联系和区别
联系:
看两者源代码可以发现 Arrays.copyOf()
内部实际调用了 System.arraycopy()
方法。
区别:
Arrays.copyOf()
在数组拷贝过程中创建新的数组,将原有数据拷贝到新数组中去,System.arraycopy()
仅拷贝数组的内容,不会创建新数组。
¶ensureCapacity()
方法
ArrayList 源码中有一个 ensureCapacity
方法不知道大家注意到没有,这个方法 ArrayList 内部没有被调用过,所以很显然是提供给用户调用的,那么这个方法有什么作用呢?
/**
如有必要,增加此 ArrayList 实例的容量,以确保它至少可以容纳由minimum capacity参数指定的元素数。
*
* @param minCapacity 所需的最小容量
*/
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);
}
}
如果使用 add方法增加大量元素,在增加之前使用 ensureCapacity
方法,可以提高ArrayList初始化速度
我们通过下面的代码实际测试以下这个方法的效果:
public class EnsureCapacityTest {
public static void main(String[] args) {
ArrayList<Object> list = new ArrayList<Object>();
final int N = 10000000;
long startTime = System.currentTimeMillis();
for (int i = 0; i < N; i++) {
list.add(i);
}
long endTime = System.currentTimeMillis();
System.out.println("使用ensureCapacity方法前:"+(endTime - startTime));
}
}
运行结果:
使用ensureCapacity方法前:2158
public class EnsureCapacityTest {
public static void main(String[] args) {
ArrayList<Object> list = new ArrayList<Object>();
final int N = 10000000;
list = new ArrayList<Object>();
long startTime1 = System.currentTimeMillis();
list.ensureCapacity(N);
for (int i = 0; i < N; i++) {
list.add(i);
}
long endTime1 = System.currentTimeMillis();
System.out.println("使用ensureCapacity方法后:"+(endTime1 - startTime1));
}
}
运行结果:
使用ensureCapacity方法前:1773
通过运行结果,我们可以看出向 ArrayList 添加大量元素之前最好先使用ensureCapacity
方法,以减少增量重新分配的次数。