1. ArrayList扩容步骤
主要分两步:
- 扩容: 将数组复制到另一个长度更大的数组中
- 添加元素: 把新元素添加到扩容以后的数组中
2. 扩容源码解析
相关参数
private static final long serialVersionUID = 8683452581122892189L;
/**
* 默认初始容量大小
*/
private static final int DEFAULT_CAPACITY = 10;
/**
* 空数组(用于空实例)。
*/
private static final Object[] EMPTY_ELEMENTDATA = {};
//用于默认大小空实例的共享空数组实例。
//我们把它从EMPTY_ELEMENTDATA数组中区分出来,以知道在添加第一个元素时容量需要增加多少。
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
/**
* 保存ArrayList数据的数组
*/
transient Object[] elementData; // non-private to simplify nested class access
/**
* ArrayList 所包含的元素个数
*/
private int size;
构造方法
/**
* 带初始容量参数的构造函数(用户可以在创建ArrayList对象时自己指定集合的初始大小)
*/
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
//如果传入的参数大于0,创建initialCapacity大小的数组
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
//如果传入的参数等于0,创建空数组
this.elementData = EMPTY_ELEMENTDATA;
} else {
//其他情况,抛出异常
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
/**
*默认无参构造函数
*DEFAULTCAPACITY_EMPTY_ELEMENTDATA 为0.初始化为10,
*也就是说初始其实是空数组 当添加第一个元素的时候数组容量才变成10
*/
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
扩容的方法: add(E e)
和 addALL(Collection<? extends E> c)
主要看下add(E e)
public boolean add(E e) {
ensureCapacityInternal(size + 1); // 第一步: 增加数组长度
elementData[size++] = e; // 第二步: 添加元素到数组
return true;
}
调用ensureCapacityInternal
得到最小扩容量,这个方法会判断ArrayLists是否初始化,如果未初始化,则将数组大小初始化为默认大小DEFAULT_CAPACITY
,即 10 ,否则容量设置为传入的minCapacity
private void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
// 获取“默认的容量”和“传入参数”两者之间的最大值
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
最后调用ensureExplicitCapacity
方法,先判断是否需要扩容,如果需要扩容则调用grow()
方法进行扩容
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
grow(int minCapacity)
是扩容的核心方法
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length; // oldCapacity为旧容量,newCapacity为新容量
int newCapacity = oldCapacity + (oldCapacity >> 1); // 新容量更新为旧容量的 1.5 倍
//然后检查新容量是否大于最小需要容量,
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
//再检查新容量是否超出了ArrayList所定义的最大容量,
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);
}
3. ArrayList扩容机制总结
初始化一个ArrayList集合还没有添加元素时,其实它是个空数组,只有当我们添加第一个元素时,内部会返回最小容量10,也就是说ArrayList初始化容量为10。当最小容量大于当前数组的长度时,便开始可以扩容了,ArrayList扩容的真正计算是在一个grow()
方法里面,新数组大小是旧数组的1.5倍,如果扩容后的新数组大小还是小于最小容量,那新数组的大小就是最小容量的大小,后面会调用一个Arrays.copyof()
方法,这个方法是真正实现扩容的步骤。