浅谈 ArrayList 的扩容机制

你的名字 2023-10-12 13:26 36阅读 0赞

相信大家对 ArrayList 这个类都不陌生吧，ArrayList 底层是基于数组实现的，作为可变长度的数组用于存储任意类型的对象，那么是否有了解过 ArrayList 是如何实现可变长的呢，它的扩容机制是什么呢？

这篇文章将从源码的角度来讲讲 ArrayList 的扩容机制，有兴趣的读者们可以接着往下了解。

# ArrayList 的构造函数 #

在了解 ArrayList 的扩容机制之前，让我们先看看它的构造函数有哪些？

> **ArrayList 的字段**

java复制代码// 默认初始容量大小
    private static final int DEFAULT_CAPACITY = 10;
    // 空数组
    private static final Object[] EMPTY_ELEMENTDATA = {};
    // 默认空数组
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
    // 存储数据的数组
    transient Object[] elementData;
    // 元素个数
    private int size;
    // 最大数组长度
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

相信大家对这里的 EMPTY\_ELEMENTDATA 和 DEFAULTCAPACITY\_EMPTY\_ELEMENTDATA 为何需要有两个空数组感到疑惑，这两个空数组之间的区别在什么地方呢？对于这个问题等看完后面的源码后就会有答案了。

> **ArrayList 的构造函数**

