手撕ArrayList的add()底层源码【无参构造器】

开篇：

今天突然看到这样一句话，着实很有道理。
如果你不能向一个六岁的孩子解释清楚，那么其实你自己根本没弄懂。这句话很适合我们这些技术人，程序员的世界里不应该出现模糊的概念，遇到一些拿捏不准的东西需要及时理解透彻。

不知何时，我们经常听到别人说手撕源码这一说，并且在很多面试中都要求程序员有一定的看源码的能力，因此对我们来说底层看懂并理解源码显得尤为重要。
在手撕Arraylsit之前，我们需要简单的了解一下集合。
先说集合的概念，然后再具体阐明。
集合：
Java的集合类是java.util包中的重要内容，它允许以各种方式将元素分组，并定义了各种使这些元素更容易操作的方法。Java集合类是Java将一些基本的和使用频率极高的基础类进行封装和增强后再以一个类的形式提供。集合类是可以往里面保存多个对象的类，存放的是对象，不同的集合类有不同的功能和特点，适合不同的场合，用以解决一些实际问题。说的更加简单些，就是因为解决数组解决不了的问题。因为我们都知道数组有一定的缺点。
比如：

1. 长度开始时必须指定，而且一旦指定，不能更改

2. 保存的必须为同一类型的元素

3. 使用数组进行增加元素的示意代码 – 比较麻烦
   那么说说集合：
   java的集合分为很多类，但主要分为单列集合和多列集合。
   请看下图：
   
   
   从图上我们可以看到单列集合的父接口是Collection,并且提供了一系列的方法。

   add:添加单个元素
   remove:删除指定元素
   contains:查找元素是否存在
   size:获取元素个数
   isEmpty:判断是否为空
   clear:清空 
   addAll:添加多个元素
   containsAll:查找多个元素是否都存在
   removeAll：删除多个元素
   

因此我们想实现这些接口的方法，就必须实现Collection接口的类。
从关系图中我们也能看到ArrayList实现了List接口，而List接口继承了Collection接口。因此，ArrayList类也实现了Collection接口。
下面我们就引入正题：
我就用一个最简单的实例来详细剖析ArrayList.

public class ArrayTheroy {

	@SuppressWarnings({ "rawtypes", "unchecked" })
	public static void main(String[] args) {
		ArrayList list = new ArrayList();
		
		for(int i=1;i<=10;i++){
		list.add("AA"+i);
		}
		for(int i=1;i<=5;i++){
		list.add("CC"+i);
		}
		list.add("AA");
		list.add("BB");
		list.add(null);
		for (Object object : list) {
		System.out.println(object);
		}


	}

}

如果你仔细观察将会发现我为什么要用一个循环并且循环10次。
这会我需要先把ArrayList底层接口和机制拿出来。

1)	ArrayList中维护了一个Object类型的数组elementData. [源码]transient Object[] elementData; 
2)	当创建对象时，如果使用的是无参构造器，则初始elementData容量为0（jdk7是10）
3)	当添加元素时：先判断是否需要扩容，如果需要扩容，则调用grow方法，否则直接添加元素到合适位置
4)	如果使用的是无参构造器，如果第一次添加，需要扩容的话，则扩容elementData为10，如果需要再次扩容的话，则扩容elementData为1.5倍。
5)	如果使用的是指定容量capacity的构造器，则初始elementData容量为capacity
6)	如果使用的是指定容量capacity的构造器，如果需要扩容，则直接扩容elementData为1.5倍。

开搞：

下面开始一步步来解释这个机制。
因为我的Debug不能Step into，因此我用静态追源码的方式来。

1.先把断点调到光标颜色高亮的地方。

开始debug运行，然后我们在控制台处观看参数的变化。

2.Step into追进ArrayList list = new ArrayList();

这个时候底层到底发什么什么呢？

1. 首先将会找到ArrayList.class类的无参构造方法。
2. 
   这里的elementDataArraylist中，并且是一个属性。

我们可以看到其实elementData是一个数组对象，前面的那个tranient现在先不要用管，其实主要是为了以后传输不会序列化。
然后这个DEFAULTCAPACITY_EMPTY_ELEMENTDATA也是一个空的数组，我们也可以看看。

3.执行Step over下一步。

结果：我们看到elementData中仍然为[0]

然后接着下一步

结果：

然后再接着下一步：

ok,这时候我们清楚发现elementData[]数组长度变为10了。
我靠，到底发什么了什么。这就是问题的核心。

