参考笔记：
java ArrayList源码分析（深度讲解）-CSDN博客
目录
（7）逐层返回，第一次扩容elementData数组完毕（0 ——> 10）
1.前言
本篇博文是对单列集合 List 的实现类 ArrayList 的内容补充。之前在 List 集合的详解篇，只是拿 ArrayList 演示了 List 接口中的常用方法，并没有对它进行深究。但这正是本文要做的内容
up会利用 Debug 来一步一步地剖析 ArrayList 底层的扩容机制到底是如何实现的。 重点是空参构造器构造ArrayList对象后，底层扩容机制的详细实现
注意 : ①解读源码需要扎实的基础，比较适合希望深究的同学； ② 不要眼高手低，看会了不代表你会了，自己能全程 Debug下来才算有收获； ③ 本篇博文对 ArrayList 源码的解读基于主流的 JDK 8.0 的版本
2. ArrayList简介
ArrayList 类是单列集合 List 接口的一个实现类，它的本质是一个可以动态修改的数组。 ArrayList 位于 java.util.ArrayList 包下，其类的定义如下：
3. ArrayList类的底层实现
① ArrayList 类在底层是由数组来实现的，ArrayList 类源码中维护了一个 Object 类型的数组 elementData，用于存储 ArrayList 集合中的元素
关于 transient 关键字，transient 本身有 "转瞬即逝、短暂的" 的意思，被 transient 关键字修饰的程序元素不可被序列化
② 使用空参构造来创建 ArrayList 类对象时，elementData 数组的初始容量为 0 。第一次添加元素时，将该数组容量扩容为 10 。如需再次扩容，则将 elementData 数组的当前容量扩大 1.5 倍
③ 使用指定数组初始容量大小的带参构造来创建 ArrayList 类对象时，elementData 数组的初始容量即为传入形参的指定容量。如果需要扩容，则直接将该数组当前容量扩大 1.5 倍
4. ArrayList的源码Debug
4.1 使用空参构造
用以下代码为演示，来进行 Debug 操作，代码如下 :
import java.util.ArrayList;
public class demo {
public static void main(String[] args) {
//演示 : Debug ArrayList空参构造，以及数组扩容的全流程
//1.通过空参构造创建一个ArrayList类对象
ArrayList arrayList = new ArrayList();
System.out.println("使用空参构造创建的集合对象 = " + arrayList);
//2.利用for循环向集合对象中添加10个元素（0~9）
for (int i = 0; i < 10; i++) {
arrayList.add(i); //此处有自动装箱，即 int -> Integer
}
System.out.println("添加十个元素后，当前集合 = " + arrayList);
//3.如果按照理论，在向集合对象中添加第11个元素时，底层的数组需要扩容 10 -> 15（1.5倍）
arrayList.add("这是集合的第十一个元素捏.");
arrayList.add("这是集合的第十二个元素捏.");
arrayList.add("这是集合的第十三个元素捏.");
arrayList.add("这是集合的第十四个元素捏.");
arrayList.add("这是集合的第十五个元素捏.");
//4.再次测试ArrayList类底层数组的扩容机制 （10 ---> 15 ---> 22）
arrayList.add("这是集合的第十六个元素捏.");
System.out.println("添加十六个元素后，当前集合 = " + arrayList);
}
}（1）开始Debug
首先，进入 Debug 界面，并在第 6 行的无参构造调用行，跳入 ArrayList 类无参构造，如下 GIF 图所示 :
（2）初始化底层elementData数组为空数组
跳入 ArrayList 无参构造，可以看到，它将用于存储集合元素的 elementData 数组进行了初始化。等号右边的 "DEFAULTCAPCITY_EMPTY_ELEMENTDATA" 直译过来就是 "默认容量空的elementData数组" ，可以根据 Ctrl + b/B 查看 ArrayList 中该常量的源码，如下 :
可以看到，这个所谓的 "默认容量空的elementData数组" 名副其实，确实是一个空的数组，而且与 ArrayLis t中用于存储集合元素的 elementData 数组一样都是 Object 类型
接下来，我们跳出这个无参构造，进入 for 循环，并跳入第一个元素的 add 方法
（3） 对add方法中的实参进行自动装箱
第一次跳入 add 方法，会先跳到 valueOf 方法中，对要添加的 int 类型进行装箱操作。如下图所示 :
这里不用管它，直接选择跳出，并准备第二次跳入 add 方法
第一次跳出 add 方法后，该行代码仍然标注着高亮，表示此行代码还未执行完毕。我们第二次跳入 add 方法
（4） 进入add方法
第二次跳入 add 方法，我们来到了真的"add"方法，如下 :
形参列表的 "e" 代表了当前要添加的元素，根据我们上面给出的代码，for循环要向集合对象中添加 0~9 这 10 个元素，这是 for 循环的第一次循环，要添加元素 0，因此可以看到，此时 e = 0
第一行调用的函数是 ensureCapcityInternal (minCapacity：size + 1) ，"size" 表示当前集合中的元素个数，此时的 size = 0 。该函数的作用是：确定是否需要对 elementData 数组进行扩容。因为我们当前正在执行添加操作嘛，所以这里传入的参数为 minCapacity： "size + 1 " 就表示要把该元素添加进去，所需的数组的最小长度
第二行就是简单的赋值操作了，把当前元素 e 添加到数组中，然后 size++
下面我们进入 ensureCapcityInternal (minCapacity：size + 1) 方法看看到底这个扩容机制到底是怎么个事
（5）进入ensureCapcityInternal 方法
进入 ensureCapcityInternal 方法，其代码如下：
可以看到，该方法中又调用了两个方法 ensureExplicitCapacity、calculateCapacity，真是跟长了包皮一样，套来套去真的烦，但是不要急躁，这里涉及到的代码都不是很难
我们先进入内层调用的函数 calculateCapacity（elementData，minCapacity）看到底做了啥：
可以看到第一条语句是 if（elementData == DEFAULTCAPCITY_EMPTY_ELEMENTDATA）
，判断数组是否为空数组，如果是的话就 return Math.max（DEFAULT_CAPACITY，minCapacity），DEFAULT_CAPACITY = 10，见名知意，它表示的意思就是：默认的数组长度为 10，源码中也有注释，如下：
而 minCapicity（数组的最小容量）= 1，代表的是要把该元素添加进去，所需的数组的最小长度。所以这个 if 语句很明显的就是用于第一次扩容的代码。我们这里的返回值就是 10
回到 ensureCapcityInternal 方法，下面就是进入 ensureExplicitCapacity 方法了：
modCount 属性用于保存你修改集合的次数，用来防止有多个线程修改它，多个线程修改时会抛出异常，这里我们不用管它
下面的 if 判断语句就是利用前面得到的所需的最小数组容量 minCapacity 和当前数组的容量elementData.length 作一个比较，如果发现当前数组的容量无法满足所需的最小数组容量 minCapacity ，那就要调用 grow 方法开始真正意义上的扩容了
这里 minCapacity = 10，elementData.length = 0，所以需要调用 grow 方法完成数组扩容
（6） 进入grow方法
private void grow(int minCapacity) {
//minCapacity：10
//记录当前数组的容量，由于此时还没有存储元素，所以为0
int oldCapacity = elementData.length;
/*
核心扩容算法：原来容量的 + 原来容量的一半（即原容量的1.5倍）,但第一次扩容的时候这里的newCapacity = 0
因为第一次扩容的时候 oldCapacity = 0 嘛。但不用担心，后面紧跟着的if语句就是用来应对这种情况的
*/
int newCapacity = oldCapacity + (oldCapacity >> 1);
//确保新容量newCapacity大于等于最小容量minCapacity，所以第一次扩容时 newCapacity = 10
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
//下面这个if语句不用管也没事，一般都不会搞这么大容量的列表
//判断新容量是否超过了Integer.MAX_VALUE - 8
if (newCapacity - MAX_ARRAY_SIZE > 0)
//如果超过了，则将新容量赋值为Integer.MAX_VALUE
newCapacity = hugeCapacity(minCapacity);
//拷贝出一个新数组，新数组的容量就是前面计算的newCapacity，扩容完毕
elementData = Arrays.copyOf(elementData, newCapacity);
}不要因为走得太远而忘记了我们为什么出发。我们一路追追追，只有一个目的：elementData数组目前是个空数组，要添加第一个元素 0 进入，必须先扩容，因此通过上述代码确定最终的 elmentData 数组长度为 newCapacity = 10，第一次扩容完毕
（7）逐层返回，第一次扩容elementData数组完毕（0 ——> 10）
grow 函数执行完毕，返回到 ensureExplicitCapacity 函数，如下：
可以看到， elementData 数组已经由原来的 "Object[0]@512" ---> "Object[10]@514" ，这也可以验证我们上文提到的 "当我们使用空参构造来创建 ArrayList 类对象时，elementData 数组的初始容量为 0 ，第一次添加元素时，将该数组扩容为 10 "。这里还需要注意的是扩容之后的数组是一个新的数组，是存储在不同地址空间的，所以 @512 ---> @514
执行完 ensureExplictitCapacity 方法，接着返回到 ensureCapacityInternal 方法，如下：
执行完 ensureCapacityInternal 方法，就回到了一开始的 add 方法了，然后是执行 elementData[size++] = e ，把当前元素 e 加入到数组中，如下 GIF 图所示：
可以看到第一个元素 e = 0 成功地被添加进了 elementData 数组，size 也更新为 1，即当前 ArrayList 集合中的元素个数为 1
接着返回到测试类中，如下：
（8）向集合中添加第二个元素(不需要扩容)
第一次扩容完成后，elementData 数组的长度由 0 ---> 10 ，因此， for 循环中后续几个元素的添加都不再需要扩容。以第二个元素的添加为例，这里再过一遍，加深印象，这次主要是体验一下流程，不会像第一次一样描述得那么细致了
如下 GIF 图所示，随着循环变量i的自增，for 的第一次循环顺利结束，第二次循环开始，向集合中添加第二个元素 1 :
可以看到，还是老规矩，需要先将 int 类型的数据 1 做装箱处理
接着，再次跳入 add 方法，如下图所示 :
跟我们前面提到的一样，需要先执行 ensureCapacityInternal 函数确定数组是否需要扩容，之后再将元素 e 加入到数组中，size++
追入 ensureCapacityInternal 方法，这里我以 GIF 图展示，不然篇幅会太长：
可以看到，这里计算得到的 minCapacity = 2 ，即加入该元素所需的数组的最小长度 minCapacity = 2，而在前面我们第一次 add 时，已经将数组的长度扩容为 10 了，所以 elementData.length = 10
因此，不会进入 grow 函数，即不需要对数组进行扩容操作
执行完 ensureCapacityInternal 后，回到 add 方法，将当前元素 e = 1 加入到数组中，然后更新 size = 2，如下 GIF 所示：
（9）将集合中的元素添加到10个（达到第一个临界点）
之后的 8 次循环(向集合中添加 2~9 这 8 个数)，流程均与第二次循环相同，我们直接一笔带过，如下 GIF 图所示 :
（10）集合的第二次扩容开始
因为第一次对 elementData 数组进行扩容时，默认只从 0 ---> 10 。而 for 循环结束后，我们已经向集合对象中添加了 10 个元素，即 ArrayList 底层的 elementData 数组已被装满。现在想添加第 11 个元素，就需要对 elementData 数组进行第二次扩容，先说结论，扩容后的数组容量扩大了 1.5 倍。即第二次扩容之后，elementData 数组为：10 --> 10 + 10 / 2 = 15
先跳入 add 方法，看看会发生什么，如下图所示 :
可以看到，由于从第 11 个元素开始，均为 String 类型，String 本身就是引用类型，因此不需要"装箱"的操作，所以直接跳入了 add 方法
跳入 ensureCapacityInternal ，判断是否需要对数组进行扩容，如下 GIF 所示：
可以看到，这里计算得到的 minCapacity = 11 ，即加入该元素所需的数组的最小长度minCapacity = 11，而当前的数组我们只在第一次 add 的时候扩容过一次，即将数组的长度扩容为10，所以此时 elementData.length = 10 ，所以需要执行 grow 函数对数组进行扩容
进入 grow 函数，对数组进行扩容：
private void grow(int minCapacity) {
//minCapacity：11
//记录当前数组的容量，oldCapacity = 10
int oldCapacity = elementData.length;
/*
核心扩容算法：原来容量的 + 原来容量的一半（即原容量的1.5倍）
扩容之后的数组容量：newCapacity = 10 + 10/2 = 15
*/
int newCapacity = oldCapacity + (oldCapacity >> 1);
//确保新容量newCapacity大于等于最小容量minCapacity
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
//下面这个if语句不用管也没事，一般都不会搞这么大容量的列表
//判断新容量是否超过了Integer.MAX_VALUE - 8
if (newCapacity - MAX_ARRAY_SIZE > 0)
//如果超过了，则将新容量赋值为Integer.MAX_VALUE
newCapacity = hugeCapacity(minCapacity);
//拷贝出一个新数组，新数组的容量就是前面计算的newCapacity = 15 ，扩容完毕
elementData = Arrays.copyOf(elementData, newCapacity);
}不要因为走得太远而忘记了我们为什么出发。我们一路追追追，只有一个目的： elementData 数组当前是个容量为 10 的数组，要添加第 11 个元素字符串 e = "这是集合的第十一个元素捏"，但是数组容量不够，所以需要先扩容。因此通过上述的 grow 函数确定扩容之后的 elmentData 数组长度为 newCapacity = 15，扩容完毕
（11）集合的第二次扩容结束
后面就是逐层返回到 add 函数了，然后将第 11 个元素 e = "这是集合的第十一个元素捏" 加入到数组中，并更新 size = 11 ，如下 GIF 图所示：
（12）将集合中的元素添加到15个（达到第二个临界点）
之后的第12到第15个元素的添加，与第 11 个元素的添加大同小异，只不过添加过程中不需要进入 grow 方法对数组进行扩容。接下来 4 个元素的添加，这里一笔带过。如下 GIF 所示：
（13）集合的第三次扩容开始
第二次扩容结束后，底层的 elementData 数组的容量由 10--->15 。而经过前面的一通操作过后，elementData 数组又满了。现在我们想向集合中添加第 16 个元素，就要进行集合的第三次扩容。从第二次扩容开始，之后的每次扩容在底层都与第二次扩容原理一样，并且每次都扩容到当前集合容量的 1.5 倍。即第三次扩容之后，elementData 数组为：15 --> 15 + 15 / 2 = 22
同样，直接跳入 add 方法。如下 GIF 图所示：
可以看到，第 16 个元素也为 String 类型，本身就是引用类型，因此不需要"装箱"的操作，所以直接跳入了 add 方法。size = 15 表示 ArrayList 集合中的元素个数为 15
跳入 ensureCapacityInternal ，判断是否需要对数组进行扩容：
可以看到，这里计算得到的 minCapacity = 16 ，即加入该元素所需的数组的最小长度 minCapacity = 16，而当前的数组经过前面的第二次扩容后长度为 15，所以 elementData.length = 15，所以需要执行 grow 函数对数组进行扩容
进入 grow 函数，对数组进行扩容：
private void grow(int minCapacity) {
//minCapacity：16
//记录当前数组的容量，oldCapacity = 15
int oldCapacity = elementData.length;
/*
核心扩容算法：原来容量的 + 原来容量的一半（即原容量的1.5倍）
扩容之后的数组容量：newCapacity = 15 + 15/2 = 22
*/
int newCapacity = oldCapacity + (oldCapacity >> 1);
//确保新容量newCapacity大于等于最小容量minCapacity
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
//下面这个if语句不用管也没事，一般都不会搞这么大容量的列表
//判断新容量是否超过了Integer.MAX_VALUE - 8
if (newCapacity - MAX_ARRAY_SIZE > 0)
//如果超过了，则将新容量赋值为Integer.MAX_VALUE
newCapacity = hugeCapacity(minCapacity);
//拷贝出一个新数组，新数组的容量就是前面计算的newCapacity = 22 ，扩容完毕
elementData = Arrays.copyOf(elementData, newCapacity);
}还是那句话，不要因为走得sssssssssssssssssss了我们为什么出发。我们一路追追追，只有一个目的：elementData 数组当前是个容量为 15 的数组，要添加第 16 个元素字符串 e = "这是集合的第十六个元素捏" ，但是数组容量不够，所以需要先扩容。因此通过上述的 grow 函数确定扩容之后的 elmentData 数组长度为 newCapacity = 22，扩容完毕
（14）集合的第三次扩容结束
后面就是逐层返回到 add 函数了，然后将第 16 个元素 e = "这是集合的第十六个元素捏" 加入到数组中，并更新 size = 16 ，如下 GIF 图所示：
到此，无参构造的分步骤Debug演示，就到这里结束了
4.2 使用有参构造
如果用带参构造来初始化 ArrayList 对象，那么它底层的扩容机制与无参构造初始化 ArrayList 对象时的大同小异。唯一不同的一点在于，使用带参构造初始化 ArrayList 对象，底层的 elementData 数组在一开始不会置空，而是将其初始化为调用带参构造时中实参指定的长度。之后的扩容流程与空参构造初始化对象时无异。因此，这里就不会像之前空参构造时演示得那么细了
将用以下代码为演示，来进行 Debug 操作，代码如下 :
import java.util.ArrayList;
public class demo {
public static void main(String[] args) {
//演示 : 测试通过带参构造初始化ArrayList集合时，其底层的数组扩容机制
//1.创建ArrayList集合对象
ArrayList arrayList = new ArrayList(4);
System.out.println("刚创建的集合 = " + arrayList);
//2.向集合中添加元素（先来4个）
for (int i = 0; i < 4; i++) {
arrayList.add(i); //此处涉及到了自动装箱，int -> Integer
}
//3.再次向集合中添加元素。（扩容：4 ——> 6）
arrayList.add("这是第五个元素捏");
arrayList.add("这是第六个元素捏");
System.out.println("添加六个元素后，集合 = " + arrayList);
//4.再次向集合中添加元素。（扩容：6 ——> 9）
arrayList.add("这是第七个元素捏");
System.out.println("添加七个元素后，集合 = " + arrayList);
}
}（1）开始Debug
首先，进入 Debug 界面，并在第 6 行的有参构造调用行，跳入 ArrayList 类有参构造，如下GIF 所示 :
（2）集合的第一次扩容（初始化）
跳入 ArrayList 的带参构造，如下图所示 :
可以看到，elementData 数组被初始化为了长度为 4 的数组， 4 正是我们调用带参构造时指定的长度
ArrayList 类的该带参构造是一个 if - else if - else 的复合条件语句。因为我们指定的长度 initialCapacity = 4 > 0 ，所以它直接进入 if 控制的语句中，即将一个长度为 4 的新数组赋值给了 elementData 数组（其实就是改变了 elementData 引用的指向）。如果带参构造传入的实参为 0 ，它会将 EMPYT_ELEMENTDATA 赋值给数组，这里的 EMPYT_ELEMENTDATA 也是一个空数组，如下：
如果传入的实参 initialCapacity< 0 ，就会抛出一个异常对象
接着，跳出带参构造，回到测试类，可以看到底层的 elementData 数组被初始化为 4 的长度。如下 GIF 所示：
（3）向集合中添加第一个元素
该过程在使用无参构造时已经详细说明，所以这里我以 GIF 图的方式演示整个添加流程，对于一些重要的部分我会放慢：
以上就是添加一个元素的整个流程，和前面使用无参构造器的时候是完全一样的，对于后续的扩容机制也是完全一致的，所以这里就不再 Debug 了，不然本文的篇幅太长了
....
5.add (E e) 方法源码
这里我将 add (E e) 涉及到的所有方法集中在一起，方便查看，代码也加了详细的注释，如下：
/**
* 往ArrayList添加元素
*
* @param e 待添加的元素
* @return
*/
public boolean add(E e) {
//调用ensureCapacityInternal方法判断是否需要对数组进行扩容
ensureCapacityInternal(size + 1);
//扩容结束后将元素e加入到数组中，并且更新 size
elementData[size++] = e;
return true;
}
/**
* 确保数组elementData容量充足
* @param minCapacity 当前数组所需的最小容量
*/
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
/**
* @param minCapacity 当前数组所需的最小容量
*/
private static int calculateCapacity(int minCapacity) {
//判断当前数组是否已被初始化
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
//通过最小容量和默认容量10求出较大值 (用于第一次扩容)
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
/**
* 确保ArrayList扩容后的容量充足
*
* @param minCapacity 当前数组所需最小容量
*/
private void ensureExplicitCapacity(int minCapacity) {
//集合修改次数++，该属性在扩容的过程中没用，主要是用于迭代器中，确保线程安全
modCount++;
//判断当前数组容量是否满足最小容量，不满足则调用grow进行进行扩容
if (minCapacity - elementData.length > 0)
//调用grow扩容方法
grow(minCapacity);
}
/**
* 扩容 elementData 数组
*
* @param minCapacity 当前数组所需最小容量
*/
private void grow(int minCapacity) {
//记录数组的当前长度,此时由于木有存储元素，长度为0
int oldCapacity = elementData.length;
//核心扩容算法：原来容量的 + 原来容量的一半（即原容量的1.5倍）
int newCapacity = oldCapacity + (oldCapacity >> 1);
//确保新容量newCapacity大于等于最小容量minCapacity
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
//下面这个if语句不用管也没事，一般都不会搞这么大容量的列表
//判断新容量是否超过了Integer.MAX_VALUE - 8
if (newCapacity - MAX_ARRAY_SIZE > 0)
//如果超过了，则将新容量赋值为Integer.MAX_VALUE
newCapacity = hugeCapacity(minCapacity);
//拷贝出一个新数组，新数组的容量就是前面计算的newCapacity，扩容完毕
elementData = Arrays.copyOf(elementData, newCapacity);
}
/**
* 获取一个超大容量
* @param minCapacity
* @return
*/
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow（健壮性代码）
throw new OutOfMemoryError();
// 如果当前超过了 MAX_ARRAY_SIZE（Integer.MAX_VALUE-8）就返回Integer.MAX_VALUE
// 否则返回 MAX_ARRAY_SIZE（Integer.MAX_VALUE-8）
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}