ArrayList可以实现容量的自适应的增加(As elements are added to an ArrayList,
its capacity grows automatically)。通过JDK1.8中ArrayList的源码来分析：
ArrayList的相关定义
ArrayList底层采用Object类型的数组实现。
首先，定义默认初始容量，为10
private static final int DEFAULT_CAPACITY = 10;
再有，定义用于空实例的空数组实例
private static final Object[] EMPTY_ELEMENTDATA = {};
再有，定义空数组实例，用于默认大小的空实例
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
再有，定义了一个未被序列化的数组elementData，用来存储ArrayList对象列表
/**
* The capacity of the ArrayList is the length of this array buffer.
*/
transient Object[] elementData;
再有，定义了ArrayList的size变量
/**
* The size of the ArrayList (the number of elements it contains).
*/
private int size;
为了实现ArrayList的自动扩容机制，java引进了capacity和size概念,以区别数组的length。capacity是底层数组的长度(length)，size是存储的列表对象的数量，被设置为private的。
ArrayList的初始化
ArrayList有三种方式来初始化，构造方法源码如下：
1.用指定的初始容量构造一个空列表
/**
* Constructs an empty list with the specified initial capacity.
*/
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);
}
}
2.使用初始容量10构造一个空列表(无参数构造)
/**
* Constructs an empty list with an initial capacity of ten.
*/
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
3.构造包含指定collection元素的列表，这些元素利用该集合的迭代器按顺序返回
如果指定的集合为null，throws NullPointerException。
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();//用Collection初始化数组elementData
if ((size = elementData.length) != 0) {
// c.toArray might (incorrectly) not return Object[] (see 6260652)
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
// replace with empty array.
this.elementData = EMPTY_ELEMENTDATA;
}
}
ArrayList扩容
以无参数构造为例，初始数组容量为10。当真正对数组进行添加时，才真正分配容量。即向数组中添加第一个元素时，数组容量扩为10。
1.以add(E e)方法为入口分析
public boolean add(E e) {
//添加元素之前，先调用ensureCapacityInternal方法
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;//添加对象时，自增size
return true;
}
2.进入到ensureCapacityInternal方法
ensureCapacityInternal（“确保内部容量”）。
private void ensureCapacityInternal(int minCapacity) {
//先判断数组是否为空
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
//如果数组为空，将DEFAULT_CAPACITY(为10)和minCapacity中较大的一个赋值给minCapacity
//则minCapaciy至少为10
}
ensureExplicitCapacity(minCapacity);
//执行ensureExplicitCapacity方法
}
当空列表add()第1个元素时，调试可知：原本minCapacity为1，在Math.max()方法比较后，minCapacity为10。
但当add()第2个元素时，数组非空，直接进入ensureExplicitCapacity(minCapacity)（此时minCapacity为2）。
3.进入ensureExplicitCapacity方法
无论数组是否为空，都会进入ensureExplicitCapacity方法。
private void ensureExplicitCapacity(int minCapacity) {
modCount++;//定义于ArrayList的父类AbstractList，用于存储结构修改次数
// overflow-conscious code
if (minCapacity - elementData.length > 0)
//如果数组的长度(elementData.length)小于最小需要的容量(minCapacity)，就扩容
grow(minCapacity);
}
当要add第1个元素时，这时elementData.length（为0，因为此时还是空列表）是要比minCapacity（为10）小的，会进入grow(minCapacity)方法（minCapacity为10）。
当add第2个元素时，调试可知：minCapacity为2，此时elementData.length(即是容量)在添加第一个元素后扩容成10了，比minCapacity大，不会去执行grow方法 。数组容量仍为10。
所以当添加第3、4···到第10个元素时，依然不会执行grow方法，数组容量都为10。
直到添加第11个元素，minCapacity(为11)比elementData.length（为10）要大。进入grow方法进行扩容。
4.进入grow方法进行扩容
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
//用来分配数组的size最大值
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
//右移一位相当于原数除以2，位运算的计算方式更快
//所以新容量扩大为原容量的1.5倍
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
//从minCapacity和这个newCapacity中取较大值作为扩容后的新数组长度（新容量）。
//这主要是针对添加第1个元素。1.5倍oldCapacity为0，所以newCapacity为最小容量10
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
//如果新容量大于数组的最大size，进入hugeCapacity方法
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
//最后，将原来数组的数据复制到新的数组中。
}
当add第1个元素时，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方法中return true,size增为11。
以此类推······
5.如果新容量大于MAX_ARRAY_SIZE,进入hugeCapacity方法
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
//对minCapacity和MAX_ARRAY_SIZE进行比较
//若minCapacity大，将Integer.MAX_VALUE作为新数组的大小
//若MAX_ARRAY_SIZE大，将MAX_ARRAY_SIZE作为新数组的大小
}
所以，像ArrayList添加对象时，在确定好新数组的大小后，会调用Arrays.copyOf()方法，以适当长度(newCapacity)新建一个原数组的拷贝，并修改原数组，指向这个新建数组。java垃圾回收机制会自动回收原数组。这样会消耗一定的资源。
因此，在初始化ArrayList时，最好可以估算一个初始大小。
6.最好在add大量元素之前用ensureCapacity方法，以减少增量从新分配的次数。 源码如下：
/**
* <p>An application can increase the capacity of an <tt>ArrayList</tt> instance
* before adding a large number of elements using the <tt>ensureCapacity</tt>
* operation. This may reduce the amount of incremental reallocation.
*/
public void ensureCapacity(int minCapacity) {
int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
// any size if not default element table
? 0
// larger than default for default empty table. It's already
// supposed to be at default size.
: DEFAULT_CAPACITY;
if (minCapacity > minExpand) {
ensureExplicitCapacity(minCapacity);
}
}
网友评论