参考：
https://github.com/Snailclimb/JavaGuide/blob/master/docs/java/collection/ArrayList-Grow.md
一、初始化
0、内部组成
ArrayList内部有一个数组elementData来存放数据，还有一个整数size来记录实际的元素个数。
private transient Object[] elementData;
private int size;
重要的数据：
- DEFAULT_CAPACITY 默认容器大小
- DEFAULTCAPACITY_EMPTY_ELEMENTDATA 默认空数组，调用空参构造函数时elementData的默认值
/**
* 默认初始容量大小
*/
private static final int DEFAULT_CAPACITY = 10;
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
1、以无参数构造方法创建 ArrayList 时，实际上初始化赋值的是一个空数组。
源码：
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
2、使用带初始容量参数的构造函数时（用户自己指定容量），在参数合法的情况下（大于等于0），分配给指定大小的数组。
源码：
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {//初始容量大于0
//创建initialCapacity大小的数组
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {//初始容量等于0
//创建空数组
this.elementData = EMPTY_ELEMENTDATA;
} else {//初始容量小于0，抛出异常
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
二、扩容机制
1. add方法
/**
* 将指定的元素追加到此列表的末尾。
*/
public boolean add(E e) {
//添加元素之前，先调用ensureCapacityInternal方法
ensureCapacityInternal(size + 1); // Increments modCount!!
//这里看到ArrayList添加元素的实质就相当于为数组赋值
elementData[size++] = e;
return true;
}
当我们调用add方法时，add方法会先调用ensureCapacityInternal(size + 1)
2. ensureCapacityInternal方法(容量最小值为10)
add方法首先调用了ensureCapacityInternal(size + 1)
//得到最小扩容量
private void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
// 获取默认的容量和传入参数的较大值
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
当ArrayList是无参构造且第一次调用add时，minCapacity 会被赋予DEFAULT_CAPACITY的值也就是10；
3. ensureExplicitCapacity(判断是否需要扩容)
ensureCapacityInternal一定会调用ensureExplicitCapacity(minCapacity);
//判断是否需要扩容
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
//调用grow方法进行扩容，调用此方法代表已经开始扩容了
grow(minCapacity);
}
最少所需容量minCapacity 大于内置数组elementData的长度时，调用grow(minCapacity)扩容
4. grow(1.5倍扩容)扩容核心
ArrayList 每次扩容之后容量都会变为原来的 1.5 倍左右（oldCapacity为偶数就是1.5倍，否则是1.5倍左右）！ 奇偶不同，比如 ：10+10/2 = 15, 33+33/2=49。如果是奇数的话会丢掉小数.
/**
* 要分配的最大数组大小
*/
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
/**
* ArrayList扩容的核心方法。
*/
private void grow(int minCapacity) {
// oldCapacity为旧容量，newCapacity为新容量
int oldCapacity = elementData.length;
//将oldCapacity 右移一位，其效果相当于oldCapacity /2，
//我们知道位运算的速度远远快于整除运算，整句运算式的结果就是将新容量更新为旧容量的1.5倍，
int newCapacity = oldCapacity + (oldCapacity >> 1);
//然后检查新容量是否大于最小需要容量，若还是小于最小需要容量，那么就把最小需要容量当作数组的新容量，
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
// 如果新容量大于 MAX_ARRAY_SIZE,进入(执行) `hugeCapacity()` 方法来比较 minCapacity 和 MAX_ARRAY_SIZE，
//如果minCapacity大于最大容量，则新容量则为`Integer.MAX_VALUE`，否则，新容量大小则为 MAX_ARRAY_SIZE 即为 `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);
}
4. hugeCapacity
从上面 grow() 方法源码我们知道： 如果新容量大于 MAX_ARRAY_SIZE,进入(执行) hugeCapacity() 方法来比较 minCapacity 和 MAX_ARRAY_SIZE，如果minCapacity大于最大容量，则新容量则为Integer.MAX_VALUE，否则，新容量大小则为 MAX_ARRAY_SIZE 即为 Integer.MAX_VALUE - 8。
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
//对minCapacity和MAX_ARRAY_SIZE进行比较
//若minCapacity大，将Integer.MAX_VALUE作为新数组的大小
//若MAX_ARRAY_SIZE大，将MAX_ARRAY_SIZE作为新数组的大小
//MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
ArrayList扩容机制总结
ArrayList的底层是数组，有两个核心内置元素：
1、 elementData 是其底层数组，存放数据元素的地方。
2、 size是当前存放元素的个数。
初始化时，若使用无参构造，elementData 指向一个空数组；若使用带参构造，则elementData 数组的初始容量大小和参数相同。
使用add方法
1、无参构造并且未进行添加操作的elementData 数组容量变为10；
2、其它情况下，elementData 数组应该有的最小容量为minCapacity =size+1。如果minCapacity 大于Integer.MAX_VALUE，抛出溢出异常；如果minCapacity 小于等于elementData 当前容量，不用进行扩容操作；如果minCapacity 大于elementData 当前容量，elementData 的容量扩容为原来的1.5倍。如果扩容后的容量不大于minCapacity ，则elementData 的容量扩容为minCapacity ；如果如果扩容后的容量大于MAX_ARRAY_SIZE，当minCapacity > MAX_ARRAY_SIZE时elementData 的容量扩容为Integer.MAX_VALUE，当minCapacity <MAX_ARRAY_SIZE时elementData 的容量扩容为MAX_ARRAY_SIZE。
网友评论