08 arrayList扩容时扩容多少

vvEcho 2024-01-24 14:52:22
Categories: Tags:

相关源码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
//默认容量大小
private static final int DEFAULT_CAPACITY = 10;

//扩容 当前数据长度+1 作为最小容量
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
// 计算容量 如果原始为空数组,则取默认容量10和+1后的容量 取二者大的
private static int calculateCapacity(Object[] elementData, int minCapacity) {
// 如果为空则返回默认容量的空数组对象
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
// 否则返回+1后容量
return minCapacity;
}
// 计算显示容量 最小容量大于当前数据长度 表示需要扩容了
// 即如果当前数据长度+1大于10 则扩容
private void ensureExplicitCapacity(int minCapacity) {
modCount++;

// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
//扩容右位移1位 10>>1 为5扩容后是15 扩容为之前的1.5倍
//最大为MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8
//public static final int MAX_VALUE = 2^31-1;
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
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);
}
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}

总结,arrayList底层是一个数组,扩容的话底层和数组的扩容方式是一样的;
第一步:判断是否超过初始容量10,超过则先创建一个新的数组,新数组的长度扩容到之前的1.5倍 10->15 另外扩容的时候如果是批量添加的话,会判断扩容1.5倍和批量添加的数量,取两者中的较大值
第二步:使用copyOf方法将原数组拷贝到新数组中,并返回新数组
第三步:扩容完成后将新的数据加到扩容的数组里面去;