浅谈 ArrayList 的扩容机制

信任我们对 ArrayList 这个类都不陌生吧，ArrayList 底层是根据数组完成的，作为可变长度的数组用于存储恣意类型的对象，那么是否有了解过 ArrayList 是如何完成可变长的呢，它的扩容机制是什么呢？

这篇文章将从源码的视点来讲讲 ArrayList 的扩容机制，有爱好的读者们能够接着往下了解。

ArrayList 的结构函数

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

ArrayList 的字段

// 默许初始容量巨细
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 的结构函数

// 有参结构函数（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()

public boolean add(E e) {
    // size + 1 确保增加后长度满足，进入办法判别是否需求扩容
    ensureCapacityInternal(size + 1);
    // 增加元素
    elementData[size++] = e;
    return true;
}

判别是否是默许长度办法：ensureCapacityInternal()

private void ensureCapacityInternal(int minCapacity) {
    // 数组为默许数组时，minCapacity只会在10之上。
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    // 进入办法判别是否需求扩容
    ensureExplicitCapacity(minCapacity);
}

判别是否需求扩容办法：ensureExplicitCapacity()

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

扩容办法：grow()

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个元素的进程：

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个元素的进程：

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)$，也便是新容量取值为旧容量的 1.5 倍。

弥补：数组复制 System.arraycopy() 办法

扩容后的数据搬迁调用的是 Arrays.copyOf() 办法底层调用的是 System.arraycopy()，这儿简略介绍一下这个常用的办法。

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 类中还有许多有意思的办法，有爱好的读者们能够自行去检查它们的源码。

感谢观看！！！