ArrayList源码初探

Posted by Lain on 09-19,2019

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_ELEMENTDATADEFAULTCAPACITY_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的构造器会对容器的扩容照成一定的影响。让我们假设一下各个初始化方法在加入第一个元素时会有什么区别:

  1. 当调用的是其无参构造器

    使用了默认的初始容量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。

  2. 当调用的是有参构造器

    当参数为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指向的位置空出来,然后将元素放到该位置上。