java复制代码// 有参构造函数（initialCapacity：指定的初始化集合大小）
    public ArrayList(int initialCapacity) {
        if (initialCapacity > 0) {
            // 创建长度为initialCapacity的数组
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
            // 使用空数组（长度为0）
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }
    
    // 无参构造器
    public ArrayList() {
        // 使用默认空数组（一开始长度为0，等集合被使用后初始化为10）
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }
    
    // 有参构造器（根据指定的集合构造列表）
    public ArrayList(Collection<? extends E> c) {
        // 通过toArray()方法转换为数组
        elementData = c.toArray();
        if ((size = elementData.length) != 0) {
            // 数组长度不为0且数组不是Object类型数据则更换类型为Object的新数组
            if (elementData.getClass() != Object[].class)
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else {
            // 数组长度为0则使用空数组
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }

通过上面源码中的三种 ArrayList 的构造函数可以看到根据不同的参数构造列表，同时根据不同的参数导致的列表的数组 elementData 被赋予的值也是不同的。

到这里应该可以看出 EMPTY\_ELEMENTDATA 和 DEFAULTCAPACITY\_EMPTY\_ELEMENTDATA 的区别：

*  **EMPTY\_ELEMENTDATA**：当构造函数使用指定 initialCapacity 为 0 或指定集合且集合元素为 0 时，会使得 elementData 被赋值为 EMPTY\_ELEMENTDATA。这里的空数组表示初始化后的数组长度就是 0 。
 *  **DEFAULTCAPACITY\_EMPTY\_ELEMENTDATA**：当构造函数使用无参构造函数时，elementData 被赋值为 DEFAULTCAPACITY\_EMPTY\_ELEMENTDATA。这里的空数组表示开始长度为 0，当列表被使用时，初始化后的数组长度为 10（DEFAULT\_CAPACITY），也就是默认数组大小。（通过后面的 add() 源码能够更好理解）

到这里就可以理解为什么 ArrayList 有两个空数组字段，主要是为了设置默认的数组长度，也就是为了区分当前数组是默认数组（也就是还不确定大小，先设置为空数组，等使用后在设置为默认长度），还是已经确认长度为 0 的空数组。

--------------------

# ArrayList 的扩容机制 #

ArrayList 的扩容机制核心方法是 grow() 方法，这里从 add() 方法进入详细看看 ArrayList 的扩容过程。

> **扩容过程源码分析**

**添加元素方法：add()**

java复制代码public boolean add(E e) {
        // size + 1 确保添加后长度足够，进入方法判断是否需要扩容
        ensureCapacityInternal(size + 1);
        // 添加元素
        elementData[size++] = e;
        return true;
    }

**判断是否是默认长度方法：ensureCapacityInternal()**

java复制代码private void ensureCapacityInternal(int minCapacity) {
        // 数组为默认数组时，minCapacity只会在10之上。
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        // 进入方法判断是否需要扩容
        ensureExplicitCapacity(minCapacity);
    }

**判断是否需要扩容方法：ensureExplicitCapacity()**

java复制代码private void ensureExplicitCapacity(int minCapacity) {
        // 用于记录修改次数的计数器，保证多线程下抛出ConcurrentModificationException异常
        modCount++;
        // minCapacity最小需求容量小于当前数组长度时则需要扩容
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

**扩容方法：grow()**

java复制代码private void grow(int minCapacity) {
        // 旧容量等于数组长度
        int oldCapacity = elementData.length;
        // 新容量等于数组长度 + 0.5 * 数组长度 也就是 1.5 数组长度
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        
        // 新容量还是小于最小需求容量时，直接将新容量赋值为最小需求容量
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
            
        // 新容量大于MAX_ARRAY_SIZE（Integer.MAX_VALUE - 8）调用hugeCapacity()扩容到Integer.MAX_VALUE
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
            
        // 数组拷贝，将数据迁移到新数组
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

> **扩容过程梳理**

下面以使用无参构造函数的列表为例，分别讲讲第1个元素插入和第11个元素插入的扩容过程：

**添加第1个元素的过程**：

![format_png][]

1.  调用 add(e) 方法添加元素，此时的 size=0。
2.  调用 ensureCapacityInternal(1) 方法判断是否是默认长度数组，此时该方法的传参是 size + 1 代表目前列表需要的最小容量。进入该方法后，因为使用的是无参构造器，故这里的数组是默认长度数组，所以 minCapacity 最小容量被置为 10，也就是列表默认长度 DEFAULT\_CAPACITY。
3.  调用 ensureExplicitCapacity(10) 方法判断是否需要扩容，此时由于 minCapacity=10 大于 数组长度 elementData.length=0 所以需要扩容。
4.  调用 grow(10) 方法进行扩容，此时旧数组容量为 oldCapacity=0，新数组容量为 newCapacity=0，而最小容量 minCapacity=10，因为新数组容量小于最小容量，故将新数组容量重新赋值为 newCapacity=minCapacity=10，然后进行数组拷贝，到此完成扩容操作。

**添加第11个元素的过程**：

![format_png 1][]

1.  调用 add(e10) 方法添加元素，此时的 size=10。
2.  调用 ensureCapacityInternal(11) 方法判断是否是默认长度数组，此时该方法的传参是 size + 1 代表目前列表需要的最小容量。进入该方法后，由于已经超出了默认长度 10，所以这里 minCapacity 设置为 11。
3.  调用 ensureExplicitCapacity(11) 方法判断是否需要扩容，此时由于 minCapacity=11 大于 数组长度 elementData.length=10 所以需要扩容。
4.  调用 grow(11) 方法进行扩容，此时旧数组容量为 oldCapacity=10，新数组容量为 newCapacity=15，而最小容量 minCapacity=11，因为新数组容量大于最小容量，故将新数组容量依旧为15，然后进行数组拷贝，到此完成扩容操作，新数组的长度扩容到了 15，并将旧数组的元素迁移到新数组中。

以上就是扩容的全过程，扩容公式为 newCapacity=oldCapacity+(oldCapacity>>1)newCapacity = oldCapacity + (oldCapacity >> 1)newCapacity=oldCapacity+(oldCapacity>>1)，也就是新容量取值为旧容量的 1.5 倍。

--------------------

> **补充：数组拷贝 System.arraycopy() 方法**

扩容后的数据迁移调用的是 Arrays.copyOf() 方法底层调用的是 System.arraycopy()，这里简单介绍一下这个常用的方法。

java复制代码public static native void arraycopy(Object src,  int  srcPos,
                                        Object dest, int destPos,
                                        int length);

该方法的参数如下：

*  src：源数组
 *  srcPos：源数组拷贝的起始位置
 *  dest：目标数组
 *  destPos：目标数组拷贝的起始位置
 *  length：需要拷贝的数组元素的数量

这里作为补充知识简单了解一下即可。

--------------------

# 总要有总结 #

以上就是 ArrayList 的扩容机制的内容了，主要总结如下：

1.  ArrayList 是基于动态数组实现的，可以扩容或缩短（缩短可以手动调用 trimToSize() 方法，ArrayList在元素小于一半长度时会自动缩短长度，这里不作过多说明）数组的大小从而实现可变长的数组。
2.  ArrayList 中声明了 EMPTY\_ELEMENTDATA 和 DEFAULTCAPACITY\_EMPTY\_ELEMENTDATA 两个字段，虽然都是空数组，但是两者之间有着不同的作用。
3.  ArrayList 的扩容机制采用的是新数组容量扩容为旧数组容量的 1.5 倍。

补充： ArrayList 提供了 ensureCapacity(int minCapacity) 用于实现手动扩容到指定的容量，这样在需要添加大量数据时可以不必重复进行扩容操作，提高性能。

到这里就是本篇的所有内容了，ArrayList 类中还有许多有意思的方法，有兴趣的读者们可以自行去查看它们的源码。

[format_png]: https://img-blog.csdnimg.cn/img_convert/1a2c97d442a6c5697dcae3720fc6701b.webp?x-oss-process=image/format,png
[format_png 1]: https://img-blog.csdnimg.cn/img_convert/42fd4c148ccdbb227f69655cedf1ccc9.webp?x-oss-process=image/format,png