【java容器的刻意练习】【三】ArrayList动态扩容
上一篇我们知道了,ArrayList核心是个数组。那么,心中肯定有个疑问:ArrayList是怎么实现数组的扩容的?
先给出结论。
- 每添加一个元素,检查数组剩余空间是否足够
- 如果第一次添加元素,就创建容量为10的数组
- 如果数组剩余空间不足,触发扩容
- 每次扩容现有容量的50%
- 把旧数组内容拷贝到新数组
- 添加新元素
这一篇我们来看看,怎么得出上面这个结论的。
先对arrayList添加一个元素。
arrayList.add(123);
调用如下方法:
public boolean add(E e) {
// 增加数组修改的次数
modCount++;
// 调用add私有方法进行元素添加
add(e, elementData, size);
return true;
}
这里的modCount是啥?跳过去看看,原来这个是继承自AbstractList中的字段,表示数组修改的次数,数组每修改一次,就要增加modCount。
还有个size又是啥?跳过去看看,原来是数组包含的元素个数。
size的注释
接着调用了另外一个add私有方法:
private void add(E e, Object[] elementData, int s) {
// 如果数组已满
if (s == elementData.length)
// 当然是扩容啦
elementData = grow();
// 还有空间或者扩容完毕,就添加元素
elementData[s] = e;
// 增加数组元素个数
size = s + 1;
}
终于找到扩容的方法,原来叫 grow
。赶紧跳过去看看。
private Object[] grow() {
return grow(size + 1);
}
呃,又封了一层,传了新增元素后的个数当参数进去。
/**
* Increases the capacity to ensure that it can hold at least the
* number of elements specified by the minimum capacity argument.
*
* @param minCapacity the desired minimum capacity
* @throws OutOfMemoryError if minCapacity is less than zero
*/
private Object[] grow(int minCapacity) {
int oldCapacity = elementData.length;
if (oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
int newCapacity = ArraysSupport.newLength(oldCapacity,
minCapacity - oldCapacity, /* minimum growth */
oldCapacity >> 1 /* preferred growth */);
return elementData = Arrays.copyOf(elementData, newCapacity);
} else {
return elementData = new Object[Math.max(DEFAULT_CAPACITY, minCapacity)];
}
}
作者的注释说,这个扩容函数保证至少扩容到传进来的最小容量。
所以,minCapacity就是扩容要求的最小容量。那么最大是多少呢?
好像这个最大容量的计算挺复杂,那我们先看这个if-else。
如果数组已经有元素,那么通过ArraysSupport.newLength
计算需要扩容的大小,通过Arrays.copyOf
创建一个新的大数组,把旧的小数组拷贝过去。如果没有新元素,就创建大小为10的数组。
噢!原来ArrayList自动扩容就这么回事!
知道了原理后,我们就深入想想,如果频繁的扩容,肯定是不行的。但是,一下子创建很大的数组,又非常浪费。那么,应该怎么扩容才合理呢?
我们看看如何计算每次扩容最大容量的。
int newCapacity = ArraysSupport.newLength(oldCapacity,
minCapacity - oldCapacity, /* minimum growth */
oldCapacity >> 1 /* preferred growth */);
- oldCapacity 是扩容前的数组大小,这里我们假设是10。
- minCapacity - oldCapacity是最小需要扩容的大小。如果只添加一个元素,那么就是1。
- oldCapacity >>1右移一位就是除以2,就是原来数组的50%。假设例子中10的一半就是5。
那么,这个ArraysSupport.newLength
是什么函数呢?跳过去看看。
public static int newLength(int oldLength, int minGrowth, int prefGrowth) {
// assert oldLength >= 0
// assert minGrowth > 0
// 最小容量与预计增长容量取较大那个,然后加上原来数组大小
int newLength = Math.max(minGrowth, prefGrowth) + oldLength;
if (newLength - MAX_ARRAY_LENGTH <= 0) {
return newLength;
}
return hugeLength(oldLength, minGrowth);
}
原来,扩容后的大小是原来的1.5倍。假设例子中10的1.5倍就是15。
当然,代码中还用hugeLength
函数考虑到扩容的上限,是Integer.MAX_VALUE即是0x7fffffff,以及超出上限会抛异常OutOfMemoryError,如下图。
到这里,我们终于知道了ArrayList自动扩容的逻辑:
ArrayList扩容示意图
- 每添加一个元素,检查数组剩余空间是否足够
- 如果第一次添加元素,就创建容量为10的数组
- 如果数组剩余空间不足,触发扩容
- 每次扩容现有容量的50%
- 把旧数组内容拷贝到新数组
- 添加新元素
到这里还没完,我们有一个额外的问题:怎么创建ArrayList最合理?
- 如果少于10个,直接创建个空的就行。
- 如果确定数组的大概数量,创建时候直接传入最大的量级,或者在合适时机提前调用
ensureCapacity
扩容。这样可以减少每次只扩容50%多次拷贝问题。 - 当确认数据已经添加完毕,如有必要,可以调用
trimToSize
回收多余的空间,这样可以节省内存空间。