ArrayList源码浅析

摘要：注意，迭代器的快速失败行为无法得到保证，快速失败迭代器会尽最大努力抛出。迭代器的快速失败行为应该仅用于检测。

首先看方法声明：

public class ArrayList extends AbstractList
        implements List, RandomAccess, Cloneable, java.io.Serializable

RandomAccess：

public interface RandomAccess {
}

RandomAccess接口都是给 List所使用的，用来表明其支持快速（通常是固定时间）随机访问，为其提供良好的性能。实际经验证明，如果是下列情况，则 List 实现应该实现此接口，即对于典型的类实例而言，此循环：

for (int i=0, n=list.size(); i < n; i++)
         list.get(i);

的运行速度要快于以下循环：

for (Iterator i=list.iterator(); i.hasNext(); )
         i.next();

Cloneable：

public interface Cloneable {
}

实现了此接口的类就可以通过重写 Object.clone（）方法来定制对其进行复制的细节,如果在没有实现 Cloneable 接口的实例上调用 Object 的 clone 方法，则会导致抛出 CloneNotSupportedException 异常。

/**
* ArrayList中元素存储的地方，数组的长度就是它的容量
*/
private transient Object[] elementData;

/**
 *ArrayList所包含的元素的大小 
*/
private int size;

提供了3种构造方法：

public ArrayList(int initialCapacity) {
        super();
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        this.elementData = new Object[initialCapacity];
    }
    
public ArrayList() {
        this(10);
    }    
    
public ArrayList(Collection c) {
        elementData = c.toArray();
        size = elementData.length;
        // c.toArray might (incorrectly) not return Object[] (see 6260652)
        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    }    

可以看到：第一种方法需要一个默认的容量大小，第二个是默认的构造方法，会默认创建一个容量为10的 ArrayList，第三个则传给一个 Collection，注意，不管 Collection里面是什么类型，最后放进 ArrayList都会上转为 Object

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

add方法中使用了 ensureCapacityInternal来控制容量：

private void ensureCapacityInternal(int minCapacity) {
        modCount++;
        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

其中 modCount是用来记录 list被结构修改的次数，所谓结构上的修改是 指任何添加或删除一个或多个元素的操作，或者显式调整底层数组的大小；仅仅设置元素的值不是结构上的修改；在上面的方法中，如果 minCapacity 大于现有数组长度，则执行 grow方法：

private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        /*newCapacity 扩展为旧容量的1.5倍左右*/
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        /*如果这时新容量还小于minCapacity，则新容量为minCapacity*/
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        /*新容量大于 Integer.MAX_VALUE - 8*/    
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // 最后将原数组放进新数组，改变长度
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

如果 newCapacity大于 Integer.MAX_VALUE - 8，则 newCapacity为 Integer.MAX_VALUE，这也是能够扩充的最大容量

再来看第二种 add方法：

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++;
    }

这种方法是在指定位置插入元素，主要使用了 System.arraycopy（）方法将 index之后的元素向后移动一个位置，将 index位空出来放入新元素

clear方法比较简单，但是注意调用 clear也会使 modCount加1：

public void clear() {
        modCount++;

        // Let gc do its work
        for (int i = 0; i < size; i++)
            elementData[i] = null;

        size = 0;
    }

public Object clone() {
        try {
            @SuppressWarnings("unchecked")
            ArrayList v = (ArrayList) super.clone();
            v.elementData = Arrays.copyOf(elementData, size);
            v.modCount = 0;
            return v;
        } catch (CloneNotSupportedException e) {
            // this shouldn"t happen, since we are Cloneable
            throw new InternalError();
        }
    }

clone方法只能进行浅复制，并不复制元素本身

public boolean remove(Object o) {
        if (o == null) {
            for (int index = 0; index < size; index++)
                if (elementData[index] == null) {
                    fastRemove(index);
                    return true;
                }
        } else {
            for (int index = 0; index < size; index++)
                if (o.equals(elementData[index])) {
                    fastRemove(index);
                    return true;
                }
        }
        return false;
    }

remove方法中，如果要移除的元素为 null，则删除数组中第一个为 null的元素。如果数组中有超过一个匹配的元素，仅移除第一个

public Object[] toArray() {
        return Arrays.copyOf(elementData, size);
    }

这个方法被很多方法使用，它调用了 Arrays工具类中的方法 copyOf：

public static  T[] copyOf(T[] original, int newLength) {
        return (T[]) copyOf(original, newLength, original.getClass());
    }

public static  T[] copyOf(U[] original, int newLength, Class newType) {
        T[] copy = ((Object)newType == (Object)Object[].class)
            ? (T[]) new Object[newLength]
            : (T[]) Array.newInstance(newType.getComponentType(), newLength);
        System.arraycopy(original, 0, copy, 0,
                         Math.min(original.length, newLength));
        return copy;
    }

最终调用了方法：

public static void arraycopy(Object src,int srcPos,Object dest,int destPos,int length)

它的参数列表如下：

src - 源数组。
srcPos - 源数组中的起始位置。 
dest - 目标数组。
destPos - 目标数据中的起始位置。
length - 要复制的数组元素的数量。

从指定源数组中复制一个数组，复制从指定的位置开始，到目标数组的指定位置结束。这个方法是一个 native方法，并且经测试，如果是引用数组类型，它不会真正复制对象，只是复制引用（浅复制）

将此 ArrayList 实例的容量调整为列表的当前大小。应用程序可以使用此操作来最小化 ArrayList 实例的存储量。

public void trimToSize() {
        modCount++;
        int oldCapacity = elementData.length;
        if (size < oldCapacity) {
            elementData = Arrays.copyOf(elementData, size);
        }
    }

由此可知:在 ArrayList容量确定下来以后，可以调用这个方法最小化存储空间

此类的 iterator 和 listIterator 方法返回的迭代器是快速失败的：在创建迭代器之后，除了通过迭代器自身的 remove 或 add 方法从结构上对列表进行修改，否则在任何时间以任何方式对列表进行修改，迭代器都会抛出 ConcurrentModificationException。因此，面对并发的修改，迭代器很快就会完全失败，而不是冒着在将来某个不确定时间发生任意不确定行为的风险。
注意，迭代器的快速失败行为无法得到保证，快速失败迭代器会尽最大努力抛出 ConcurrentModificationException。迭代器的快速失败行为应该仅用于检测 bug。
前面说到 ArrayList中定义了一个 modCount来记录对容器进行结构修改的次数，在 add、 addAll、 remove、 clear、 clone方法中都会引起 modCount变化，而在创建迭代器时，会使用局部变量保存当前的 modCount值：

private class Itr implements Iterator {
        int cursor;       // index of next element to return
        int lastRet = -1; // index of last element returned; -1 if no such
        int expectedModCount = modCount;
        ...

在进行迭代的过程中，会先检查 modCount 有没有发生变化，以此来判定是否有外部操作改变了容器：

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

最后，因为 ArrayList是非同步的，因此，在多线程环境下，如果有对容器进行结构修改的操作，则必须使用外部同步。