【Java集合】ArrayList源码深度分析

参考笔记：

java ArrayList源码分析（深度讲解）-CSDN博客

【源码篇】ArrayList源码解析-CSDN博客

---

目录

1.前言

2. ArrayList简介

3. ArrayList类的底层实现

4. ArrayList的源码Debug

4.1 使用空参构造 

        （1）开始Debug

        （2）初始化底层elementData数组为空数组

        （3） 对add方法中的实参进行自动装箱

        （4） 进入add方法

        （5）进入ensureCapcityInternal 方法

        （6） 进入grow方法

        （7）逐层返回，第一次扩容elementData数组完毕（0 ——> 10）

        （8）向集合中添加第二个元素(不需要扩容)

        （9）将集合中的元素添加到10个（达到第一个临界点）

        （10）集合的第二次扩容开始

        （11）集合的第二次扩容结束

        （12）将集合中的元素添加到15个（达到第二个临界点） 

        （13）集合的第三次扩容开始

        （14）集合的第三次扩容结束 

4.2 使用有参构造

        （1）开始Debug

        （2）集合的第一次扩容（初始化）

        （3）向集合中添加第一个元素

        ....

 5.add (E e) 方法源码

---

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//记录当前数组的容量，由于此时还没有存储元素，所以为0int oldCapacity = elementData.length;/*核心扩容算法：原来容量的 + 原来容量的一半（即原容量的1.5倍）,但第一次扩容的时候这里的newCapacity = 0因为第一次扩容的时候 oldCapacity = 0 嘛。但不用担心，后面紧跟着的if语句就是用来应对这种情况的*/int newCapacity = oldCapacity + (oldCapacity >> 1);//确保新容量newCapacity大于等于最小容量minCapacity，所以第一次扩容时 newCapacity = 10if (newCapacity - minCapacity < 0)newCapacity = minCapacity;//下面这个if语句不用管也没事，一般都不会搞这么大容量的列表//判断新容量是否超过了Integer.MAX_VALUE - 8if (newCapacity - MAX_ARRAY_SIZE > 0)//如果超过了，则将新容量赋值为Integer.MAX_VALUEnewCapacity = 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 = 10int oldCapacity = elementData.length;/*核心扩容算法：原来容量的 + 原来容量的一半（即原容量的1.5倍）扩容之后的数组容量：newCapacity = 10 + 10/2 = 15*/int newCapacity = oldCapacity + (oldCapacity >> 1);//确保新容量newCapacity大于等于最小容量minCapacityif (newCapacity - minCapacity < 0)newCapacity = minCapacity;//下面这个if语句不用管也没事，一般都不会搞这么大容量的列表//判断新容量是否超过了Integer.MAX_VALUE - 8if (newCapacity - MAX_ARRAY_SIZE > 0)//如果超过了，则将新容量赋值为Integer.MAX_VALUEnewCapacity = 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 = 15int oldCapacity = elementData.length;/*核心扩容算法：原来容量的 + 原来容量的一半（即原容量的1.5倍）扩容之后的数组容量：newCapacity = 15 + 15/2 = 22*/int newCapacity = oldCapacity + (oldCapacity >> 1);//确保新容量newCapacity大于等于最小容量minCapacityif (newCapacity - minCapacity < 0)newCapacity = minCapacity;//下面这个if语句不用管也没事，一般都不会搞这么大容量的列表//判断新容量是否超过了Integer.MAX_VALUE - 8if (newCapacity - MAX_ARRAY_SIZE > 0)//如果超过了，则将新容量赋值为Integer.MAX_VALUEnewCapacity = 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加入到数组中，并且更新 sizeelementData[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) {//记录数组的当前长度,此时由于木有存储元素，长度为0int oldCapacity = elementData.length;//核心扩容算法：原来容量的 + 原来容量的一半（即原容量的1.5倍）int newCapacity = oldCapacity + (oldCapacity >> 1);//确保新容量newCapacity大于等于最小容量minCapacityif (newCapacity - minCapacity < 0)newCapacity = minCapacity;//下面这个if语句不用管也没事，一般都不会搞这么大容量的列表//判断新容量是否超过了Integer.MAX_VALUE - 8if (newCapacity - MAX_ARRAY_SIZE > 0)//如果超过了，则将新容量赋值为Integer.MAX_VALUEnewCapacity = 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;
}