Java容器之ArrayList源码解析

声明：源码解析基于JDK1.8

ArrayList 继承自 AbstractList 类，并且实现了 List，RandomAccess，Cloneable，java.io.Serializable 接口

使用 ArrayList 的空参构造器实例化对象，会初始化一个长度为 0 空数组。由此可以看出，底层使用的是 Object 类型的数组存储数据

从上面代码中可以看出，初始化的时候，数组的长度为0，那么何时扩容数组的长度呢？其实是在第一次 add 的时候

add 的代码比较多，一步步来分析

复杂内容其实是在 ensureCapacityInternal(size + 1) 这个里面，先抛开这个不说

size 表示当前数组的长度，由于类型是 int，所以默认值为 0

elementData[size++] = e 可以拆分为 elementData[size] = e; size = size + 1

第一次添加数据时，可以表示为：elementData[0] = e; size = 0+1; 即 size = 1

最后返回 true

但是问题来了，初始化时数组的长度为空，即长度为0，是无法往数组中添加数据的，需要将数组扩容

扩容的代码就在 ensureCapacityInternal(size + 1) 方法里

ensureCapacityInternal：翻译过来就是，确保数组内部的容量

首先调用 calculateCapacity 方法计算数组的最小容量

最小容量什么意思呢？用白话说，就是每次添加数据的时候，要确保当前数组的容量要大于计算出来的最小容量。如果当前数组的容量小于计算出来的最小容量，就意味着数组内没有可以存放新数据的位置了，此时就需要扩容数组的容量

从计算最小容量的代码中可以看出：第一次添加数据时，minCapacity = 1 

calculateCapacity 方法头上的参数 minCapacity 的实际意义是：每次添加数据的时候，期望的最小容量就是当前数组的容量+1，因为只有当前数组的容量+1 才能新增加一条数据

第一次添加数据时，elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA 成立，所以返回的最小容量是 DEFAULT_CAPACITY = 10

只有第一次添加数据时，计算出来的最小容量才为 10，其余时候，计算出来的最小容量都是当前数组的容量+1

由此可见，第一次添加数据时，扩容的容量为 10

接下来是 ensureExplicitCapacity 这个方法

这个方法内部逻辑理解起来比较简单，就是说：如果计算出来的最小容量大于当前数组的容量，就执行扩容的逻辑，反之则不扩容

真正的核心代码在 grow 里，这个才是扩容的真面目

oldCapacity：表示当前数组的容量，即当前数组的长度

newCapacity：表示扩容后数组的容量

  >> 1 右移一位，其实就是除以 2 这个操作

以此类推，>> 2 右移两位，表示除以 2 的 2 次方

>> 3 右移三位，表示除以 2 的 3 次方

>> n 右移 n 位，表示除以 2 的 n 次方

oldCapacity + (oldCapacity >> 1) 可以写成 oldCapacity + (oldCapacity / 2) 实际含义是扩容 1.5 倍

如果扩容后数组的容量还比计算出来的最小容量小的话，就把数组容量扩容至计算出来的最小容量

这种情况只会在第一次添加数据，扩容数组容量时发生。

如果扩容后数组的容量大于数组允许的最大容量，就调用 hugeCapacity 方法（这种情况很少发生）

最后使用 Arrays.copyOf 方法进行数组的扩容

最后，白话总结：

首先，ArrayList 底层是一个 Object 类型的数组，实例化 ArrayList 对象时，底层是创建了一个长度为 0 的空数组

当调用 ArrayList 的 add 方法时，如果数组的长度不满足时，就扩容 1.5 倍

第一次 add 的时候，会默认扩容 10 个长度。之后每次 add，如果数组长度不满足时，才扩容 1.5 倍

扩容是使用 Arrays.copyOf 方法