ArrayList
ArrayList是基于数组这一数据结构,其并非线程安全,在多线程环境下对其进行操作会引发线程安全问题。ArrayList继承至AbstractList,实现了List、RandomAccess、Cloneable、Serializable等接口
ArrayList的数据结构
/**
* 默认初始容量
*/
private static final int DEFAULT_CAPACITY = 10;
/**
* Shared empty array instance used for empty instances.
*/
private static final Object[] EMPTY_ELEMENTDATA = {};
/**
* Shared empty array instance used for default sized empty instances. We
* distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when
* first element is added.
* 按照注释上的说明,这个空数组是用于和EMPTY_ELEMENTDATA区分开来,当第一个元素被加入的时候,以此来判断需要进行多大程度的扩容。按照变量名来理解,ArrayList被实例化的时候,如果不指定初始容量,则会默认设置为10,这个空数组就是表示在默认情况下被赋予的初始数组
*/
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
/**
* The array buffer into which the elements of the ArrayList are stored.
* The capacity of the ArrayList is the length of this array buffer. Any
* empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
* will be expanded to DEFAULT_CAPACITY when the first element is added.
*
* ArrayList中的数组容器,下文中的数组容器皆是指代本数组
* elementData被transient标注,这个值不会被序列化。原因是因为数组会动态扩容,如果原样序列化的话会造成磁盘空间的浪费,因此ArrayList自己实现了ReadObject和WriteObject方法,当序列化时,只会在磁盘上写出size个数的元素
*/
transient Object[] elementData; // non-private to simplify nested class access
/**
* 容器内元素的个数
*
* @serial
*/
private int size;
ArrayList的构造器
public ArrayList()
public ArrayList(int initialCapacity)
public ArrayList(Collection<? extends E> c)
当构造器中不传参数时,会将数组容器指向DEFAULTCAPACITY_EMPTY_ELEMENTDATA
当传入初始容量值的时候,如果初始值等于0,会将容器数组指向EMPTY_ELEMENTDATA
当初始容量值大于0时,会实例化一个Object数组,容量为初始容量值。
当传入一个Collection的实现的时候,会调用该实例的toArray方法,并将其赋值给数组容器,且将数组容量值size置为该数组的长度。
这里源码中做了一个操作,被赋值后的数组容器长度不等于0,且toArray的结果返回的不是一个Object类型的数组的时候,会新建一个Object数组,并该集合对象的元素全拷贝到新建的集合对象里去。之所以这样处理是因为Collection的toArray方法并不一定会返回一个Object数组,非Object数组是无法存储Object对象的,这里注释里给出了一个Bug编号6260652。我们可以通过下述实验来验证这一点:
String []list = new String[]{"Lain"};
Object [] listObj = list;//由于存在向上转型,子类数组可以直接转换成父类数组
System.out.println("Lain".getClass());
System.out.println(list.getClass());
listObj[0] = new Object();//抛出java.lang.ArrayStoreException
System.out.println("end");
//输出:
// class java.lang.String
// class [Ljava.lang.String;
// Exception in thread "main" java.lang.ArrayStoreException: java.lang.Object
// at fun.lain.laintest.ArrayTest.main(ArrayTest.java:10)
当被赋值后的数组容器长度为0时,它会将常量EMPTY_ELEMENTDATA赋值给它,用于表示这个ArrayList对象是一个初始容量为0的数组列表。
为什么要用EMPTY_ELEMENTDATA和DEFAULTCAPACITY_EMPTY_ELEMENTDATA来区分这两种状态呢?主要是会影响数组的扩容操作。
ArrayList的主要方法
添加操作
当一个元素被添加到数组容器中来,首先会保证数组容器中有足够的空间放入该元素,因此会先调用ensureCapacityInternal方法,对数组进行扩容。
ensureCapacityInternal方法传入一个int类型的参数minCapacity,我在这里称之为最小预期值,确保数组的容量不会小于该值。当数组容器指向的是DEFAULTCAPACITY_EMPTY_ELEMENTDATA时,会比较该值与默认初始化值的大小,取当中较大的一方作为最小预期值参与扩容计算。当数组容器的值小于最小预期值时,会触发扩容操作grow(int minCapacity)。
private void grow(int minCapacity) {//拟定的最小容量
// overflow-conscious code 防止越界的代码
int oldCapacity = elementData.length;//当前数组容量作为旧值,注意,数组的长度并不等于其size,而是等于其容量的大小,和其中的元素没有关系
int newCapacity = oldCapacity + (oldCapacity >> 1);//预计的新容量值
if (newCapacity - minCapacity < 0)//如果新容量值比最小预期值还小,则将最小预期值作为新容量值
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)//校验新容量值是否突破MAX_ARRAY_SIZE,如果突破,此时离越界只差8
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();//判断预期容量值是否小于0,小于则说明已经内存溢出了
return (minCapacity > MAX_ARRAY_SIZE) ?//如果预期容量值大于最大容量值,且没有超出int的最大范围
Integer.MAX_VALUE ://则将数组新容量值设置为Integer的最大值
MAX_ARRAY_SIZE;//还没达到的话就扩容至MAX_ARRAY_SIZE
}
可以看到,每次扩容操作时,都会以原数组长度的1.5倍(>>1 相当于除以2),作为新容量值,当预计值依旧小于最小预期值时,会将最小预期值作为新容量值,然后判断新容量值是否越界(超过MAX_ARRAY_SIZE,MAX_ARRAY_SIZE是个常量,数值为Integer的最大值-8),如果超过,则以最小预期值为基准计算新容量值,如果最小预期值本身没有超过MAX_ARRAY_SIZE的话,则新容量值为MAX_ARRAY_SIZE,否则为Integer.MAX_VALUE。如果最小预期值突破了Integer.MAX_VALUE,毫无疑问它会变成负数,并抛出越界异常。
add(E)
此方法向数组中插入一个元素。
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
代码很简单,我们可以看到方法开头就调用了扩容判断方法。
前文说过了,ArrayList的构造器会对容器的扩容照成一定的影响。让我们假设一下各个初始化方法在加入第一个元素时会有什么区别:
-
当调用的是其无参构造器
使用了默认的初始容量10,且数组容器指向DEFAULTCAPACITY_EMPTY_ELEMENTDATA时,size值为0,当第一个元素被添加时,此时以size + 1作为minCapacity,传入扩容方法中,此时minCapacity显然小于10,所以会以10作为预期容量,进入grew方法。由于此时数组容器还指向空数组,所以数组长度为0,计算出的新容量也等于0(0+0>>1 = 0),新容量小于预期容量,将预期容量10作为新容量值,且10远小于MAX_ARRAY_SIZE,不会进入越界判断,因此当第一个元素被加入时,将数组扩充到10。
-
当调用的是有参构造器
当参数为0,或是空集合对象的时候,都会将数组容器指向EMPTY_ELEMENTDATA,和默认的无参构造器不同的是,由于指向不是DEFAULTCAPACITY_EMPTY_ELEMENTDATA,因此在插入第一个元素的时候,并不会将minCapacity替换成10,而是保持传入的size+1,也就是1作为预期容量值。在初次加入元素的时候只会扩容1个位置。
当有参数大于0时,在构造器中就会依照参数初始化数组容器,容量为初始化参数。
当传入的集合对象非空时,数组容器的容量等于传入的集合对象的容量。
预测结论:由于只有当数组容器的容量小于预期值时,才会触发扩容,因此,在频繁调用add的情况下,如果以空对象或参数0初始化ArrayList,在元素量比较少的时候会频繁的触发扩容,使得性能会有所下降。这就要看自己的需求了,如果预计要插入大量元素,建议给一个比较大的初始化容量以减少扩容次数,但同时也要注意空间的浪费,如果只有十几个元素,却给他一个十几倍大的容量值,这就是对资源的浪费了。
add(int,E)
先来看源代码
public void add(int index, E element) {
rangeCheckForAdd(index);
ensureCapacityInternal(size + 1); // Increments modCount!!
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}
该函数在指定位置插入元素,首先会检查index是否越界,小于0或大于size的时候会抛越界异常。
然后就是我们的老朋友,扩容函数,确保数组容器能够放下这个元素。
最后调用系统方法,将index之后的所有元素向后拷贝一位,将index指向的位置空出来,然后将元素放到该位置上。