ArrayList源码深度解析
概述
ArrayList是一个顺序的容器，底层实际上是一个数组，可以动态扩容，所以使用起来非常方便，也是程序员非常爱用的一个容器，那它底层的扩容机制是怎么样的呢？是如何添加元素的呢？那我们基于jdk8来一探究竟。
类结构
以下是ArrayList的类结构图：
- RandomAccess 是一个标记接口，用于标记实现该接口的集合支持快速随机访问。
- Serializable 是一个标记接口，用于标记实现该接口的类可以序列化。
- Cloneable 是一个标记接口，用于标记实现该接口的类可以调用 clone 方法，否则会抛异常。
- Iterable 是一个遍历接口，内部提供了支持不同遍历方式的方法，比如顺序遍历迭代器、函数式的 foreach 遍历、并行遍历迭代器。
- Collection 是 java 集合体系的根接口，包含了通用的遍历、修改方法，例如 addAll、removeAll。
- AbstractCollection 是一个抽象类，重写了 Collection 中最基础的方法，减少具体集合类的实现成本，比如 contains、isEmpty、toArray，iterator，但是 add 等需要具体集合类自我实现。
- List 是 java 有序集合的基础接口，除了 Collection 的方法，还有支持倒序遍历的 listIterator 方法、子列表 subList 方法，另外重写 spliterator 方法的实现。
- AbstractList 是一个抽象类，重写了 List 的大部分方法，作用跟 AbstractCollection 类似。
核心机制
我们先了解下ArrayList的一些核心机制，然后通过源码的角度来学生和验证这些核心机制，加强了解。
扩容机制
- ArrayList的底层实现就是一个数组，但我们知道创建数组的时候长度是固定的，所以必须要进行自动扩容。
- 每当向数组中添加元素时，都要去检查添加后元素的个数是否会超出当前数组的长度，如果超出，数组将会进行扩容，以满足添加数据的需求。
- 数组进行扩容时，会将老数组中的元素重新拷贝一份到新的数组中，每次数组容量的增长大约是其原容量的1.5倍。这种操作的代价是很高的，因此在实际使用时，我们应该尽量避免数组容量的扩张。当我们可预知要保存的元素的多少时，要在构造ArrayList实例时，就指定其容量，以避免数组扩容的发生。
FailFast机制
FailFast机制也叫做快速失败机制，它只能被用来检测错误，因为JDK并不保证fail-fast机制一定会发生。当多个线程对同一个集合的内容进行操作时，就可能会产生fail-fast事件。例如：当某一个线程A通过iterator去遍历某集合的过程中，若该集合的内容被其他线程所改变了；那么线程A访问集合时，就会抛出ConcurrentModificationException异常，产生fail-fast事件。
通过记录ArrayList容器的modCount参数来实现。在面对并发的修改时，迭代器很快就会完全失败，而不是冒着在将来某个不确定时间发生任意不确定行为的风险。
源码解析
关键成员变量
/** * 默认的容量为10，也就是一开始创建数组的长度 */ private static final int DEFAULT_CAPACITY = 10; /** * 有参构造缺省空数组 */ private static final Object[] EMPTY_ELEMENTDATA = {}; /** * 无参构造缺省空数组 */ private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; /** * 数组的元素，不是private类型，主要是为了方便内部类的访问 */ transient Object[] elementData; // non-private to simplify nested class access /** * 数组元素的个数 * * @serial */ private int size; /** * 数组的最大容量 */ private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
这里面关键的是elmentData属性，是一个数组，存储Arraylist增改删的元素，印证了ArrayList底层就是一个数组。
- 为什么数组最大容量是Integer.MAX_VALUE - 8，而不是Integer.MAX_VALUE？
可以查看源码的注释，有些虚拟机在数组中保留了一些头信息。避免内存溢出。
- 为什么定义了两个空数组？
主要是为了优化处理，我们可以看到他们是static类型，是被类共享的。如果一个应用中有很多这样ArrayList空实例的话，就会有很多的空数组，无疑是为了优化性能，所有ArrayList空实例都指向同一个空数组。两者都是用来减少空数组的创建，所有空ArrayList都共享空数组。两者的区别主要是用来起区分作用，针对有参无参的构造在扩容时做区分走不同的扩容逻辑，优化性能。
- elementData为什么定义成transient？这样能序列化吗？
Java中transient关键字的作用，简单地说，就是让某些被修饰的成员属性变量不被序列化。有了transient关键字声明，则这个变量不会参与序列化操作，即使所在类实现了Serializable接口，反序列化后该变量为空值。
实际上ArrayList在序列化的时候会调用writeObject()方法，将size和element写入ObjectOutputStream；反序列化时调用readObject()，从ObjectInputStream获取size和element，再恢复到elementData。
而不是通过elementData来序列化，主要原因在于elementData是一个缓存数组，它通常会预留一些容量，等容量不足时再扩充容量，那么有些空间可能就没有实际存储元素，采用上诉的方式来实现序列化时，就可以保证只序列化实际存储的那些元素，而不是整个数组，从而节省空间和时间。
构造方法
- 无参构造方法ArrayList()
// 创建一个容量为10的ArrayList public ArrayList() { // 将elementData元素数组初始化为空数组 this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; }
- 有参构造方法 ArrayList(int)
/** * 构造一个具有指定初始容量的列表 * * @param initialCapacity: 初始化数组的值 */ public ArrayList(int initialCapacity) { //如果初始化的值大于0，则给定elementData一个长度为initialCapacity的数组 if (initialCapacity > 0) { this.elementData = new Object[initialCapacity]; } else if (initialCapacity == 0) { // 如果初始化的值等于0，则初始化为空数组 this.elementData = EMPTY_ELEMENTDATA; } else { //否则（小于0的情况）抛出异常 throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity); } }
- 有参构造方法 ArrayList(Collection<? extends E> c)
//构造一个指定元素的集合 public ArrayList(Collection<? extends E> c) { // 将集合转换为数组并赋值给elementData elementData = c.toArray(); // 如果集合的大小不为0 if ((size = elementData.length) != 0) { // 如果转换后的数组不是泛型(object)，则需要用Arrays的工具转换一下为object数组 if (elementData.getClass() != Object[].class) elementData = Arrays.copyOf(elementData, size, Object[].class); } else { // 否则初始化elementData为一个空数组 this.elementData = EMPTY_ELEMENTDATA; } }
关键方法
- add(E e) 方法
非常重要的一个方法，深入学习这个方法基本就了解ArrayList的一些核心机制。
// 往数组中添加一个元素 public boolean add(E e) { // 确定内部数组容量是否够用,如果不够用需要进行扩容处理，就是在这个方法中 //size是元素数组中数据的个数，因为要添加一个元素，所以size+1 //先判断size+1的这个个数数组能否放得下，就在这个方法中去判断是否数组.length是否够用了。 ensureCapacityInternal(size + 1); // Increments modCount!! // 将数组size++索引的位置设置为元素e elementData[size++] = e; return true; }
// 容量处理的中间方法 private void ensureCapacityInternal(int minCapacity) { ensureExplicitCapacity(calculateCapacity(elementData, minCapacity)); }
// 计算ArrayList的容量大小 private static int calculateCapacity(Object[] elementData, int minCapacity) { // 判断数组是不是空数组 if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { // 如果是空数组(此时minCapacity = 0 + 1 = 1)，和默认的DEFAULT_CAPACITY=10比较，返回大的那个数 return Math.max(DEFAULT_CAPACITY, minCapacity); } // 返回容量 return minCapacity; }
// 用于检查容量以及扩容操作 private void ensureExplicitCapacity(int minCapacity) { // 修改次数记录+1 在父类AbstractList中定义了一个int型的属性：modCount，记录了ArrayList修改的次数 // 主要是用来在并发修改的时候快速失败，提高性能 modCount++; // 判断数组是否够用，如果不够用，则自动扩容 // 1、当初始化的集合为空数组时，此时minCapacity是10，而elementData的长度为0，所以需要扩容 // 2、当初始化的集合不为空时，也就是给定了大小，或已经初始化了元素，此时的minCapacity = 实际数组个数+1，此时判断集合不够用，也需要进行扩容，否则元素会溢出 if (minCapacity - elementData.length > 0) // 扩容处理 grow(minCapacity); }
// 扩容逻辑 private void grow(int minCapacity) { //元素数组的实际长度(即扩充前的数组大小) int oldCapacity = elementData.length; //新的容量，扩容1.5倍赋值给newCapacity( >>为右移运算符，相当于除以2 即oldCapacity/2 ) int newCapacity = oldCapacity + (oldCapacity >> 1); // 如果初始化为空的情况，则将数组扩容为10，此时才是真正初始化元素数组elementData大小为10 if (newCapacity - minCapacity < 0) newCapacity = minCapacity; // 如果1.5倍的数组大小超过了集合的最大长度，则调用hugeCapacity方法，重新计算，也就是给定最大的集合长度 if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity); // 已经确定了大小，就将元素copy到elementData元素数组中~~ elementData = Arrays.copyOf(elementData, newCapacity); }
private static int hugeCapacity(int minCapacity) { // 内存溢出判断 if (minCapacity < 0) throw new OutOfMemoryError(); // 这里的逻辑为：如果需要扩容的大小比数组的最大值都大，就返回Integer,MAX_VALUE(int最大值),否则返回集合的最大值(int最大值-8) return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE; }
- 新增时，如果ArrayList容器的size+1 大于数组的长度，则需要进行扩容
- 扩容底层相当于数组的拷贝操作，将老的数组拷贝到新的数组中，这个过程其实比较消耗性能，所以一开始设置一个合理的数量显得非常重要，尽量避免出现扩容的情况。
2.add(E e) 方法
需要先对元素进行移动，然后完成插入操作，也就意味着该方法有着线性的时间复杂度。
/** * 增加元素到指定下标 * * @param index 下标 * @param element 元素 */ public void add(int index, E element) { // 参数校验，判断是不是存在越界 rangeCheckForAdd(index); // 此方法不再赘述 ensureCapacityInternal(size + 1); // 拷贝数组 System.arraycopy(elementData, index, elementData, index + 1, size - index); // 将指定元素覆盖到指定下标 elementData[index] = element; // 长度size + 1 size++; } /** * 适用于add 和 addAll的校验方法 */ private void rangeCheckForAdd(int index) { if (index > size || index < 0) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); }
- boolean remove(Object o)
根据指定元素删除列表中的元素
// 根据元素o进行删除 public boolean remove(Object o) { // 如果o等于空 if (o == null) { for (int index = 0; index < size; index++) // 如果遇到的第一个是null的元素，快速进行删除，因为arraylist可以存储null if (elementData[index] == null) { fastRemove(index); return true; } } else { for (int index = 0; index < size; index++) // 比较对象的equals方法 // 因此类型变量E对应的类注意重写equlas方法 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) // 将elemenData中index+1及其后面的元素都向前移动一个下标 System.arraycopy(elementData, index+1, elementData, index, numMoved); // 根据上一步的操作, size-1位置的对象向前移动了一个下标 // 如果没有elementData[--size]==null，可能会导致内存泄漏 // 试想，ArrayList被add了100个对象，然后被remove了100次。按照GC的机制来说，100个对象应该可以被GC掉（假设没有对象对象），但是由于还存在ArrayList的实例引用，对应的100个对象就无法删除 elementData[--size] = null; }
- E get(int index)
获取指定位置的元素。
/** * 检查给定的索引是否在范围内。 如果没有，则抛出一个适当的运行时异常。 * @param index : 下标 */ public E get(int index) { // 校验下标有效性 rangeCheck(index); // 返回元素数组中指定index位置的数据 return elementData(index); } private void rangeCheck(int index) { // 如果下标大于实际数组长度（元素数组最后一个数据下标为size-1） if (index >= size) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); }
- 迭代器遍历
// 创建迭代器 public Iterator<E> iterator() { return new Itr(); }
private class Itr implements Iterator<E> { int cursor; // index of next element to return int lastRet = -1; // index of last element returned; -1 if no such // 设置期望的修改次数，也就是创建迭代器那一时刻ArrayList的修改次数 int expectedModCount = modCount; Itr() {} 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; if (i >= elementData.length) throw new ConcurrentModificationException(); cursor = i + 1; return (E) elementData[lastRet = i]; } final void checkForComodification() { // 如果此刻的修改次数和一开始的不一致，抛出ConcurrentModificationException并发修改的异常 if (modCount != expectedModCount) throw new ConcurrentModificationException(); } }
- subList方法
subList方法返回的是SubList对象，不是原来的ArrayList类型。相当于一个子视图，他们本质还是共用底层的数据。
public List<E> subList(int fromIndex, int toIndex) { // 范围验证 subListRangeCheck(fromIndex, toIndex, size); // 创建SubList的对象 return new SubList(this, 0, fromIndex, toIndex); }
private class SubList extends AbstractList<E> implements RandomAccess { private final AbstractList<E> parent; private final int parentOffset; private final int offset; int size; SubList(AbstractList<E> parent, int offset, int fromIndex, int toIndex) { this.parent = parent; this.parentOffset = fromIndex; this.offset = offset + fromIndex; this.size = toIndex - fromIndex; this.modCount = ArrayList.this.modCount; } // 添加元素 public void add(int index, E e) { rangeCheckForAdd(index); // 校验原来的容器是否发生变化，如果发生变化抛出异常 checkForComodification(); parent.add(parentOffset + index, e); this.modCount = parent.modCount; this.size++; } ........ }
在 subList 场景中，高度注意对父集合元素的增加或删除，均会导致子列表的遍历、增加、删除产生 ConcurrentModificationException 异常。
总结
- 增删改查中， 增导致扩容，则会修改modCount, 删除也会修改modCount。 改和查一定不会修改modCount。
- 扩容操作会导致数组复制，批量删除会导致找出两个集合的交集，以及数组复制操作，因此，增、删都相对低效。 而 改、查都是很高效的操作。
- ArrayList是一个线程不安全的容器，如果要使用线程安全的话可以考虑Vector，Collections.synchronizedList 或者CopyOnWriteArrayList。
