ArrayList简介

ArrayList 是一个数组队列，内部维护一个 Java数组，并且它是动态的，数组的容量可以自动增长。它继承了 AbstractList，且实现了 List、RandomAccess、Cloneable、Serializable等接口。

ArrayList的优缺点

优点

• 支持随机存取，由于其内部是一个数组，随机访问元素等于通过数组下标访问，随机获取元素效率高。
• 元素是有序的（按照添加顺序）。
• 支持自动扩容（既是优点也是缺点）。

缺点

• 线程不安全。
• 自动扩容效率低，每次扩容都需要将所有元素添加到新增数组中。
• 添加和删除操作需要移动数组中的元素。

ArrayList部分字段

/**
 * 默认容量为10
 */
private static final int DEFAULT_CAPACITY = 10;

/**
 * 空数组 
 */
private static final Object[] EMPTY_ELEMENTDATA = {};

/**
 * 用于默认大小的空数组。将此与EMPTY_ELEMENTDATA区分开来，以便在添加第一个元素时知道要膨胀多少。
 * 使用无参构造初始化ArrayList时默认的数组
 */
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

/**
 * 存储ArrayList元素的数组。添加第一个元素时，如果elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
 * 则此数组的长度是默认的10
 */
transient Object[] elementData;

/**
 * ArrayList的元素个数
 */
private int size;

ArrayList的构造方法

带一个 int类型参数的构造方法，传入的是 ArrayList的初始长度

public ArrayList(int initialCapacity) {
	if (initialCapacity > 0) {
			this.elementData = new Object[initialCapacity];
	} else if (initialCapacity == 0) {
			// 默认的空数组 Object[] EMPTY_ELEMENTDATA = {}
			this.elementData = EMPTY_ELEMENTDATA;
	} else {
			throw new IllegalArgumentException("Illegal Capacity: "+initialCapacity);
	}
}

JDK8的无参构造

public ArrayList() {
	this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

JDK8中使用默认的无参构造方法初始化 ArrayList时，做了延迟优化，在未执行 add() 方法前 ArrayList 数组中的实际大小还是 0，等到第一次添加元素的时候才进行默认长度为 10的数组初始化。

传入一个集合对象的构造方法，构造一个包含此集合元素的 ArrayList

public ArrayList(Collection<? extends E> c) {
	elementData = c.toArray();
	if ((size = elementData.length) != 0) {
			if (elementData.getClass() != Object[].class)
					elementData = Arrays.copyOf(elementData, size, Object[].class);
	} else {
			this.elementData = EMPTY_ELEMENTDATA;
	}
}

ArrayList自动扩容

首先看 add(E e)方法

public boolean add(E e) {
	// 判断添加此元素时数组是否会超出，超出则增长数组
	ensureCapacityInternal(size + 1);
	// 添加元素
	elementData[size++] = e;
	return true;
}

/**
 * 此方法用于判断当添加这个元素时数组容量是否超出，超出则自动增长
 */
private void ensureCapacityInternal(int minCapacity) {
	ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

private static int calculateCapacity(Object[] elementData, int minCapacity) {
	// 如果数组是通过默认构造方法实例化的，elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA 将返回true
	if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
			// 返回最大的值 ，如果minCapacity大于10则返回minCapacity的值
			return Math.max(DEFAULT_CAPACITY, minCapacity);
	}
	return minCapacity;
}

private void ensureExplicitCapacity(int minCapacity) {
	// fail-fast机制，并发修改会抛出异常 throw new ConcurrentModificationException()
	modCount++;

	// overflow-conscious code
	if (minCapacity - elementData.length > 0)
			// 新增元素后的数组长度超过了当前数组长度，所以调用增加数组长度的方法
			grow(minCapacity);
}

看一看 grow(int minCapacity)方法就能知道 ArrayList是如何自动增长容量的了

// 分配的最大数组大小
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

private void grow(int minCapacity) {
	// overflow-conscious code
	int oldCapacity = elementData.length;
	// 增长后的容量等于旧容量的1.5倍
	int newCapacity = oldCapacity + (oldCapacity >> 1);
	if (newCapacity - minCapacity < 0)
			newCapacity = minCapacity;
	 // MAX_ARRAY_SIZE为int的最大值减8，如果增长后的容量超过该值，则直接返回int的最大值，否则返回该值
	if (newCapacity - MAX_ARRAY_SIZE > 0);
			newCapacity = hugeCapacity(minCapacity);
	// 使用的是Arrays.copyOf()方法将原数组中的元素拷贝到新增数组中，新增数组的长度即是newCapacity
	elementData = Arrays.copyOf(elementData, newCapacity);
}

再看 hugeCapacity(int minCapacity)方法

private static int hugeCapacity(int minCapacity) {
	if (minCapacity < 0) 
			throw new OutOfMemoryError();
	return (minCapacity > MAX_ARRAY_SIZE) ?
			Integer.MAX_VALUE :
			MAX_ARRAY_SIZE;
}

JDK8中使用了位运算，直接增长为旧容量的1.5倍。

fail-fast机制

由于 ArrayList不是线程安全的，所以如果在使用迭代器的过程中有其它线程修改了 ArrayList，那么将会抛出 throw new ConcurrentModificationException()的异常，这就是 fail-fast机制（快速失败）。
fail-fast机制是通过 modCount字段来判断的，modCount字段是父类 AbstractList的字段，在每次修改 ArrayList时，modCount字段都会自动加1，迭代器初始化时会将 modCount的值赋给迭代器的 expectedModCount字段。 ArrayList的迭代器内部实现（部分）

public Iterator<E> iterator() {
	return new Itr();
}

private class Itr implements Iterator<E> {
	int cursor;   
	int lastRet = -1; 
	int expectedModCount = modCount;

	Itr() {}

	public boolean hasNext() {
		return cursor != size;
	}

	@SuppressWarnings("unchecked")
	public E next() {
		checkForComodification();
		int i = cursor;
		if (i >= size)
				throw new NoSuchElementException();
		Object[] elementData = ArrayList.this.elementData;
		if (i >= elementData.length)
				throw new ConcurrentModificationException();
		cursor = i + 1;
		return (E) elementData[lastRet = i];
	}

	public void remove() {
		if (lastRet < 0)
				throw new IllegalStateException();
		checkForComodification();

		try {
				ArrayList.this.remove(lastRet);
				cursor = lastRet;
				lastRet = -1;
				expectedModCount = modCount;
		} catch (IndexOutOfBoundsException ex) {
				throw new ConcurrentModificationException();
		}
	}
}

在执行 next()、remove()方法时都会调用 checkForComodification()方法，判断 expectedModCount是否还等于 modCount，如果不相等则说明已经有其它线程修改了 ArrayList，这时就将抛出异常 throw new ConcurrentModificationException()。

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