ArrayList扩容机制
在ArrayList中,声明了三个常量
private static final int DEFAULT_CAPACITY = 10;
private static final Object[] EMPTY_ELEMENTDATA = {};
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
还声明了一个数组
transient Object[] elementData;
然后再看一下ArrayList的构造方法
这是无参构造
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
这是有参构造
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
通常创建ArrayList时都是调用的无参构造,调用无参构造时,会将数组赋为默认长度的空数组,之后通过调取add方法添加元素时会进行扩容
add方法有三个,看一下常用add方法的源码
public boolean add(E e) {
modCount++;
add(e, elementData, size);
return true;
}
private void add(E e, Object[] elementData, int s) {
if (s == elementData.length)
elementData = grow();
elementData[s] = e;
size = s + 1;
}
调用boolean add(E e),首先让modCount++,这是用来记录数组被修改次数的变量,我们先不管它,此时size值为0,再调取void add(E e, Object[] elementData, int s)这个方法,将初始化的elementData,e, 还有size传过去,在这个add方法中先判断数组长度是否与size相等,如果相等,则调用grow()方法进行扩容,扩容后再将e插入到elementData最后,size+1。
看一下grow方法的源码
private Object[] grow() {
return grow(size + 1);
}
private Object[] grow(int minCapacity) {
return elementData = Arrays.copyOf(elementData,
newCapacity(minCapacity));
}
add方法调用grow的无参方法,无参grow方法又调用带参grow方法,并传入size+1。
在grow方法中,返回一个elementData,elementData等于Arrays.coptOf(element, newCapacity(minCapacity)),这个Arrays.copyOf是一个数组复制方法,将elementData数组赋给newCapacity(minCapacity)返回的新数组中。接着就是重点了,看newCapacity(minCapacity)方法的源码
private int newCapacity(int minCapacity) {
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity <= 0) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
return Math.max(DEFAULT_CAPACITY, minCapacity);
if (minCapacity < 0)
throw new OutOfMemoryError();
return minCapacity;
}
return (newCapacity - MAX_ARRAY_SIZE <= 0)
? newCapacity
: hugeCapacity(minCapacity);
}
在这个方法中有一个oldCapacity,表示旧的数组容量,还有一个newCapacity表示扩容后的数组容量,这个容量为oldCapacity+(oldCapacity >> 1),这里有一个位运算,表示将oldCapacity右移一位,在二进制中,右移一位相当于除以二,下面举例说明:
十进制2用二进制表示为10,右移一位后变为1,也就是十进制的1
十进制6用二进制表示为110,右移一位后变为11, 也就是十进制的3
所以扩容后的容量相当于oldCapacity * (Capacity / 2),也就有了ArrayList每次扩容都是原来1.5倍的说法。
扩容后判断是否小于minCapacity(注:minCapacity的值为grow传入的size+1),若小于,判断elementData是否为默认大小的空数组,若是,则返回minCapaacity与默认大小比较后的最大值。
若不是,再判断minCapacity是否小于0,若小于0,则抛出异常。最后再返回minCapacity。
oldCapacity由于扩容后没有引用,很快就会被垃圾回收器回收掉,再调用add方法时,还会再走一遍扩容流程,由于此时数组已经经过了一次扩容,他的size与elementData.length不同,直接插入即可,当到达上限后在进行下此次扩容。
我们可以写一段代码来查看ArrayList的容量
获取ArrayList当前容量
import java.lang.reflect.Field;
import java.util.ArrayList;
public class Test{
public static void main(String args[]) {
ArrayList<Integer> arrayList = new ArrayList<>();
System.out.println(getArrayListCapacity(arrayList));
arrayList.add(0);
System.out.println(getArrayListCapacity(arrayList));
for(int i = 0; i < 10; ++i)
arrayList.add(0);
System.out.println(getArrayListCapacity(arrayList));
for(int i = 0; i < 5; ++i)
arrayList.add(0);
System.out.println(getArrayListCapacity(arrayList));
}
public static int getArrayListCapacity(ArrayList<?> arrayList) {
Class<ArrayList> arrayListClass = ArrayList.class;
try {
Field field = arrayListClass.getDeclaredField("elementData");
field.setAccessible(true);
Object[] objects = (Object[])field.get(arrayList);
return objects.length;
} catch (NoSuchFieldException e) {
e.printStackTrace();
return -1;
} catch (IllegalAccessException e) {
e.printStackTrace();
return -1;
}
}
}
输出结果
0
10
15
22
以上均为个人理解,如有错误,欢迎指正,不胜感激。
|