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

一、成员变量

<code>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 access

private 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 work

return 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 code

if (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 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);

}

private static int hugeCapacity(int minCapacity) {

if (minCapacity < 0) // overflow

throw new OutOfMemoryError();

return (minCapacity > MAX_ARRAY_SIZE) ?

Integer.MAX_VALUE :

MAX_ARRAY_SIZE;

}

七、总结

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