在内部其实经过了一系列的处理。

①：先进入到add的方法中

然后继续Step into追加，将进入到ensureCapacityInternal（）方法中，并且传入的参数为“size+1"，可以看到size为ArrayList的属性，默认值为0。

那么为什么要用size+1呢？底层用的机制真的很巧，它的意思是再你调用add（）方法时,我底层确保至少要有一个长度的大小，不然你就没法添加。

②进入到ensureCapacityInternal(）方法中

这时候在方法中参数minCapacity为1，接着进入到条件中进行判断，
此时elementData仍然为空，并且等于ArrayList中默认DEFAULTCAPACITY_EMPTY_ELEMENTDAT空。
此时条件中调用max方法，获取到你传入的minCapacity和DEFAULT_CAPACITY中的最大值。

在ArrayList将DEFAULT_CAPACITY封装起来作为静态常量的一个值10并且不可修改。
因此调完之后将minCapacity重置为max函数的最大值。

③进入到ensureExplicitCapacity（）方法中。

继续在方法中判断当前传来的数组长度和原数组长度的大小，若原数组的长度小于当前传来的长度，则表明数组长度不够，需要进行扩容。那么就把比较得来的最大值也就是新参的值传给grow（），这个方法就是进行真正的扩容。前面一系类就是判断是否需要扩容，若扩容应该扩容多少。

③进入到gorw()方法中。

将原数组的长度做一份保留，然后扩容一个新数组且大小为原数组的1.5倍。int newCapacity = oldCapacity + (oldCapacity >> 1);

表示右移两位，底层除二都是用这种方法。可以自己使用。

再进行比较新扩容数组的长度是否小于传入的定义长度。如果小于，则表明此时原数组的长度为0。因为当前做完 int newCapacity = oldCapacity + (oldCapacity >> 1);后原新组长度为0，此时将 minCapacity（10）赋值给要扩容的 长度。而最后一个if条件则是比较你如果扩容太大超过设定的最大值后，将从新设定你要扩容的长度，因此这个条件基本不进入。
最后长度确定之后，调用Array.copyof()将原数组扩容，并且扩容长度为newCapacity 也就10，但是copyof（）方法拷贝的长度，没有元素的将用null填充。

④：在一次Step Into，跳出这时将进入到

当ensureCapacityInternal（）方法。进入到elementData[size++] = e;
这时size的值为0，然后将你要添加的值放入到elementData数组中，然后size进行加一为了下一次将值放进去。
最终也就是当你看到结果为什么为9个null,一个值了。
因为你此时调用了一次add()方法。

④：我将十次都遍历完，然后继续添加，看看出现什么。此时Step into到下面位置

数组长度仍然是10，接着

Step into进去

执行完后，发现数组长度又多了五个。这就回到了最初了，因为此时数组长度为10，在下面的扩容将会安按照1.5倍扩容，因此扩容之后长度为15，但是不要以为是重新扩了15哈，是本次扩容的长度为15，这个是Array.copyOf()方法的使用规则。详细也可以追加copyOf()的源码。我在这里不再演示。我主要分析这个15是怎么来的。

1）进入到add()方法：

size此时已经为10了，将size+1y也就是11传入到ensureCapacityInternal（int minCapacity）方法中去。

在方法中开始判断此时elementData为10了，而不是像最初进去时的长度0，这就是第二次的关键点。此时发现条件不再相等，因此将会往下执行ensureExplicitCapacity(minCapacity);

接着又开始判断if中的条件，此时11仍然大于10，接着开始调用grow（）方法开始扩容，进到grow()方法中去。

此时在grow()方法中：

1. 仍然先保存着当前数组的长度。此时长度为（10）
2. 计算要扩容的大小：10+10/2；
3. 开始判断要新扩容的长度是不是小于当前我空间中最小的长度。一比较发现此时我计算出来的数组长度是大于我空间预留的长度。因此不需要从新赋值，直接把扩容我当前计算出来的数组长度扔到copyOf()方法中，因此最终将会扩容15个长度。

这就是调用一次add方法，底层源码帮你做的工作，是不是感觉自己用的时候就直接拿去，感觉十分方便，但是当你进入源码的时候，会发现十分的麻烦。望大家平时多分析一些底层源码，将会是一种能力的隐形提高。

PS 撸出来的代码，才有意义。

本文地址：https://blog.csdn.net/qq_40530040/article/details/107370320