探秘ArrayList源码：Java动态数组的背后实现

---

---

读者需先对源码的成员变量阅览一遍，看个眼熟，有助于后面源码的理解

private static final long serialVersionUID = 8683452581122892189L;        private static final int DEFAULT_CAPACITY = 10;        private static final Object[] EMPTY_ELEMENTDATA = {};     //用于默认大小空实例的共享空数组实例。      //我们把它从EMPTY_ELEMENTDATA数组中区分出来，以知道在添加第一个元素时容量需要增加多少。    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};        transient Object[] elementData;         private int size;

1、默认构造器

public ArrayList() {    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;}

以无参数构造方法创建 ArrayList时，实际上初始化赋值的是一个空数组。此时并没有为它创建对象，当真正对数组进行添加元素操作时，才真正分配容量。即向数组中添加第一个元素时，数组容量扩为 10。

2、带初始容量参数构造器

public ArrayList(int initialCapacity) {    if (initialCapacity > 0) {//初始容量大于0        //创建initialCapacity大小的数组        this.elementData = new Object[initialCapacity];    } else if (initialCapacity == 0) {//初始容量等于0        //创建空数组        this.elementData = EMPTY_ELEMENTDATA;    } else {//初始容量小于0，抛出异常        throw new IllegalArgumentException("Illegal Capacity: "+               initialCapacity);    }}

3、指定collection元素参数构造器

 public ArrayList(Collection c) {    elementData = c.toArray();    if ((size = elementData.length) != 0) {        // c.toArray might (incorrectly) not return Object[] (see 6260652)        if (elementData.getClass() != Object[].class)            elementData = Arrays.copyOf(elementData, size, Object[].class);    } else {        // replace with empty array.        this.elementData = EMPTY_ELEMENTDATA;    }}

在进入ArrayList的核心源码扩容机制前，我们首先需要对源码中涉及到的一些变量进行一个初步的了解，这将有助于你对源码的深入了解

1. minCapacity：数组所需的最小容量
2. elementData：存储ArrayList元素的数组缓冲区

public boolean add(E e) {   ensureCapacityInternal(size + 1);  // size = 0   elementData[size++] = e;   return true;}

private void ensureCapacityInternal(int minCapacity) {//minCapacity = 1    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));//elementData = {}}

private static int calculateCapacity(Object[] elementData, int minCapacity) {    //判断elementData是否为空数组    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {//DEFAULTCAPACITY_EMPTY_ELEMENTDATA =  {}        return Math.max(DEFAULT_CAPACITY, minCapacity);//DEFAULT_CAPACITY = 10;minCapacity = 1    }    return minCapacity;}

private void ensureCapacityInternal(int minCapacity) {//minCapacity = 1    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));//ensureExplicitCapacity(10)}

private void ensureExplicitCapacity(int minCapacity) {//minCapacity = 10    modCount++;    if (minCapacity - elementData.length > 0)//elementData.length = 0        grow(minCapacity);}

private void grow(int minCapacity) {//minCapacity = 10    int oldCapacity = elementData.length;//oldCapacity = 0    int newCapacity = oldCapacity + (oldCapacity >> 1);//newCapacity  = 1.5*oldCapacity = 0    if (newCapacity - minCapacity < 0)//minCapacity = 10        newCapacity = minCapacity;//newCapacity = 10    if (newCapacity - MAX_ARRAY_SIZE > 0)        newCapacity = hugeCapacity(minCapacity);    //利用Arrays.copyOf()方法进行扩容    elementData = Arrays.copyOf(elementData, newCapacity);}

private static int hugeCapacity(int minCapacity) {     if (minCapacity < 0) // overflow         throw new OutOfMemoryError();     return (minCapacity > MAX_ARRAY_SIZE) ?         Integer.MAX_VALUE :         MAX_ARRAY_SIZE; }

1. 增加一个新元素，此时所需的最小容量是 minCapacity = size+1
2. 首先判断底层数组 elementData 是否是空数组
   • 如果是空数组，则更新 minCapacity 为默认容量10，
   • 如果不是空数组，则对 minCapacity 不做变更
3. 判断所需最小容量 minCapacity 是否大于缓冲数组 elementData 的长度：
   • 如果大于，则进行扩容 grow()，
   • 否则不做处理
4. 扩容 grow()中，首先一上来就将 elementData 的长度扩长为原来长度的1.5倍，再对扩容后的 elementData 的长度和所需最小的容量 minCapacity进行判断
   • 如果扩容后的 elementData 的长度还小于 minCapacity 的长度，说明还是不够，此时就直接将minCapacity的长度赋值给elementData
   • 否则的话直接进行下一步即可
5. 最后需要对 elementData 的长度进行一个是否超过最大限度值MAX_ARRAY_SIZE判断
   • 如果超过最大限度值，就看看所需的最小容量minCapacity是否大于最大限度值Integer.MAX_VALUE
   • 如果不是，就将数组的长度扩容为数组的最大限度值MAX_ARRAY_SIZE，如果是，则返回Integer.MAX_VALUE

1、对于ensureExplicitCapacity（）方法

1.1 add 进第 1 个元素到 ArrayList 时

当我们要 add 进第 1 个元素到 ArrayList 时，elementData.length 为 0 （因为还是一个空的 list），因为执行了 ensureCapacityInternal() 方法 ，所以 minCapacity 此时为 10。此时，minCapacity - elementData.length > 0成立，所以会进入 grow(minCapacity) 方法。

1.2 当 add 第 2 个元素时

当 add 第 2 个元素时，minCapacity 为 2，此时 elementData.length(容量)在添加第一个元素后扩容成 10 了。此时，minCapacity - elementData.length > 0 不成立，所以不会进入 （执行）grow(minCapacity) 方法。
添加第 3、4···到第 10 个元素时，依然不会执行 grow 方法，数组容量都为 10。

1.3 直到添加第 11 个元素

minCapacity(为 11)比 elementData.length（为 10）要大。进入 grow 方法进行扩容。

2、对于grow() 方法：

2.1 当 add 第 1 个元素时

oldCapacity 为 0，经比较后第一个 if 判断成立，newCapacity = minCapacity(为 10)。但是第二个 if 判断不会成立，即 newCapacity 不比 MAX_ARRAY_SIZE 大，则不会进入 hugeCapacity 方法。数组容量为 10，add 方法中 return true,size 增为 1。

2.2 当 add 第 11 个元素进入 grow 方法时

newCapacity 为 15，比 minCapacity（为 11）大，第一个 if 判断不成立。新容量没有大于数组最大 size，不会进入 hugeCapacity 方法。数组容量扩为 15，add 方法中 return true,size 增为 11。以此类推······

1. 变量 minCapacity 理解为我们添加元素进ArrayList集合中，底层数组所需的最小容量
2. 变量 elementData.length 理解为我们添加元素进ArrayList集合中，底层数组的最大限度容量
3. 当最小容量 minCapacity> 最大限度容量 elementData.length ,必定会触发扩容机制。
4. 我们总是频繁地向ArrayList集合添加元素，开发人员也想到了这点，所以在ArrayList集合的扩容机制中，当我们添加第一个元素时，直接就把minCapacity设置为10，此处可以理解为，因为我们后续要频繁添加元素，为了不总是触发该集合的扩容机制，便“谎称”所需的最小容量是10，所以系统就直接把elementData.length设置为10

来源地址：https://blog.csdn.net/weixin_52533007/article/details/130638330