原文地址：https://xeblog.cn/articles/19
本文主要介绍的是ArrayList在JDK8中的实现。
ArrayList简介
ArrayList 是一个数组队列，内部维护一个Java数组，并且它是动态的，数组的容量可以自动增长。它继承了AbstractList，且实现了List、RandomAccess、Cloneable、Serializable等接口。
ArrayList UML
ArrayList的优缺点
优点
- 支持随机存取，由于其内部是一个数组，随机访问元素等于通过数组下标访问，随机获取元素效率高。
- 元素是有序的（按照添加顺序）。
- 支持自动扩容（既是优点也是缺点）。
缺点
- 线程不安全。
- 自动扩容效率低，每次扩容都需要将所有元素添加到新增数组中。
- 添加和删除操作需要移动数组中的元素。
疑问：为何ArrayList继承AbstractList后又实现了List接口？
- 这个回答本人无法辨别内容真实性，不过可以晾出来晒晒。
stackoverflow上有人回答说是Josh Bloch（Java集合框架作者）设计失误，作者原本以为这样的设计是有价值的，后来发现并不是。
image
- 方便使用Java反射机制获取方法实现的所有接口，因为如果不显式的实现
List接口，反射获取接口的时候还需要先获取父类，然后再通过父类获取接口。 - 方便一眼就能看出
ArrayList实现了List接口（敷衍.gif）。 - 其它...
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;
}
JDK7的无参构造
public ArrayList() {
this(10);
}
JDK8中使用默认的无参构造方法初始化ArrayList时，做了延迟优化，在未执行add() 方法前ArrayList 数组中的实际大小还是0，等到第一次添加元素的时候才进行默认长度为10的数组初始化。
传入一个集合对象的构造方法，构造一个包含此集合元素的ArrayList
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
if ((size = elementData.length) != 0) {
// c.toArray might (incorrectly) not return Object[] (see 6260652)
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
// replace with empty array.
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) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
JDK6中 int newCapacity = (oldCapacity * 3)/2 + 1; 增长容量等于旧容量的1.5倍加1，JDK8中使用了位运算，直接增长为旧容量的1.5倍。
手动调整ArrayList的容量
在添加大量元素前，可以通过调用ensureCapacity(int minCapacity)方法来手动增加ArrayList的容量，以减少递增式再分配的数量
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);
}
}
trimToSize()方法可以将ArrayList的容量调整为实际元素的大小
public void trimToSize() {
modCount++;
if (size < elementData.length) {
elementData = (size == 0)
? EMPTY_ELEMENTDATA
: Arrays.copyOf(elementData, size);
}
}
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; // index of next element to return
int lastRet = -1; // index of last element returned; -1 if no such
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();
}
