ArrayList 扩容机制源码分析
本篇通过阅读JDK1.8源码,了解ArrayList是如何进行自动扩容的。
初始化
无参构造方法创建ArrayList()
ArrayList arrayList = new ArrayList();
源码:
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
将默认的大小为0的object数组
赋值给elementData
实现初始化。
指定容量的够着方法创建ArrayList()
ArrayList arrayList = new ArrayList(14);
源码:
private static final Object[] EMPTY_ELEMENTDATA = {};
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
//指定容量大于0,则创建一个指定容量的Object数组
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
//指定容量等于0,则将他指向EMPTY_ELEMENTDATA的size为0的空Object数组引用
/**
*另外注意:EMPTY_ELEMENTDATA和DEFAULTCAPACITY_EMPTY_ELEMENTDATA都是空Object数组
*但是其含义不一样,在后面自动扩容的时候会讲到
**/
this.elementData = EMPTY_ELEMENTDATA;
} else {
//其他情况抛出异常
throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity);
}
}
自动扩容
当添加元素时,会根据情况进行是否扩容。
public boolean add(E e) {
//ensureCapacityInternal:翻译:确保内部容量
//size == elementData.length 即当前数组大小
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
public boolean addAll(Collection<? extends E> c) {
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(size + numNew); // Increments modCount
System.arraycopy(a, 0, elementData, size, numNew);
size += numNew;
return numNew != 0;
}
再看 ensureCapacityInternal
是如何确保内部容量的
//minCapacity 数组需要的最小容量,(原容量+添加元素个数)
private void ensureCapacityInternal(int minCapacity) {
//ensureExplicitCapacity:翻译:确保明确的容量
//确保明确的容量,那 calculateCapacity(计算容量) 计算的就是明确的容量值咯
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
calculateCapacity
如何计算容量
private static final int DEFAULT_CAPACITY = 10;//默认扩容容量
private static int calculateCapacity(Object[] elementData, int minCapacity) {
/**
在添加元素方法到这里的时候,如果是 new ArrayList() 创建的对象,
就会进入到if中返回的,DEFAULT_CAPACITY(10) 将最小所需容量设置为 10
其他情况不设默认值,直接返回最小所需容量
还有一个是如果是new ArrayList(0) 创建的,也会直接返回 minCapacity,而不是给默认扩容容量
因为此时elementData指向的是EMPTY_ELEMENTDATA
*/
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
接下来看 ensureExplicitCapacity
:
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// 最少所需容量 > 原来容量 才进行扩容
if (minCapacity - elementData.length > 0)
grow(minCapacity); //扩容的方法
}
扩容方法:
private void grow(int minCapacity) {
// overflow-conscious code
//原来的容量
int oldCapacity = elementData.length;
//新的容量 (原来的容量+原来容量的一半[拟扩容的容量])
int newCapacity = oldCapacity + (oldCapacity >> 1);
//新的容量 < 最少所需容量
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
//新的容量 > 数组最大容量(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);
}
重新计算大容量:
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
//大于数组最大容量则用Integer.MAX_VALUE
//否则用数组最大容量作为新的容量值。
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
总结
ArrayList用默认无参构造方法创建时,在第一次添加元素时将数组大小扩展至默认容量(10)。
通常每次扩展容量,扩展至原来容量的1.5倍。
所需最少容量 > 原来容量的1.5倍时, 则扩展至所需最少容量。
拟扩容至的容量 > 数组的最大大小时,进行一次大容量扩容
- 所需最少容量 > 数组最大大小:扩容至Integer的最大值
- 所需最少容量 < 数组最大大小:扩容至数组最大大小(Integer.Max -8)
本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 tangseng233的日常!
评论