上一篇我们知道了，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自动扩容的逻辑：
- 每添加一个元素，检查数组剩余空间是否足够
- 如果第一次添加元素，就创建容量为10的数组
- 如果数组剩余空间不足，触发扩容
- 每次扩容现有容量的50%
- 把旧数组内容拷贝到新数组
- 添加新元素
ArrayList扩容示意图
到这里还没完，我们有一个额外的问题：怎么创建ArrayList最合理？
- 如果少于10个，直接创建个空的就行。
- 如果确定数组的大概数量，创建时候直接传入最大的量级，或者在合适时机提前调用
ensureCapacity扩容。这样可以减少每次只扩容50%多次拷贝问题。 - 当确认数据已经添加完毕，如有必要，可以调用
trimToSize回收多余的空间，这样可以节省内存空间。
网友评论