面试官：说说你对ArrayList的了解……
整体架构
ArrayList 整体架构就是一个数组结构：
- index 表示数组下标，从 0 开始计数，elementDatda 表示数组本身
DEFAULT_CAPACITY表示数组的初始化大小，默认是10- size 表示数组的大小，int 类型，没有使用 volatile 修饰，非线程安全
- modCount 统计当前数组被修改的版本次数，数组结构有变动，就会
+1
类注释
- 允许 put null 值，会自动扩容
- size、isEmpty、get、set、add 等方法的时间复杂度都是
O(1) - 不是线程安全的，多线程情况下，推荐使用线程安全类：
Collections#synchronizedList - 增强 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; } }
从源码中可以得到以下几点：
- ArrayList 无参构造器初始化时，默认大小是空数组，数组大小 10 是在第一次 add 的时候扩容的数组值。
- 指定数据初始化的时候，在传入的数据为空时，依旧会初始化为空数组。当传入的集合类型为ArrayList 时，elementData 会直接使用 toArray 生成的数组。
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 的源码有一些需要注意的点：
- 初始化未指定大小的集合，第一次扩容的大小为 10
- 添加元素时，不管数组有没有扩容，modCount 都会
+1 - 数组容量的最大值是 Integer.MAX_VALUE，超过这个值，JVM 就不会给数组分配内存空间了
- 新增元素时，没有对值进行严格的校验，所以 ArrayList 可以添加
null值。
源码中值得我们去学习的地方：
- 代码书写很优雅，一个方法只做一件事，便于理解
- 要有边界意识，数组的下标最大不超过 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 }
从源码可以看出一些注意点：
- 新增的时候没有对 null 做校验，删除的时候也是可以删除 null 值的
- 删除所有元素使用的是
clear()方法 - 删除的时候，只做了 index 是否大于 size 的判断，index 为负值时在数组取值时抛出异常。小于 0 和大于 size 时的抛出异常不同。
- 元素相等的判断在不为 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、线程安全
ArrayList 是线程不安全的，是因为 ArrayList 自身的 elementData、size、modConut 在进行各种操作时，都没有加锁。要想保证线程安全，需要我们手动加锁，或者使用一些线程安全的集合类。
