1. AzrrayList 简介
java.util.ArrayList 是一个数组队列，相当于 动态数组。与Java中的数组相比，它具有容量能动态增长、元素增删慢、查找快的特点。
ArrayList继承于 AbstractList，实现了 List、 RandomAccess、 Cloneable、java.io.Serializable 这些接口。
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable{
--- omit ---
}ArrayList继承了AbstractList抽象方法，实现了List接口，提供了相关的添加、删除、修改、遍历等功能。RandomAccess是一个标志接口，表明实现这个这个接口的 List 集合是支持快速随机访问的。在ArrayList中，我们即可以通过元素的序号快速获取元素对象，这就是快速随机访问。ArrayList实现了Cloneable接口，即覆盖了函数clone()，能被克隆。ArrayList实现了java.io.Serializable接口，这意味着ArrayList支持序列化，能通过序列化去传输。
Tips：ArrayList中的操作不是线程安全的！建议在单线程中才使用ArrayList，多线程中选择使用Vector或者CopyOnWriteArrayList。
2. ArrayList源码简析（JDK 1.8）
2.1 成员属性
// 默认容量大小
private static final int DEFAULT_CAPACITY = 10;
// ArrayList空实例共享的一个空数组
private static final Object[] EMPTY_ELEMENTDATA = {};
// ArrayList空实例共享的一个空数组，用于默认大小的空实例。
// 与EMPTY_ELEMENTDATA分开，这样就可以了解当添加第一个元素时需要创建多大的空间。
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
// 真正存储ArrayList中的元素的数组
transient Object[] elementData;
// ArrayList 所包含的元素个数，注意并不是elementData的长度
private int size;
// 数组的最大长度
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;AbstractList抽象类中唯一属性：
// 表示elementData被修改的次数，每次add或者remove它的值都会加1
protected transient int modCount = 0;为什么size不是用来标记elementData数组的长度呢？
在Java中，一般来说：
length属性是针对数组而言的，比如下面源码中elementData.length表示elementData数组的长度。length()方法是针对字符串而言的，可以调用length()获取字符串长度。size()方法是针对泛型集合而言的，可以调用size()来获取集合中个数。
这样，就很好理解为什么size不是ArrayList的长度了，不易记混。
2.2 构造方法
ArrayList有三种初始化方式：
/**
* 有参的构造函数
*/
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
// 初始化容量大于0，创建initialCapacity大小的数组
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
// 初始化容量等于0，创建空数组
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
/**
* 默认无参构造函数（未指定初始化容量大小），使用初始容量10构造一个空列表。
*/
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
/**
* 使用Collection集合来初始化ArrayList
*/
public ArrayList(Collection<? extends E> c) {
// 将集合转换为数组
elementData = c.toArray();
// 如果数组的长度size不等于0
if ((size = elementData.length) != 0) {
// 如果返回的不是Object类型数据
if (elementData.getClass() != Object[].class)
// 重新创建一个size大小的数组。
// 并将原来不是Object[]数组的内容，Copy给新的是Object[]的数组
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
// 用空数组代替
this.elementData = EMPTY_ELEMENTDATA;
}
}从上面的分析中看出EMPTY_ELEMENTDATA与DEFAULTCAPACITY_EMPTY_ELEMENTDATA的区别。
EMPTY_ELEMENTDATA表示在我们实例化对象时指定了容量就是0，当添加1个元素后，那么elementData.length=1。
DEFAULTCAPACITY_EMPTY_ELEMENTDATA表示实例化时是无参构造，未指定容量，在调用add方法添加第1个元素后会默认扩容容量为10，即elementData.length=10。
2.3 添加元素
/**
* 直接将元素添加到数组末尾。
*/
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
/**
* 将元素添加到指定index位置。
*/
public void add(int index, E element) {
// 对index进行界限检查
rangeCheckForAdd(index);
ensureCapacityInternal(size + 1); // Increments modCount!!
// native静态方法，原elementData数组的index（包含）之后的数据，复制到目标elementData数组的index + 1之后位置
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
// 将从index开始之后的所有成员后移一个位，将element插入到index位置。
elementData[index] = element;
// 最后size+1
size++;
}
/**
* 将指定集合中的所有元素追加到此列表的末尾。
*/
public boolean addAll(Collection<? extends E> c) {
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(size + numNew); // Increments modCount
System.arraycopy(a, 0, elementData, size, numNew);
size += numNew;
return numNew != 0;
}
/**
* 从指定的位置开始，将指定集合中的所有元素插入到此列表中。
*/
public boolean addAll(int index, Collection<? extends E> c) {
rangeCheckForAdd(index);
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(size + numNew); // Increments modCount
int numMoved = size - index;
if (numMoved > 0)
System.arraycopy(elementData, index, elementData, index + numNew,
numMoved);
System.arraycopy(a, 0, elementData, index, numNew);
size += numNew;
return numNew != 0;
}源码中大量调用了arraycopy()方法，其具体使用可以参考由 System.arraycopy 引发的巩固：对象引用 与 对象 的区别一文。
2.4 删除元素
/**
* 删除列表中指定位置的元素。将任何后续元素移动到左侧（从其索引中减1）。
*/
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;
// 从列表中删除的元素
return oldValue;
}
/**
* 从列表中删除指定元素。
*/
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++)
// 返回true，此列表包含指定的元素
if (o.equals(elementData[index])) {
fastRemove(index);
return true;
}
}
return false;
}
// 它跳过边界检查而不返回移除的值。
private void fastRemove(int index) {
modCount++;
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null;
}
/**
* 从列表中删除所有元素。
*/
public void clear() {
modCount++;
// 把数组中所有的元素的值设为null
for (int i = 0; i < size; i++)
elementData[i] = null;
size = 0;
}
/**
* 从此列表中删除所有索引为fromIndex （包含）和toIndex之间的元素。
*/
protected void removeRange(int fromIndex, int toIndex) {
modCount++;
int numMoved = size - toIndex;
System.arraycopy(elementData, toIndex, elementData, fromIndex,
numMoved);
int newSize = size - (toIndex-fromIndex);
for (int i = newSize; i < size; i++) {
elementData[i] = null;
}
size = newSize;
}
/**
* 从此列表中删除指定集合中包含的所有元素。
*/
public boolean removeAll(Collection<?> c) {
Objects.requireNonNull(c);
// 如果此列表被修改则返回true
return batchRemove(c, false);
}2.5 ArrayList扩容机制
可以发现，ArrayList添加元素时，都会调用ensureCapacityInternal方法。
以add(E e)方法为例：
/**
* 直接将元素添加到数组末尾。
*/
public boolean add(E e) {
// 检查是否需要扩容
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}2.5.1 ensureCapacityInternal() 和 ensureExplicitCapacity()
查看ensureCapacityInternal()方法：
// 获取到满足需求的最小容量
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
private static int calculateCapacity(Object[] elementData, int minCapacity) {
// elementData是空列表
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
// 扩容数组到DEFAULT_CAPACITY(10)
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
// return size+1
return minCapacity;
}
// 判断是否需要扩容
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
if (minCapacity - elementData.length > 0)
//调用grow方法进行真正地扩容
grow(minCapacity);
}- 当添加第1个元素到 ArrayList 中时，minCapacity 为size+1=0，elementData还是空的list，elementData.length=0 ，所有会执行
return Math.max(DEFAULT_CAPACITY, minCapacity);，minCapacity变为10。此时，minCapacity - elementData.length > 0成立，所以会进入grow(minCapacity)方法真正扩容。 - 当添加第2个元素时，minCapacity 为 size+1 =2，由于elementData.length在添加第一个元素后已经扩容成10了。此时，
minCapacity - elementData.length > 0不成立，不会执行grow(minCapacity)方法，即不会扩容。 - 添加第 3、4、5......到第10个元素时，依然不会扩容，数组容量还是为10。
直到添加第11个元素，minCapacity - elementData.length > 0 成立，执行grow 方法进行扩容。
2.5.2 grow()
grow方法是整个ArrayList扩容的核心：
private void grow(int minCapacity) {//11
// oldCapacity为旧容量
int oldCapacity = elementData.length;//10
// 位移运算符比普通运算符的运算快很多。>>表示将oldCapacity右移一位，(oldCapacity >> 1)相当于oldCapacity /2
// 将新容量更新为旧容量的1.5倍
int newCapacity = oldCapacity + (oldCapacity >> 1);
// 若新容量还是小于最小需求容量
if (newCapacity - minCapacity < 0)
// 直接最小需求容量当作数组的新容量
newCapacity = minCapacity;
//如果minCapacity大于最大容量，则新容量则为`Integer.MAX_VALUE`，否则，新容量大小则为 MAX_ARRAY_SIZE 即为 `Integer.MAX_VALUE - 8`。
// 新容量大于MAX_ARRAY_SIZE,
if (newCapacity - MAX_ARRAY_SIZE > 0)
// 执行hugeCapacity()方法
newCapacity = hugeCapacity(minCapacity);
elementData = Arrays.copyOf(elementData, newCapacity);
}
// 比较minCapacity和MAX_ARRAY_SIZE
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0)
throw new OutOfMemoryError();
// minCapacity > MAX_ARRAY_SIZE，新数组的大小为Integer.MAX_VALUE
// 否则，新数组的大小为MAX_ARRAY_SIZE
// MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}由此可知，ArrayList默认扩容大小是原大小的1.5倍左右（oldCapacity为偶数肯定是 1.5 倍，为奇数肯定就是等于1.5倍左右）。
- 如果扩容后的newCapacity仍小于minCapacity，那么就将数组大小调整为minCapacity大小。
- 如果minCapacity的值在MAX_ARRAY_SIZE和Integer.MAX_VALUE之间，那么新数组分配Integer.MAX_VALUE大小，否则分配MAX_ARRAY_SIZE。
">>"（右移运算符）：”>>1“表示右移1位；右移n位相当于除以2的n次方。
2.6 ensureCapacity
从上面源码分析，在使用Arraylist初始化容量时，就会通过一系列逻辑判断后再进行扩容。如果数据量很大，运行效率岂不是很低。
而ensureCapacity()方法，就是让我们预先设置Arraylist的大小，这样就可以大大提高初始化速度了。
public void ensureCapacity(int minCapacity) {
// 以此来判断我们实例化时是否调用无参构造函数。如果不是，minExpand=0；如果是，minExpand=10。
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;
// 我们设置的minCapacity大于minExpand才进行扩容
if (minCapacity > minExpand) {
ensureExplicitCapacity(minCapacity);
}
}最好在 add 大量元素之前用 ensureCapacity 方法，以减少增量重新分配的次数。
下面就来测试一下使用ensureCapacity前后的区别：
public class EnsureCapacityTest {
public static void main(String[] args) {
ArrayList<Object> list = new ArrayList<Object>();
final int minCapacity = 10000000;
long startTime = System.currentTimeMillis();
for (int i = 0; i < minCapacity; i++) {
list.add(i);
}
long endTime = System.currentTimeMillis();
System.out.println("不使用ensureCapacity耗时：" + (endTime - startTime));
list = new ArrayList<Object>();
long startTime1 = System.currentTimeMillis();
list.ensureCapacity(minCapacity);
for (int i = 0; i < minCapacity; i++) {
list.add(i);
}
long endTime1 = System.currentTimeMillis();
System.out.println("使用ensureCapacity耗时：" + (endTime1 - startTime1));
}
}运行结果：
不使用ensureCapacity耗时：2471
使用ensureCapacity耗时：2893 遍历
ArrayList主要支持三种遍历方式：
- foreach循环遍历
Integer value = null;
for (Integer integ:list) {
value = integ;
}- 迭代器遍历
Integer value = null;
Iterator iter = list.iterator();
while (iter.hasNext()) {
value = (Integer)iter.next();
}- 随机访问，通过索引值去遍历
由于ArrayList实现了RandomAccess接口，它支持通过索引值去随机访问元素。
Integer value = null;
int size = list.size();
for (int i=0; i<size; i++) {
value = (Integer)list.get(i);
}4 fail-fast机制
快速失败(fail-fast) 是 Java 集合中的一种错误检测机制。它的特性就是在遍历Java集合时，不允许进行值的修改，否则会抛出ConcurrentModificationException异常。
例如在多线程开发中，线程A正在通过iterator遍历某集合，线程B恰巧对该集合的内容进行了修改，那么线程A继续遍历集合就会抛出ConcurrentModificationException异常，产生fail-fast事件。
查看AbstractList源码：
public abstract class AbstractList<E> extends AbstractCollection<E> implements List<E> {
... ...
// 用来记录List修改的次数：每修改一次(添加/删除等操作)，将modCount+1
protected transient int modCount = 0;
// 返回List对应迭代器。实际上，是返回Itr对象。
public Iterator<E> iterator() {
return new Itr();
}
// Itr是Iterator(迭代器)的实现类
private class Itr implements Iterator<E> {
int cursor = 0;
int lastRet = -1;
// 修改数的记录值。
// 每次新建Itr()对象时，都会保存新建该对象时对应的modCount。
int expectedModCount = modCount;
public boolean hasNext() {
return cursor != size();
}
public E next() {
checkForComodification();
--- omit ---
}
public void remove() {
if (lastRet == -1)
throw new IllegalStateException();
checkForComodification();
--- omit ---
}
final void checkForComodification() {
// 每次遍历List中的元素的时候，都会比较expectedModCount和modCount是否相等。
// 若不相等，则抛出ConcurrentModificationException异常，产生fail-fast事件。
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}
... ...
}可见，ArrayList在添加或者删除元素时，无论是调用add()、remove()还是clear()等其他方法，只要涉及到修改集合中的元素个数时，都会改变modCount的值。
而每当迭代器遍历下一个元素之前，都会检测 modCount 变量是否为 expectedModCount 值。如果在集合被遍历期间修改 modCount 的值，那么 modCount != expectedModCount ，进而抛出 ConcurrentModificationException 异常。
因此，在多线程开发中，建议使用java.util.concurrent包下的线程安全类去取代java.util包下的线程不安全类。比如ArrayList对应的线程安全类为CopyOnWriteArrayList。
特别注意的是，并不是只有在多线程中才会出现fail-fast事件。在单线程下，如果遍历过程中对集合对象的内容进行了修改的话也会触发 fail-fast 机制。
foreach循环也是借助迭代器进行遍历的。
应该避免写出类似这样的代码：
List<String> list = new ArrayList<>();
list.add("a");
list.add("b");
for (String str : list) {
if("b".equals(str)){
list.remove(str);
}
}
