【集合详解】ArrayList 源码解读之动态扩容
本文所使用的 JDK 版本：1.8.0_144
ArrayList 是一个 Java 集合，它的底层数据结构实际上就是一个数组，只不过这个数组长度不固定，动态可变，其中数组元素的类型是 Object 类型的，可以说对 ArrayList 的所有操作底层都是基于数组的。
在阿里巴巴 Java 开发手册第 25 页有这么一句话：
【推荐】在集合初始化时，指定集合初始值大小 阿里巴巴 Java 开发手册
哪么，你有没有想过是为什么呢？大家稍安勿躁，我们先来一个比较有趣的测试：往指定初始化大小的 ArrayList 和 未指定大小的 ArrayList 中填充元素，比较其性能孰优孰劣。
集合性能测试
使用如下测试代码:
测试结果如下：
可以发现，随着集合元素的增加，设置了初始化大小的 ArrayList 在性能上会比没有设置初始化大小的 ArrayList 产生足足一个数量级的差距
。
为了深入了解一下为什么会出现这样的情况，我们需要先翻一翻 ArrayList 的源码，看下它底层到底是怎么实现的。
初始化
通过查看源码，发现有以下三个构造方法：
- 用指定的大小来初始化内部数组
public ArrayList(int initialCapacity) - 默认构造器，以默认大小来初始化内部数组
public ArrayList()- 接收一个 Collection 对象，并将该集合的元素添加到 ArrayList 中
public ArrayList(Collection<? extends E> c)动态扩容
以无参构造器为例，ArrayList 内部数组初始长度为 0，源码如下：
其中，方法 ensureCapacityInternal(size+1)是为了保证内部容量，通过判断，当内部容量不足时则进行扩容操作；
这里有两个点需要注意一下：
- 方法
ensureCapacityInternal()的参数 size 表示的是在执行添加元素之前的数组元素个数，而不是 ArrayList 的具体容量； - ArrayList 的容量本质上是 elementData 数组的长度；
1
确保内部容量
先判断 ArrayList 是否需要扩容：
private static final int DEFAULT_CAPACITY = 10;private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
private void ensureCapacityInternal(int minCapacity) { // 如果 elementData 数组是一个空数组的话，最小需要容量就是默认容量 if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity); }
ensureExplicitCapacity(minCapacity);}
private void ensureExplicitCapacity(int minCapacity) { modCount++; // 如果elementData 数组的长度小于最小需要的容量（minCapacity）,则进行扩容 // overflow-conscious code if (minCapacity - elementData.length > 0) // 扩容方法 grow(minCapacity);}简而言之，当传入的最小需要容量（也就是数组中的实际元素个数加 1 ）大于等于数组容量的时候，就需要进行扩容。
2
扩容
紧接着我们继续看它底层到底是如何扩容的，详细扩容方式参见以下源码注释：
/** * The maximum size of array to allocate. * Some VMs reserve some header words in an array. * Attempts to allocate larger arrays may result in * OutOfMemoryError: Requested array size exceeds VM limit */private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
private void grow(int minCapacity) { // overflow-conscious code int oldCapacity = elementData.length; // 位运算，向右移动一位 (位运算右移意味着做除法，但是位运算效率更高) // 用除法表示就相当于 newCapacity = oldCapacity + 0.5 * oldCapacity // 也就是说 ArrayList 的扩容是每次 1.5 倍数扩容的 int newCapacity = oldCapacity + (oldCapacity >> 1); if (newCapacity - minCapacity < 0) // newCapacity 取 minCapacity 和 newCapacity 之间较大的一个值 newCapacity = minCapacity; if (newCapacity - MAX_ARRAY_SIZE > 0) // 此处对 MAX_ARRAY_SIZE 的值是 Integer.MAX_VALUE - 8 // 根据注释来看 是说 当数组长度超过 Integer.MAX_VALUE - 8 这个值之后有可能会发生 OutOfMemoryError 异常，但是为啥偏偏减了 8 这个值，尚待研究！ newCapacity = hugeCapacity(minCapacity); // 元素复制 // minCapacity is usually close to size, so this is a win: elementData = Arrays.copyOf(elementData, newCapacity);}3
添加元素
当上述容量判断结束之后，真正开始添加元素到 elementData 数组中，就是 add(E e) 方法中的 elementData[size++]=e 这行代码。
另外可以得到一点，就是 ArrayList 在使用默认构造方法初始化的时候，会延迟分配数组对象空间，只有在第一次真正插入元素的时候才会去分配数组空间（默认初始空间大小是 DEFAULT_CAPACITY = 10）。
用代码说话
我们模拟往 ArrayList 中添加 20 个数据，根据以上我们对 ArrayList 源码的分析可以得出 ArrayList 的容量变化过程是：
- 往 ArrayList 添加第一个元素的时候，ArrayList 会初始化内部的 elementData 数组，容量使用默认容量（默认容量值为 10）；
- 往 ArrayList 添加第 11 个元素的时候，容量不足（11 > 10）,需要扩容，通过上节源码分析可得 ArrayList 是按照 1.5 倍进行扩容的，也就是说此时会扩容到 10 + 10 * 0.5 = 15;
- 往 ArrayList 添加第 16 个元素的时候，容量再次不足（16 > 15），需要再次扩容，此次扩容结果是 15 + 15 * 0.5 = 22;
哪么实际的扩容结果是不是和我们分析的一致呢 ？请看如下实代码的实际测试结果：
- 尚未开始添加数据的时候
- 往 ArrayList 添加第一个元素的时候
- 往 ArrayList 添加第 11 个元素的时候
- 往 ArrayList 添加第 16 个元素的时候
综上：我们之前的分析结果是完全 ok 的哈，如果还是不太理解的话大家可以一步一步去亲手调试一下代码，看一下分别在第 10 、第 11、第 15、第 16 个元素添加到 ArrayList 时具体的容量变化，眼过千遍，不如手过一遍，毕竟只有自己撸到手的才算是自己的知识。
经过今天的学习之后，就会很容易理解文章最开始提到的哪个问题，为什么会建议在集合初始化的时候尽量指定大小？
因为在我们根据预估数据量大小之后，指定集合初始化大小，这样会减少扩容次数，进而提高代码执行效率！当然，如果实在不知道容量大小，直接使用默认构造方法即可。
总结
结合本文所述，对于 ArrayList 的自动扩容原理，概括起来就是以下几点：
- ArrayList 通过无参构造的话，初始数组容量为 0 ；
- ArrayList 通过无参构造的话，会延迟分配数组对象空间，只有在对数组真正开始添加元素时，才数组对象分配空间（默认初始容量值是 10）；
- 容量不足时每次按照 1.5 倍（位运算）的比率进行扩容；
本篇内容比较简单，如有错误也欢迎大家留言指出。常听大佬说看源码是相当好的一种学习方式，以前不觉得，随着工作越来越长时间，发现单纯的靠 CRUD 的业务代码的确是很难提高自己的编码水平，除非项目是非常具有挑战性的（当然大多数程序员的项目说白了没啥技术难度和挑战性，比如我... ...）。哪么我们就只有通过读源码的方式来学习，来提高自己的代码水平，长路漫漫，共勉吧!