ArrayList 源码解析

ArrayList是Java集合框架中的一个动态数组实现，提供了可变大小的数组功能。它继承自AbstractList并实现了List接口，是顺序容器，即元素存放的数据与放进去的顺序相同，允许放入null元素，底层通过数组实现。除该类未实现同步外，其余跟Vector大致相同。每个ArrayList都有一个容量capacity，表示底层数组的实际大小，容器内存储元素的个数不能多于当前容量。当向容器中添加元素时，如果容量不足，容器会自动增大底层数组的大小。

一、成员变量

size(), isEmpty(), get(),set()方法均能在常数时间内完成，add()方法的时间开销跟插入位置有关，addAll()方法的时间开销跟添加元素的个数成正比。其余方法大都是线性时间。为追求效率，ArrayList没有实现同步synchronized，如果需要多个线程并发访问，用户可以手动同步，也可使用Vector替代。

public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable {private static final int DEFAULT_CAPACITY = 10;private static final Object[] EMPTY_ELEMENTDATA = {};private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};transient Object[] elementData; // non-private to simplify nested class accessprivate int size;
}

【1】DEFAULT_CAPACITY：默认初始容量为10。
【2】EMPTY_ELEMENTDATA：空数组实例，用于空实例。
【3】DEFAULTCAPACITY_EMPTY_ELEMENTDATA：默认容量为空数组实例。
【4】elementData：存储元素的数组。
【5】size：当前ArrayList中的元素数量。

二、构造方法

public ArrayList() {this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}public ArrayList(int initialCapacity) {if (initialCapacity > 0) {this.elementData = new Object[initialCapacity];} else if (initialCapacity == 0) {this.elementData = EMPTY_ELEMENTDATA;} else {throw new IllegalArgumentException("Illegal Capacity: " + initialCapacity);}
}

【1】无参构造方法：初始化elementData为默认容量的空数组。
【2】指定初始容量的构造方法：根据传入的初始容量创建数组。

三、添加元素

public boolean add(E e) {ensureCapacityInternal(size + 1);  // Increments modCount!!elementData[size++] = e;return true;
}private void ensureCapacityInternal(int minCapacity) {if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);}ensureExplicitCapacity(minCapacity);
}private void ensureExplicitCapacity(int minCapacity) {if (minCapacity - elementData.length > 0)grow(minCapacity);
}private void grow(int minCapacity) {int oldCapacity = elementData.length;int newCapacity = oldCapacity + (oldCapacity >> 1);if (newCapacity - minCapacity < 0)newCapacity = minCapacity;if (newCapacity - MAX_ARRAY_SIZE > 0)newCapacity = hugeCapacity(minCapacity);elementData = Arrays.copyOf(elementData, newCapacity);
}

【1】add(E e)：添加元素到ArrayList中。
【2】ensureCapacityInternal(size + 1)：确保内部数组有足够的容量。
【3】elementData[size++] = e：将元素添加到数组中，并增加size。
【4】ensureCapacityInternal(int minCapacity)：检查并确保内部数组的容量。
【5】ensureExplicitCapacity(int minCapacity)：如果需要，增加数组的容量。
【6】grow(int minCapacity)：增加数组的容量，通常是原来容量的1.5倍。

四、获取元素

public E get(int index) {rangeCheck(index);return elementData(index);
}private void rangeCheck(int index) {if (index >= size)throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}E elementData(int index) {return (E) elementData[index];
}

【1】get(int index)：获取指定索引处的元素。
【2】rangeCheck(index)：检查索引是否越界。
【3】elementData(index)：返回数组中指定位置的元素。

五、删除元素

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 workreturn oldValue;
}

【1】remove(int index)：删除指定索引处的元素。
【2】rangeCheck(index)：检查索引是否越界。
【3】System.arraycopy：将后续元素向前移动一位。
【4】elementData[--size] = null：将最后一个元素设为null，帮助垃圾回收。

六、大小调整

ArrayList的核心在于其动态调整大小的能力，通过grow方法来实现。当添加元素时，如果内部数组容量不足，就会创建一个更大的数组，并将旧数组中的元素复制到新数组中。

每当向数组中添加元素时，都要去检查添加后元素的个数是否会超出当前数组的长度，如果超出，数组将会进行扩容，以满足添加数据的需求。数组扩容通过一个公开的方法ensureCapacity(int minCapacity)来实现。在实际添加大量元素前，我也可以使用ensureCapacity来手动增加ArrayList实例的容量，以减少递增式再分配的数量。数组进行扩容时，会将老数组中的元素重新拷贝一份到新的数组中，每次数组容量的增长大约是其原容量的1.5倍。这种操作的代价是很高的，因此在实际使用时，我们应该尽量避免数组容量的扩张。当我们可预知要保存的元素的多少时，要在构造ArrayList实例时，就指定其容量，以避免数组扩容的发生。或者根据实际需求，通过调用ensureCapacity方法来手动增加ArrayList实例的容量。

    /*** Increases the capacity of this <tt>ArrayList</tt> instance, if* necessary, to ensure that it can hold at least the number of elements* specified by the minimum capacity argument.** @param   minCapacity   the desired minimum capacity*/public void ensureCapacity(int minCapacity) {int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)// any size if not default element table? 0// larger than default for default empty table. It's already// supposed to be at default size.: DEFAULT_CAPACITY;if (minCapacity > minExpand) {ensureExplicitCapacity(minCapacity);}}private void ensureCapacityInternal(int minCapacity) {if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);}ensureExplicitCapacity(minCapacity);}private void ensureExplicitCapacity(int minCapacity) {modCount++;// overflow-conscious codeif (minCapacity - elementData.length > 0)grow(minCapacity);}/*** The maximum size of array to allocate.* Some VMs reserve some header words in an array.* Attempts to allocate larger arrays may result in* OutOfMemoryError: Requested array size exceeds VM limit*/private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;/*** Increases the capacity to ensure that it can hold at least the* number of elements specified by the minimum capacity argument.** @param minCapacity the desired minimum capacity*/private void grow(int minCapacity) {// overflow-conscious codeint 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);}private static int hugeCapacity(int minCapacity) {if (minCapacity < 0) // overflowthrow new OutOfMemoryError();return (minCapacity > MAX_ARRAY_SIZE) ?Integer.MAX_VALUE :MAX_ARRAY_SIZE;}

七、总结

Fail-Fast机制： ArrayList也采用了快速失败的机制，通过记录modCount参数来实现。在面对并发的修改时，迭代器很快就会完全失败，而不是冒着在将来某个不确定时间发生任意不确定行为的风险。