0%

ArrayList 扩容机制源码分析

本篇通过阅读JDK1.8源码,了解ArrayList是如何进行自动扩容的。

初始化

无参构造方法创建ArrayList()
1
ArrayList arrayList = new ArrayList();

源码:

1
2
3
4
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

将默认的大小为0的object数组赋值给elementData实现初始化。

指定容量的够着方法创建ArrayList()
1
ArrayList arrayList = new ArrayList(14);

源码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
private static final Object[] EMPTY_ELEMENTDATA = {};
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
//指定容量大于0,则创建一个指定容量的Object数组
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
//指定容量等于0,则将他指向EMPTY_ELEMENTDATA的size为0的空Object数组引用
/**
*另外注意:EMPTY_ELEMENTDATA和DEFAULTCAPACITY_EMPTY_ELEMENTDATA都是空Object数组
*但是其含义不一样,在后面自动扩容的时候会讲到
**/
this.elementData = EMPTY_ELEMENTDATA;
} else {
//其他情况抛出异常
throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity);
}
}

自动扩容

当添加元素时,会根据情况进行是否扩容。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public boolean add(E e) {
//ensureCapacityInternal:翻译:确保内部容量
//size == elementData.length 即当前数组大小
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}

public boolean addAll(Collection<? extends E> c) {
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(size + numNew); // Increments modCount
System.arraycopy(a, 0, elementData, size, numNew);
size += numNew;
return numNew != 0;
}

再看 ensureCapacityInternal 是如何确保内部容量的

1
2
3
4
5
6
//minCapacity 数组需要的最小容量,(原容量+添加元素个数)
private void ensureCapacityInternal(int minCapacity) {
//ensureExplicitCapacity:翻译:确保明确的容量
//确保明确的容量,那 calculateCapacity(计算容量) 计算的就是明确的容量值咯
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

calculateCapacity 如何计算容量

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
private static final int DEFAULT_CAPACITY = 10;//默认扩容容量

private static int calculateCapacity(Object[] elementData, int minCapacity) {
/**
在添加元素方法到这里的时候,如果是 new ArrayList() 创建的对象,
就会进入到if中返回的,DEFAULT_CAPACITY(10) 将最小所需容量设置为 10
其他情况不设默认值,直接返回最小所需容量
还有一个是如果是new ArrayList(0) 创建的,也会直接返回 minCapacity,而不是给默认扩容容量
因为此时elementData指向的是EMPTY_ELEMENTDATA
*/
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}

接下来看 ensureExplicitCapacity :

1
2
3
4
5
6
7
private void ensureExplicitCapacity(int minCapacity) {
modCount++;

// 最少所需容量 > 原来容量 才进行扩容
if (minCapacity - elementData.length > 0)
grow(minCapacity); //扩容的方法
}

扩容方法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
private void grow(int minCapacity) {
// overflow-conscious code
//原来的容量
int oldCapacity = elementData.length;
//新的容量 (原来的容量+原来容量的一半[拟扩容的容量])
int newCapacity = oldCapacity + (oldCapacity >> 1);
//新的容量 < 最少所需容量
if (newCapacity - minCapacity < 0)
newCapacity = 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);
}

重新计算大容量:

1
2
3
4
5
6
7
8
9
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
//大于数组最大容量则用Integer.MAX_VALUE
//否则用数组最大容量作为新的容量值。
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}

总结

  • ArrayList用默认无参构造方法创建时,在第一次添加元素时将数组大小扩展至默认容量(10)。

  • 通常每次扩展容量,扩展至原来容量的1.5倍。

  • 所需最少容量 > 原来容量的1.5倍时, 则扩展至所需最少容量。

  • 拟扩容至的容量 > 数组的最大大小时,进行一次大容量扩容

    • 所需最少容量 > 数组最大大小:扩容至Integer的最大值
    • 所需最少容量 < 数组最大大小:扩容至数组最大大小(Integer.Max -8)