ArrayList源码分析

概览

1 2	public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable

ArrayList是基于数组实现的，所以支持快速的随机访问。

属性解释

1	private static final int DEFAULT_CAPACITY = 10;

默认的初始容量。在创建ArrayList实例的时候可以不用指定其大小，默认的容量大小为10；但建议提前预估好合适的容量大小，因为扩容的开销比较大。后面会专门分析。

1	private static final Object[] EMPTY_ELEMENTDATA = {};

共享的空数组实例。在创建ArrayList对象实例的时候，如果容量大小指定为为0时，会让elementData引用共享的整个空数组。

1	private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

共享的容量为10空数组。当我们使用无参构造器创建一个ArrayList对象时，该对象共享这个容量为10的空数组。官方注释中解释到：共享空数组实例，用于默认大小的空实例。我们将其与EMPTY_ELEMENTDATA区分开来，以了解何时添加第一个元素。在创建对象之初，并没有为它创建一个长度为10的数组，而在添加元素的时候，判断如果此时 elementData==DEFAULTCAPACITY_EMPTY_ELEMENTDATA的话，就以10为大小为其开辟了空间。

1	transient Object[] elementData

这就是ArrayList存取元素的数组了。它使用了transient修饰，说明它在不会被序列化。

1	private int size;

记录ArrayList的大小，即它包含的元素的大小。

1	protected transient int modCount = 0;

ArrayList中的方法中频繁出现了一个modCount的属性，它继承于AbstractList，用于记录List结构修改了多少次，所以每个修改List结构的方法中都存在modCount++ 。其作用在于在迭代或序列化时，需要比较前后的modCount的值，防止在迭代或序列化的同时List结构发生了改变。如果在这个过程之中发生了List结构改变，那么就会抛出ConcurrentModificationException 异常。

重要方法分析

1.添加

public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

private void ensureCapacityInternal(int minCapacity) {
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

private static int calculateCapacity(Object[] elementData, int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    return minCapacity;
}
 private void ensureExplicitCapacity(int minCapacity) {
    modCount++;

    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // minCapacity is usually close to size, so this is a win:
    elementData = Arrays.copyOf(elementData, newCapacity);
}

虽然看起来add(E e)方法牵扯的方法很多，但是其实它一点也不复杂。在添加之前调用了 ensureCapacityInternal(size+1)先确保容量是否足够。然后调用calculateCapacity(elementData, minCapacity)计算明确的需要的容量的大小。在这个方法中判断了如果elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA则返回需要的容量为10。现在已经知道了需要的容量大小了，下面就需要看一看现在的elementData够不够了，如果够的话，就可以直接添加了，否者就扩容。这个步骤方法ensureExplicitCapacity(int minCapacity)完成了。它还完成了modCount++,事情发展到了这一步，List结构的改变的结果已经不可逆转了，所以现在就可以记录List结构改变的次数了。如果这个时候容量不够，那么它就会调用grow(int minCapacity).这个方法会把容量拓展1.5倍，然后把所有的数据拷贝到新的elementData里面去。这一步是非常低效的，这也解释了为什么建议提前预估好容量。

删除

public E remove(int index) {
    rangeCheck(index);

    modCount++;
    E oldValue = elementData(index);

    int numMoved = size - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    elementData[--size] = null; // clear to let GC do its work

    return oldValue;
}

private void rangeCheck(int index) {
    if (index >= size)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

首先确保index的有效性，它调用了rangeCheck(int index)这里有一个非常有趣的现象，代码中它只在index>=size才抛异常。难道它没考虑index为负数的情况吗？其实它是考虑了的，只不过这个检查交给了Array处理。像get(-1)时会报异常ArrayIndexOutOfBoundsException。确保了index的有效性后，就可以删除了，这些大佬工程师写的数组的删除和大家一样，都是把index+1后面的元素复制到index位置上。这个操作的时间复杂度为O(N),代价还是比较高的。

fail-fast

fail-fast 机制是java集合(Collection)中的一种错误机制。当多个线程对同一个集合的内容进行操作时，就可能会产生fail-fast事件。例如：当某一个线程A通过iterator去遍历某集合的过程中，若该集合的内容被其他线程所改变了；那么线程A访问集合时，就会抛出ConcurrentModificationException异常，产生fail-fast事件。

ArrayList中的modCount

private void writeObject(java.io.ObjectOutputStream s)
    throws java.io.IOException{
    // Write out element count, and any hidden stuff
    int expectedModCount = modCount;
    s.defaultWriteObject();

    // Write out size as capacity for behavioural compatibility with clone()
    s.writeInt(size);

    // Write out all elements in the proper order.
    for (int i=0; i<size; i++) {
        s.writeObject(elementData[i]);
    }

    if (modCount != expectedModCount) {
        throw new ConcurrentModificationException();
    }
}

在序列化的时候，比较了前后的modCount值，防止序列化途中List结构发生了改变。