ArrayList的底层是动态数组,初始容量为10,增长因子为1.5。在JDK1.7的时候默认的初始容量是在无参的构造方法中给出,在JDK1.8的时候默认容量是在第一次调用add方法时设置初始化的。本篇文章主要写的是ArrayList在jdk1.8时的扩容。
jdk1.7的时候
数组的大小
private static final int DEFAULT_CAPACITY = 10;
默认空数组元素
transient Object[] elementData;
默认初始化容量
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
记录被修改的次数执行add或者remove方法
private int size;
public ArrayList() {
super();
this.elementData = EMPTY_ELEMENTDATA;
}
public ArrayList(int initialCapacity) {
super();
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity);
this.elementData = new Object[initialCapacity];
}
jdk1.8
数组的大小
private static final int DEFAULT_CAPACITY = 10;
默认空数组元素
transient Object[] elementData;
默认初始化容量
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
记录被修改的次数执行add或者remove方法private int size;
初始容量为0
public ArrayList() {
this.elementData =DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
调用add方法时进行size+1,在调用ensureCapacityInternal方法
public boolean add(E e) {
ensureCapacityInternal(size +1);// Increments modCount!!
elementData[size++] = e;
return true;
}
ensureCapacityInternal方法主要进行数组的初始化工作,将数组的初始化为10,初始化完成后去执行ensureExplicitCapacity方法
private void ensureCapacityInternal(int minCapacity) {
if (elementData ==DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
进入ensureExplicitCapacity方法首先进行modCount自增,然后判断当前数组元素的个数是否大于数组的长度,如果不大于则不需要进行扩充,如果大于则需要grow方法进行扩充。
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
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;
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);
}
总结:
jdk1.8时ArrayList的扩充规则为。当第一次调用add方法时,首先对数组中元素的个数进行增加,其次调用ensureExplicitCapacity方法进行数组的初始化工作,接着调用ensureExplicitCapacity方法查看已有的元素是否大于数组的长度,如果不大于则不进行扩充,如果大于则进行调用grow方法进行扩充。扩充一共分为5步,第一步先获取原数组容量,然后设置新数组的容量是原数组容量的1.5倍,如果新容量小于老容量则将老容量的值设置给新容量。如果新容量的值大于数组的最大值调用hugeCapacity方法。最后调用copyOf在原数组上增加容量。
网友评论