ArrayList概述
ArrayList是我们常用的集合类，是基于数组实现的。不同于数组的是ArrayList可以动态扩容。
ArrayList 是 java 集合框架中比较常用的数据结构了。继承自 AbstractList，实现了 List 接口。底层基于数组实现容量大小动态变化。允许 null 的存在。同时还实现了 RandomAccess、Cloneable、Serializable 接口，所以ArrayList 是支持快速访问、复制、序列化的。
- 注：本文解析的 ArrayList 源代码基于 Java 1.8
成员变量
/**
* 默认初始容量大小为 10;
*/
private static final int DEFAULT_CAPACITY = 10;
/**
* 这是一个共享的空的数组实例，当使用 ArrayList(0) 或者 ArrayList(Collection<? extends E> c)
* 并且 c.size() = 0 的时候 elementData 数组讲指向这个实例对象。
*/
private static final Object[] EMPTY_ELEMENTDATA = {};
/**
* 另一个共享空数组实例，在第一次 add 元素的时候将使用它来判断数组大小是否设置为
* DEFAULT_CAPACITY 默认初始大小
*/
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
/**
* 真正装载集合元素的底层数组 无法被 Serializable 序列化
*/
transient Object[] elementData;
/**
* 实际元素个数
*/
private int size;
/**
* 记录ArrayList结构变化的次数。主要使用是在 Iterator，是防止在迭代的过程中集合被修改。
*/
protected transient int modCount = 0;
elementData是被关键字transient修饰的。我们知道被transient修饰的变量，是不会参与对象序列化和反序列化操作的。而我们知道ArrayList实现了java.io.Serializable，这就表明ArrayList是可序列化的类，这里貌似出现了矛盾。
ArrayList在序列化和反序列化的过程中，有两个值得关注的方法：（writeObject和 readObject：)
writeObject会将ArrayList中的size和element数据写入ObjectOutputStream。readObject会从ObjectInputStream读取size和element数据。
之所以采用这种序列化方式，是出于性能的考量。因为ArrayList中elementData数组在add元素的过程，容量不够时会动态扩容，这就到可能会有空间没有存储元素。采用上述序列化方式，可以保证只序列化有实际值的数组元素，从而节约时间和空间。
构造函数
无参构造函数
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
构造一个初始容量大小为 initialCapacity 的 ArrayList
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);
}
}
使用指定 Collection 来构造 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;
}
}
将 Collection 转化为数组并赋值给 elementData，把 elementData 中元素的个数赋值给 size。
如果 size 不为零，则判断 elementData 的 class 类型是否为 Object[]，不是的话则做一次转换。
如果 size 为零，则把 EMPTY_ELEMENTDATA 赋值给 elementData，相当于new ArrayList(0)
- 无参构造函数JDK注释是说构造一个容量大小为 10 的空的 list 集合，但构造函数了只是给 elementData 赋值了一个空的数组，其实是在第一次添加元素时容量扩大至 10 的。需要注意size除了指定Collection构造之外默认是0。
添加元素add方法
/**
* 将指定元素添加到集合（底层数组）末尾
*/
public boolean add(E e) {
//检查当前底层数组容量，如果容量不够则进行扩容（当前需要的最小的容量为size + 1）
ensureCapacityInternal(size + 1);
//将数组添加一个元素，size 加 1
elementData[size++] = e;
return true;
}
扩容机制
// 扩容检查
private static int calculateCapacity(Object[] elementData, int minCapacity) {
// 如果是无参构造方法构造的的集合，第一次添加元素的时候会满足这个条件 minCapacity 将会被赋值为 10
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
// 其它情况直接返回minCapacity
return minCapacity;
}
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
//当需要的最小容量 大于了 此时底层数据的长度 进行扩容
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
private void grow(int minCapacity) {
int oldCapacity = elementData.length;
//oldCapacity >> 1 等价于 oldCapacity / 2 所以新容量为当前容量的 1.5 倍
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
//使用 Arrays.copyOf 构建一个长度为 newCapacity 新数组 并将 elementData 指向新数组
elementData = Arrays.copyOf(elementData, newCapacity);
}
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0)
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
每次扩容的大小为原来大小的1.5倍（当然这里没有包含 1.5倍后大于 MAX_ARRAY_SIZE 的情况）扩容的过程其实是一个将原来元素拷贝到一个扩容后数组大小的长度新数组中。所以 ArrayList 的扩容其实是相对来说比较消耗性能的。不是每次Add元素的时候就要扩容的，而是当扩容检查之后需要的时候才进行扩展空间。
获取元素get方法
public E get(int index) {
//判断 index >= size 是否越界
rangeCheck(index);
// 返回指定位置的元素
return elementData(index);
}
由于 ArrayList 底层是基于数组实现的，所以获取元素就相当简单了，直接调用数组随机访问即可。
替换元素set方法
public E set(int index, E element) {
// 角标越界检查
rangeCheck(index);
// 下标取数据注意这里不是elementData[index] 而是 elementData(index) 方法
E oldValue = elementData(index);
// 将 index 位置设置为新的元素
elementData[index] = element;
// 返回之前在 index 位置的元素
return oldValue;
}
删除元素remove方法
public E remove(int index) {
rangeCheck(index);
modCount++;
E oldValue = elementData(index);
// 需要移动的元素个数
int numMoved = size - index - 1;
if (numMoved > 0)
//采用拷贝赋值的方法将 index 之后所有的元素 向前移动一个位置
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
// 将 element 末尾的元素位置设为 null（size自减1 末尾元素置为null） 让gc回收
elementData[--size] = null;
return oldValue;
}
/**
* 删除指定元素，如果它存在则返回 true，如果不存在返回 false。
* 更准确地说是删除集合中第一出现 o 元素位置的元素 ，
* 也就是说只会删除一个，并且如果有重复的话，只会删除第一个次出现的位置。
*/
public boolean remove(Object o) {
// 如果元素为空则只需判断 == 也就是内存地址
if (o == null) {
for (int index = 0; index < size; index++)
if (elementData[index] == null) {
//得到第一个等于 null 的元素角标并移除该元素 返回 ture
fastRemove(index); //fastRemove(index)的逻辑和 remve(index)一样
return true;
}
} else {
// 如果元素不为空则需要用 equals 判断。
for (int index = 0; index < size; index++)
if (o.equals(elementData[index])) {
//得到第一个等于 o 的元素角标并移除该元素 返回 ture
fastRemove(index);
return true;
}
}
return false;
}
删除元素说白了就是将从 index（要删除的元素索引位置） + 1 开始向后所有的元素都向前挪一个位置。然后将数组的最后一个位置空，size - 1。如果 index 是最后一个元素那么就直接将数组的最后一个位置空，size - 1即可。 （size在集合改变的时候是变化的 ，警惕for循环的时候删除元素没有达到预想的结果或者数组越界异常）
迭代器 iterator
有使用过集合的都知道，在用 for 遍历集合的时候是不可以对集合进行 remove操作的，因为 remove 操作会改变集合的大小size。从而容易造成结果不准确甚至数组下标越界，更严重者还会抛出 ConcurrentModificationException。
private class Itr implements Iterator<E> {
int cursor; // 对照 hasNext 方法 cursor 应理解为下次调用 next 返回的元素 初始为 0
int lastRet = -1; // 上一个返回的角标
int expectedModCount = modCount; //初始化的时候将其赋值为当前集合中的操作数
//是否还有下一个元素 cursor == size 表示当前集合已经遍历完了 所以只有当 cursor 不等于 size 的时候 才会有下一个元素
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;
// 由于多线程的问题这里再次判断是否越界，如果有异步线程修改了List（增删）这里就可能产生异常
if (i >= elementData.length)
throw new ConcurrentModificationException();
cursor = i + 1;
// 最终返回 集合中对应位置的元素，并将 lastRet 赋值为已经访问的元素的下标
return (E) elementData[lastRet = i];
}
public void remove() {
// 如果操作者没有调用 next 方法就调用了 remove 操作，lastRet 等于 -1的时候抛异常
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();
try {
// 调用删除元素的方法 移除上次调用 next 访问的元素
ArrayList.this.remove(lastRet);
cursor = lastRet;
lastRet = -1;
// 修改操作数期望值， modCount 在调用集合的 remove 的时候被修改过了。
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}
next 方法是我们获取集合中元素的方法，next 返回当前遍历位置的元素，如果在调用 next 之前集合被修改，并且迭代器中的期望操作数并没有改变，将会引发ConcurrentModificationException。next 方法每次调用 checkForComodification 来检验这个条件是否成立。
只有 Iterator 的 remove 方法会在调用集合的 remove 之后让 期望 操作数改变使expectedModCount与 modCount 再相等，所以是安全的。
调用 remove 之前必须先调用 next。因为 remove 开始就对 lastRet 做了校验。而 lastRet 初始化时为 -1。
next 之后只可以调用一次 remove。因为 remove 会将 lastRet 重新初始化为 -1
总结
1）ArrayList 底层是一个动态扩容的数组结构, 因此在get的时候效率高，而add或者remove的时候，效率低.
2）ArrayList 每次扩容需要增加1.5倍的容量, 扩容底层是通过 Arrays.CopyOf 和 System.arraycopy 来实现的。每次都会产生新的数组，和数组中内容的拷贝，所以会耗费性能，所以在多增删的操作的情况可优先考虑 LinkList 而不是 ArrayList。
3）允许存放（不止一个） null 元素，允许存放重复数据，存储顺序按照元素的添加顺序
4）ArrayList 并不是一个线程安全的集合。如果集合的增删操作需要保证线程的安全性，可以考虑使用 CopyOnWriteArrayList 或者使collections.synchronizedList(List l)函数返回一个线程安全的ArrayList类.
如果需要边遍历边 remove ，必须使用 iterator。且 remove 之前必须先 next，next 之后只能用一次 remove。