6⌥codecode6⌥codecodeArrayList扩容机制
ArrayList扩容机制
●先来看Add方法
Java
运行代码复制代码
1
2
3
4
5
6
7
8
9
10
/**
*将指定的元素追加到此列表的末尾
*/
public boolean add(E e) {
//添加元素之前，先调用ensureCapacityInternal方法
ensureCapacityInternal(size + 1); // Increments modCount!!（增量modCount）
//这里看到ArrayList添加元素的实质就相当于为数组赋值
elementData[size++] = e;
return true;
}
●再来看看ensureCapacityInternal（）方法，可以看到add()方法首先调用了ensureCapacityInternal（size+1）
Java
运行代码复制代码
1
2
3
4
5
6
7
8
//得到最小扩容量
private void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
//获取默认的容量和传入参数的较大值（第一次的较大值是DEFAULT_CAPACITY=10，minCapacity=1）
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
当要add进第一个元素时，minCapacity为1，在Math.max()方法比较后，minCapacity为10
●ensureExplicitCapacity()方法
Java
运行代码复制代码
1
2
3
4
5
6
7
8
//判断是否需要扩容
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
//调用grow()方法进行扩容，调用此方法代表已经开始扩容了
grow(minCapacity);
}
我们来仔细分析一下
1当我们要add进第一个元素到ArrayList时，elementData.length为0（因为还是一个空的list，里面还没有数据，所以没有进行扩容，默认扩容10），因为执行了ensureCapacityInternal()方法，所以minCapacity此时为10。此时，minCapacity - elemetData.length > 0（minCapacity=10,elemetData.length=0）成立，所以会进入==grow(minCapacity)==方法。
2当add第2个元素时，minCapacity为2，此时elementData.length(容量)在添加第一个元素后扩容成10了。此时，minCapacity - elementData.length > 0不成立，所以不会进入（执行）==grow(minCapacity)==方法。
3添加第3、4…到第10个元素时，依然不会执行==grow()==方法，数组容量都为10。知道添加第11个元素，minCapacity(为11)比elementData.length(为10)要大。进行grow方法进行扩容
4grow方法
Java
运行代码复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
private void grow(int minCapacity) {
// oldCapacity为旧容量，newCapacity为新容量
int oldCapacity = elementData.length;//（0,10,15）
//将oldCapacity右移一位，其效果相当于oldCapacity/2;
// 我们知道位运算的速度远远快于整除运算，整句运算式的结果就是将新容量更新为旧容量的1.5倍
int newCapacity = oldCapacity + (oldCapacity >> 1);
// 然后检查新容量是否大于最小需要容量，若还是小于最小需要容量，那么久把最小需要容量当作数组的新容量
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
//判断新容量是否大于集合的最大容量（一般大不了）
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// 给elementData从新赋值（10,15）
elementData = Arrays.copyOf(elementData, newCapacity);
}
int newCapacity = oldCapacity + (oldCapacity >> 1),所以 ArrayList 每次扩容之后容量都会变为原来的 1.5 倍！
“>>”（移位运算符）：>>1 右移一位相当于除2，右移n位相当于除以 2 的 n 次方。这里 oldCapacity 明显右移了1位所以相当于oldCapacity /2。对于大数据的2进制运算,位移运算符比那些普通运算符的运算要快很多,因为程序仅仅移动一下而已,不去计算,这样提高了效率,节省了资源
通过例子探究一下grow()方法
●当add第一个元素时，oldCapacity为0，经比较后第一个if判断成立，newCapacity = minCapacity(为10)。但是第二个if判断不会成立，即newCapacity不比MAX_ARRAY_SIZE大，则不会进入hugeCapacity方法。数组容量为10，add方法中return true,size增为1。
●当add第11个元素进入grow方法时，newCapacity为15，比minCapacity(为11)大，第一个if判断不成立。新容量没有大于数组最大size,不会进入hugeCapacity方法。数组容量扩为15，add方法中rerurn,true,size增为11。
●以此类推…这里补充一点比较重要，但是容易被忽视掉的知识点：
●java中的length属性是针对数组说的，比如说你声明了一个数组，想知道这个数组的长度则用到了length这个属性。
●java中的length() 方法是针对字符串说的，如果想看这个字符串的长度则用到 length() 这个方法。
●java中的size() 方法是针对泛型集合说的，如果想看这个泛型有多少元素，就调用此方法类查看！
