ArrayList源码刨析
1.概述
ArrayList 是基于数组实现的，并且支持 动态扩容 的动态数组。相比于数组而言，因为其支持 自动扩
容 的特性，成为我们在开发中最常用的集合类之一。
本篇的讲解是基于 JDK1.8 ，话不多说， 就让我们翻开 ArrayList 的源代码，遨游一番吧~
Let’s GO !!!
2.类图
从类图中我们可以看出， ArrayList 实现了4个接口和继承了1个抽象类；4个接口分别为：
List 接口，主要提供数组的添加、删除、修改、迭代遍历等操作。
1 Cloneable 接口，表示ArrayList支持克隆。
2 RandomAccess 接口，表示ArrayList支持 快速 的随机访问。
3 Serializable 接口，表示ArrayList支持序列化的功能。
继承的抽象类为 AbstractList ，主要提供的是 迭代遍历 相关的操作；如果我们单纯看 List -->
AbstractList --> ArrayList 这一实现/继承关系来看的，是不是有一种 模板方法模式 的感觉呢？
List 接口定义了操作行为， AbstractList 抽象类提供了可重用的 算法骨架 ；而最终的 ArrayList
实现类根据自己的情况自定义实现接口。
注意：实际上 ArrayList 大量重写了 AbstractList 抽象类提供的方法实现；所以 AbstractList 对
ArrayList 来说意义不大，但不过 AbstractList 的其他很多子类享受到了这个福利。
3.源码解析
先来看看源码的方法
3.1属性
ArrayList 的属性很少，只有2个属性： elementData 和 size ；其中 elementData 代表的是存放
元素的数组；而 size 代表的是 elementData 数组中元素的数量。比如下图所示： elementData 数
组的长度是8，但是只存放了4个元素，这时候 size 属性就是4。
我们在使用 ArrayList 的时候会经常调用其 size() 方法，返回的就是 elementData 数组中 已使用
的元素的数量，也即是当前的 4；并且当我们新添加元素的时候， size 所指代的也恰巧是新元素的下标
(数组下标从0开始)
3.2 构造方法
ArrayList 一共有3个构造方法，分别如下所示。
1. ArrayList(int initialCapacity)
ArrayList(int initialCapacity) 构造方法，根据传入的 initialCapacity 初始化容量来创建
elementData 数组。如果我们在使用 ArrayList 的时候，预先知道元素的数量，应该尽可能的使用该
构造方法，这样可避免数据扩容，从而提升性能，同时也是合理的利用内存空间（一点不浪费~）。
这里需要留意的是：当初始化容量 initialCapcity 为 0 的时候，使用了一个 EMPTY_ELEMENTDATA
对象，查看源码可知其定义： private static final Object[] EMPTY_ELEMENTDATA = {} 是一个
空数组。在添加元素的时候，会进行扩容创建需要的数组。
2. ArryaList()
无参构造方法，平时使用的时候，如果你的IDEA有安装 sonarLint 扫描，会被提示：创建集合的时候
要指定初始化容量噢~
无参构造方法使用了 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 对象，查看源码可知其定义： private
static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {} 是一个空数组。
似乎有朋友会有疑问：“我之前学习的时候被灌输的是：当未指定初始化大小的时候，ArrayList默认的大
小是10呀！”
这句话一定程度上来说是没问题的，只是缺失了一些补充描述：当未指定初始化大小的时候，ArrayList
先是初始化为一个空数组；但在首次添加元素时，ArrayList才会初始化为一个容量为10的数组。这么做
的原因是节省内存，一些场景可能只是单纯的定义了数组并没有真实的使用，直接初始化容量为10的数
组会造成不必要的浪费。
细心的朋友可能会有疑问：“既然都是空的数组，那为什么不直接使用 EMPTY_ELEMENTDATA 空数组；而
是要重新定义一个新的空数组 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 呢？”
别急，正所谓：“存在即是合理。” 设计者这么做肯定有其特殊的考虑，后面在介绍 数组扩容 的时候会详
细介绍两者的不同； DEFAULTCAPACITY_EMPTY_ELEMENTDATA 的首次扩容是 10，
EMPTY_ELEMENTDATA 的首次扩容是按照1.5倍扩容，从0开始；两者的起点不同。
3. ArrayList(Collection<? extends E> c)
ArrayList(Collection<? extends E> c) 构造方法，使用传入的集合 c 作为 ArrayList的
elementData
当 elementData 数组不空的时候，有一个类型转换的过程，因为 elementData 是 Object[] 类型的
数组。
3.3 新增元素
新增元素的方法主要有如下4个，分别为：
public boolean add(E e) 在数组后面 顺序 新增一个元素
public void add(int index, E element) 在指定 index 位置添加元素
public boolean addAll(Collection<? extends E> c) 在数组后面 顺序 添加多个元素
public boolean addAll(int index, Collection<? extends E> c) 在指定 index 位置，添加多个元素
1. public boolean add(E e)
继承于 AbstractList 抽象类，在数组后面顺序添加单个元素。
方法只有3句代码，看起来比较简单；主要关注一下 ensureCapacityInternal 方法做了什么事情；，
经过上面的介绍我们知道，ArrayList的底层是使用数组实现，并且其特性是支持动态扩容的；那么当我
们新增元素的时候应该需要考虑： 现有的数组容量是否支持新增元素，如果容量不满足，则要考虑扩容操作 。
我们来看看JDK的设计者是咋做的~
STEP -1 首先是 ensureCapacityInternal(int minCapacity) 方法，该方法主要功能：**确保数组内
部容量足以满足本次添加元素操作。**
方法实现上首先是调用了 calculateCapacity(Object[] elementData, int minCapacity) 方法，
计算满足本次新增操作所需的容量，然后调用 ensureExplicitCapacity(int minCapacity) 方法，
保证容量足够。
STEP -2 然后我们来看看 calculateCapacity(Object[] elementData, int minCapacity) 方法是
如何计算本次新增操作所需的容量的。
如果 elementData 是 DEFAULTCAPACITY_EMPTY_ELEMENTDATA ——没有指定初始化容量时；则会判断
是最小容量 minCapacity 和 DEFAULT_CAPACITY 的大小，取大值。
STEP -3 ensureExplicitCapacity 如何确保数组容量足够本次新增操作的？ 由代码可以看出，当所需
的最小容量 minCapacity 大于 elementData.length 数组长度的时候，则触发 grow() 执行扩容。
STEP -4 看看 grow 是咋扩容的~
经过一轮讲解，我们大体上知道 ArrayList 是如何新增元素的，首先计算出新增元素所需要的最小容
量，然后判断当前 elementData 数组是否支持本次新增操作（容量是否足够），当容量不足的时候则
触发扩容机制，将原有数组的元素拷贝到新数组上，然后往后追加新的元素。
接下来我们再来看看剩下的几个新增元素的方法
2. public void add(int index, E element)
public void add(int index, E element) 方法继承于 AbstractList 抽象类，在指定 index 位
置新增元素 element 。
源码如下：
方法比较简单，首先是参数的合法性检查，然后就是上面介绍的 ensureCapacityInternal 方法，用
以确保数组容量满足本次新增操作；需要额外讲解的可能是 System.arraycopy() 方法。
System.arraycopy(Object src, int scrPos, Object desc, int destPos, int length) 方
法，用于将指定源数组中的元素从指定位置到目标数组的指定位置
src：源数组
srcPos：源数组复制的起始位置
desc：目标数组
descPos：目标数组填充数据的起始位置
length：要复制源数组的元素数量
例如
3. public boolean addAll(Collection<? extends E> c)
public boolean addAll(Collection<? extends E> c) 继承于 AbstractCollection 抽象类，在
数组后面 顺序 添加多个元素。当我们确定会添加多个元素的时候，建议使用该方法而不是单个元素逐个
的添加，避免可能多次扩容造成的性能下降。
源码如下：
代码相对比较简单，和 add(E e) 很类似，只不过是将添加1个元素变成了添加多个元素罢了~
4. public boolean addAll(int index, Collection<? extends E> c)
public boolean addAll(int index, Collection<? extends E> c) 方法继承于 AbstractList
抽象类，用以在指定 index 位置添加多个元素
代码相对比较简单，首先还是先进行容量可达操作，让数组的容量满足本次的扩容操作；其次是因为需
要在 index 位置新增多个元素，则原来在 index 位置后的的元素都应该往后顺延 c.length 个位置。
