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它的值都会加1protected 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); } }参考
- ArrayList源码解析
- 由 System.arraycopy 引发的坚固：对象援用 与 对象 的区别
- Java 汇合系列03之 ArrayList具体介绍(源码解析)和应用示例
- Java 汇合系列04之 fail-fast总结(通过ArrayList来阐明fail-fast的原理、解决办法)