基础介绍
ArrayList 底层数据结构就是一个数组：
1、index 表示数组下标，从 0 开始计数，elementDatda 表示数组本身
2、DEFAULT_CAPACITY 表示数组的初始化大小，默认是10
3、size 表示数组的大小，int 类型，没有使用 volatile 修饰，非线程安全
4、modCount 统计当前数组被修改的版本次数，数组结构有变动，就会+1
类注释
1、允许 put null 值，会自动扩容
2、size、isEmpty、get、set、add 等方法的时间复杂度都是O(1)
3、不是线程安全的，多线程情况下，推荐使用线程安全类：Collections#synchronizedList
4、增强 for 循环，或者使用迭代器迭代过程中，如果数组大小被改变，会快速失败，抛出异常
源码解析
1、初始化
三种方法：无参数直接初始化、指定大小初始化、指定初始数据初始化。
源码
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
// 保存数组的容器，默认是null
transient Object[] elementData;
// 无参数直接初始化
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
// 指定大小初始化
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);
}
}
// 指定初始化数据初始化
public ArrayList(Collection<? extends E> c) {
Object[] a = c.toArray();
// 如果给定的集合不为空
if ((size = a.length) != 0) {
// 传入的集合类型为ArrayList时，数组直接地址指向a，否则拷贝数据
if (c.getClass() == ArrayList.class) {
elementData = a;
} else {
elementData = Arrays.copyOf(a, size, Object[].class);
}
} else {
// 给定的集合数据为空时，默认空数组
elementData = EMPTY_ELEMENTDATA;
}
}从源码中可以得到以下几点：
1、ArrayList 无参构造器初始化时，默认大小是空数组，数组大小 10 是在第一次 add 的时候扩容的数组值。
2、指定数据初始化的时候，在传入的数据为空时，依旧会初始化为空数组。当传入的集合类型为ArrayList 时，elementData 会直接使用 toArray 生成的数组。
2、新增和扩容
添加元素时进行了两步操作：
1、判断是否需要扩容
2、elementData 数组赋值，这里是非线程安全的
/**
* Appends the specified element to the end of this list.
*
* @param e element to be appended to this list
* @return <tt>true</tt> (as specified by {@link Collection#add})
*/
public boolean add(E e) {
// 判断数组的大小是否还够存放新数据，不够则扩容，size是当前数组存放元素的个数
ensureCapacityInternal(size + 1);
// 数组赋值，线程不安全
elementData[size++] = e;
return true;
}扩容（ensureCapacityInternal）的源码
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
// 计算数组需要的最小容量
private static int calculateCapacity(Object[] elementData, int minCapacity) {
// 如果是初始化时未指定大小，则使用默认的大小 10
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
// 否则返回存放当前元素需要的最小容量值
return minCapacity;
}
private void ensureExplicitCapacity(int minCapacity) {
// 数组改变的标志+1
modCount++;
// 数组需要的最小容量大于数组的长度，数组需要扩容
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
/**
* Increases the capacity to ensure that it can hold at least the
* number of elements specified by the minimum capacity argument.
*
* @param minCapacity the desired minimum capacity
*/
private void grow(int minCapacity) {
// 记录旧的数组长度
int oldCapacity = elementData.length;
// 新的数组长度等于旧的数组长度的 1.5 倍，oldCapacity >> 1相当于除以 2
int newCapacity = oldCapacity + (oldCapacity >> 1);
// 新的数组长度小于需要的最小容量时，扩容值修改为最小容量值
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
// 新的数组长度超过最大值时，MAX_ARRAY_SIZE 的值为 Integer 表示的最大值-8
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// 数组的复制
elementData = Arrays.copyOf(elementData, newCapacity);
}
private static int hugeCapacity(int minCapacity) {
// 内存溢出
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
// 需要的最小容量超过最大值时，返回Integer 表示的最大值
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}Java 的源码有一些需要注意的点：
1、初始化未指定大小的集合，第一次扩容的大小为 10
2、添加元素时，不管数组有没有扩容，modCount 都会+1
3、数组容量的最大值是 Integer.MAX_VALUE，超过这个值，JVM 就不会给数组分配内存空间了
4、新增元素时，没有对值进行严格的校验，所以 ArrayList 可以添加null值。
源码中值得我们去学习的地方：
1、代码书写很优雅，一个方法只做一件事，便于理解
2、要有边界意识，数组的下标最大不超过 Integer 最大值，最小不能小于 0
3、扩容的本质
ArrayList 中的数组扩容是通过调用 Arrays 的 copyOf 方法。先创建一个符合我们预期容量的新数组，然后把旧数组的元素拷贝过去。通过调用 System.arraycopy 方法进行拷贝，此方法是 native 修饰的方法
/**
* @param src 被拷贝的数组
* @param srcPos 从数组那里开始
* @param dest 目标数组
* @param destPos 从目标数组那个索引位置开始拷贝
* @param length 拷贝的长度
* 此方法是没有返回值的，通过 dest 的引用进行传值
*/
public static native void arraycopy(Object src, int srcPos,
Object dest, int destPos,
int length);4、删除
在源码中关于删除的方法：
public boolean remove(Object o)：删除第一个匹配的元素public E remove(int index)：删除指定位置上的元素，并返回该元素private void fastRemove(int index)：私有方法，被remove(Object o)方法调用public boolean removeAll(Collection<?> c)：从此列表中删除包含在指定集合中的所有元素。public void clear()：清空集合
/**
* 移除此列表中指定位置的元素
*/
public E remove(int index) {
// 数组越界的检查，index 大于 size 时会抛 IndexOutOfBoundsException 异常
rangeCheck(index);
modCount++;
// 当 index 小于 0 时，在这里取值的时会抛出 ArrayIndexOutOfBoundsException 异常
E oldValue = elementData(index);
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // clear to let GC do its work
return oldValue;
}
/**
* 如果指定元素存在，则从此集合中删除第一次出现的指定元素，如果不存在，在保持不变，返回false
*/
public boolean remove(Object o) {
// 如果要删除的元素为 null 时
if (o == null) {
for (int index = 0; index < size; index++)
// 判断元素是否为null
if (elementData[index] == null) {
fastRemove(index);
return true;
}
} else {
for (int index = 0; index < size; index++)
// 使用equals判断元素是否相等
if (o.equals(elementData[index])) {
fastRemove(index);
return true;
}
}
return false;
}
private void fastRemove(int index) {
// 记录数组的结构变化
modCount++;
// 需要移动的元素个数
// size 从 1 开始计算，index 从 0 开始，所以需要 -1
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // clear to let GC do its work
}从源码可以看出一些注意点：
1、新增的时候没有对 null 做校验，删除的时候也是可以删除 null 值的
2、删除所有元素使用的是clear()方法
3、删除的时候，只做了 index 是否大于 size 的判断，index 为负值时在数组取值时抛出异常。小于 0 和大于 size 时的抛出异常不同。
4、元素相等的判断在不为 null 的情况下使用 equals 方法，自定义类型元素的删除要注意 equals 的具体实现。
5、单向迭代器
实现java.util.Iterator接口类，迭代器中定义的几个参数：
int cursor;// 迭代过程中，下一个元素的位置，默认从 0 开始。
int lastRet = -1; // 最后一次迭代时返回的值的索引位置；默认为 -1。
int expectedModCount = modCount;// expectedModCount 表示迭代过程中，期望的版本号；modCount 表示数组实际的版本号。常用的迭代器方法有三个：
hasNext还有没有值可以迭代next如果有值可以迭代，迭代的值是多少remove删除当前迭代的值
hasNext 源码
public boolean hasNext() {
// cursor 表示下一个元素的大小，size 表示实际存放的元素个数，两者相等时，表示没有元素可以便利了
return cursor != size;
}next源码
@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];
}
// 判断是否修改了 elementData 数组
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}源码这一块里面，next 做了两件事，第一判断能不能继续迭代，第二找到需要迭代的值，并为下次迭代做准备。
这里面有个很有意思的点，在判断版本号和 i 是否超过元素个数以后，又做了一次是并发修改的判断。新建了一个本地变量，将地址指向 ArrayList 的数组 elementData。此时 elementData 如果修改地址对取值已经没什么影响了。然后判断 i 是否超过数组长度，保证代码正常运行能取值，但是多线程的情况下，取值不一定是对的。
remove源码
public void remove() {
if (lastRet < 0)
throw new IllegalStateException();
// 判断数组是否被修改
checkForComodification();
try {
ArrayList.this.remove(lastRet);
cursor = lastRet;
// -1 表示元素已经被删除，防止重复删除
lastRet = -1;
// 删除元素会修改modCount，需要给expectedModCount重新复制
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}这里有两点需要注意的：
lastRet = -1的操作是为了防止重复删除- 删除元素成功，数组的 modCount 会改变，需要同步修改 expectedModCount 的值。
6、双向迭代器
除了对java.util.Iterator接口类的实现，ArrayList 还有一个双向迭代器的实现，这个类在继承Iterator接口实现类的基础上，实现了java.util.ListIterator接口。因此又增加了几个逆向迭代方法：
hasPrevious前面还有没有值可以迭代，实现代码类似hasNextnextIndex正向迭代时，下一个迭代的位置previousIndex逆向迭代时，下一个迭代的位置previous逆向迭代时，下一个迭代的值，实现类似nextset(E e)修改当前迭代位置上的元素add(E e)在当前迭代的位置上添加一个元素
双向迭代器的获取方式，一种是调用listIterator()方法直接获取，默认起始位置是 0 ；另一种是调用listIterator(int index)方法指定迭代器的起始位置
public int nextIndex() {
return cursor;
}
public int previousIndex() {
return cursor - 1;
}
// 修改指定迭代位置上的值
public void set(E e) {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();
try {
ArrayList.this.set(lastRet, e);
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
// 在迭代的位置上新增一个值
public void add(E e) {
checkForComodification();
try {
int i = cursor;
ArrayList.this.add(i, e);
cursor = i + 1;
lastRet = -1;
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}7、线程安全
ArrayList 是线程不安全的，是因为 ArrayList 自身的 elementData、size、modConut 在进行各种操作时，都没有加锁。
其他问题
1、为什么引入 modCount 这个变量？
引入 modCount 变量是为了在遍历集合时，判断是否有并发操作改变数据的标志，在快速失败原理上有使用。
2、为什么在添加数据时扩容10，而不是初始化的时候？
节约空间，有时候初始化之后就赋值成别的 list 了
3、elementData 为什么使用 transient 修饰？
因为elementData里面不是所有的元素都有数据，因为容量的问题，elementData里面有一些元素是空的，这种是没有必要序列化的。ArrayList的序列化和反序列化依赖writeObject和readObject方法来实现。可以避免序列化空的元素。
4、new ArrayList(0) 和 new ArrayList(1)的实现
new ArrayList() 在添加第一个元素时会初始化为 10 个空间，new ArrayList(0)在扩容的时候，执行代码newCapacity = oldCapacity + (oldCapacity >> 1)，得到的新数组容量也是 0 ，这时候就会根据实际元素的个数扩容 newCapacity = size + 1。new ArrayList(0)在添加第一个元素后的容量为 1 。
同样的道理，new ArrayList(1)在添加 2 个元素时，扩容的新容量为 1，不满足最低的容量需求，这时候按照最低的容量要求扩容。
5、ArrayList 存放整型元素，调用remove方法是按照下标移除还是按照元素移除？
当集合添加元素为数字时，添加进去的元素自动装箱成Integer类型。我们在删除元素时，如果直接传入参数，会被当作索引处理。
ArrayList list = new ArrayList(0);
list.add(1);
list.add(3);
list.remove(3);
// 输出：class java.lang.Integer
System.out.println(list.get(0).getClass());
// 抛出异常：IndexOutOfBoundsException
list.remove(3);
// 正常删除
list.remove(new Integer(3));6、Java 的快速失败和安全失败
快速失败（fail—fast）
用迭代器遍历一个集合对象时，如果遍历过程中对集合对象的内容进行了修改（增加、删除、修改），则会抛出 ConcurrentModificationException
原理： 迭代器在遍历时直接访问集合中的内容，并且在遍历过程中会判断 modCount 和expectedmodCount是否相等。两者相等的情况下才会进行迭代。集合在被遍历期间如果内容发生变化，就会改变 modCount 的值，然后导致两者不相等，会抛出异常，终止遍历
注意：通过源码可以看出，虽然做了很多判断，但是并不能保证线程安全。如果正好在判断以后修改了 modCount 的值，并且 elementData 的长度满足条件，那么这次迭代还是能正常运行的。因此，不能依赖于这个异常是否抛出而进行并发操作的编程，这个异常只建议用于检测并发修改的 bug。
场景： java.util 包下的集合类都是快速失败的，不能在多线程下发生并发修改（迭代过程中被修改）。
安全失败（fail—safe）yuanmaa
采用安全失败机制的集合容器，在遍历时不是直接在集合内容上访问的，而是先复制原有集合内容，在拷贝的集合上进行遍历。
所以在遍历过程中对原集合所作的修改并不能被迭代器检测到，所以不会触发 ConcurrentModificationException。
场景： java.util.concurrent 包下的容器都是安全失败，可以在多线程下并发使用和修改。
7、ArrayList 的扩容为什么是 1.5 倍？
扩容参数为 (1, 2) 之间比较好。
假设扩容参数为 x，当 x >= 2 时，每次扩展的新尺寸必然刚好大于之前分配的总和
也就是说之前的内存空间都不能进行复用。
IF x = 2 :
caps: 1 2 4 8 16 32
---
1
12
1234
12345678
123456789012345
12345678901234567890123456789012
IF x = 1.5 :
caps: 1 2 3 4 6 9 13 19 28
---
1
12
123
1234
123456
123456789
1234567890123
1234567890123456789
1234567890123456789012345678可以看到，k = 1.5 在几次扩展之后，可以重用之前的内存空间。
