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

ArrayList源码初探