ArrayList扩容机制

首先看一下ArrayList的构造函数,ArrayList有3个构造函数。

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

private static final Object[] EMPTY_ELEMENTDATA = {};
//用于默认大小的空实例的共享空数组实例。将其与空的元素data区分开来,以知道在添加第一个元素时要填充多少。
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

public ArrayList() {
//设置数组没空
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
//创建initialCapacity大小的数组
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
//初始容量为0,则设置为空数组
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}

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;
}
}

在已无参的构造函数创建ArrayList时,初始化的是一个空数组,并没有设置数组的大小,只有当第一次添加的时候,才分配数组大小。
当调用add()函数时的逻辑。

1
2
3
4
5
6
7
public boolean add(E e) {
//添加之前先判断是否需要扩容
ensureCapacityInternal(size + 1); // Increments modCount!!
//添加元素
elementData[size++] = e;
return true;
}

扩容的具体逻辑

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}


private static final int DEFAULT_CAPACITY = 10;
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++;

// 判断传入的获取到的数组长度是否大于当前数组的长度,如果大于则扩容
// 当第一次添加时,数组默认值为0,这时才设置数组大小
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}



//要分配的数组的最大大小。
//一些vm在数组中保留一些头字。尝试分配较大的数组可能会导致OutOfMemory错误:请求的数组大小超过了VM限制
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
private void grow(int minCapacity) {

int oldCapacity = elementData.length;
//扩容的长度为原来数组的长度加原来数组长度的一半,也就是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);
}


private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0)
throw new OutOfMemoryError();
//如果添加后的长度大于默认最大长度,则设置成Integer.MAX_VALUE;否则,设置成默认最大长度
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}

-------------本文结束感谢您的阅读-------------