简介
说明
本文介绍Java的ArrayList是如何进行扩容的。即：扩容的机制。
重要大小
| 类 | 初始大小 | 扩容倍数 | 底层实现 | 是否线程安全 | 同步方式 |
| ArrayList | 10 | 1.5倍 | Object数组 | 线程不安全 | 无 |
| Vector | 10 | 2倍 | Object数组 | 线程安全 | synchronized |
ArrayList在添加元素时实际容量如果不够了，就会扩容，没有HashMap那种加载因子的概念。（也可以理解为加载因子是1）。
下边介绍ArrayList的扩容机制。
扩容机制
1. new一个ArrayList对象
直接new 一个ArrayList对象时（未指定初始容量大小）是一个空的数组，容量大小为零。
public ArrayList() {
// DEFAULTCAPACITY_EMPTY_ELEMENTDATA 变量为一个空的数组
// private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
2. 调用add()方法
当第一次调用ArrayList对象的add方法时，分配容量大小
public boolean add(E e) {
// size为ArrayList的实际数量大小而非容量大小，若未指定容量构建ArrayList对象，size为0
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
private void ensureCapacityInternal(int minCapacity) {
// 如果为空数组，最小需要容量为默认容量DEFAULT_CAPACITY 也就是10
// private static final int DEFAULT_CAPACITY = 10;
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
// 调用扩容方法
ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
//protected transient int modCount = 0;
modCount++;
// 如果需要的最小容量大于此时的容量，调用真正的扩容方法
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
3. 扩容
private void grow(int minCapacity) {
// transient Object[] elementData;
// overflow-conscious code
int oldCapacity = elementData.length;
// 第一次扩容1.5倍
int newCapacity = oldCapacity + (oldCapacity >> 1);
// 还是比需要的容量小就把需要的容量作为新的容量值
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
// 这里主要防止1.5倍扩容导致新容量值超过数组最大容量。
// 如果新的容量比数组最大容量还大，则比较需求容量和数组最大容量
// 如果需求容量比数组最大容量大就取整数最大值，反之取数组最大容量
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);
}
/**
* The maximum size of array to allocate.
* Some VMs reserve some header words in an array.
* Attempts to allocate larger arrays may result in
* OutOfMemoryError: Requested array size exceeds VM limit
*/
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
请先 ！