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

调用 add(e) 办法增加元素，此刻的 size=0。
调用 ensureCapacityInternal(1) 办法判别是否是默许长度数组，此刻该办法的传参是 size + 1 代表现在列表需求的最小容量。进入该办法后，因为运用的是无参结构器，故这儿的数组是默许长度数组，所以 minCapacity 最小容量被置为 10，也便是列表默许长度 DEFAULT_CAPACITY。
调用 ensureExplicitCapacity(10) 办法判别是否需求扩容，此刻因为 minCapacity=10 大于数组长度 elementData.length=0 所以需求扩容。
调用 grow(10) 办法进行扩容，此刻旧数组容量为 oldCapacity=0，新数组容量为 newCapacity=0，而最小容量 minCapacity=10，因为新数组容量小于最小容量，故将新数组容量重新赋值为 newCapacity=minCapacity=10，然后进行数组复制，到此完结扩容操作。

增加第11个元素的进程：

调用 add(e10) 办法增加元素，此刻的 size=10。
调用 ensureCapacityInternal(11) 办法判别是否是默许长度数组，此刻该办法的传参是 size + 1 代表现在列表需求的最小容量。进入该办法后，因为现已超出了默许长度 10，所以这儿 minCapacity 设置为 11。
调用 ensureExplicitCapacity(11) 办法判别是否需求扩容，此刻因为 minCapacity=11 大于数组长度 elementData.length=10 所以需求扩容。
调用 grow(11) 办法进行扩容，此刻旧数组容量为 oldCapacity=10，新数组容量为 newCapacity=15，而最小容量 minCapacity=11，因为新数组容量大于最小容量，故将新数组容量仍旧为15，然后进行数组复制，到此完结扩容操作，新数组的长度扩容到了 15，并将旧数组的元素搬迁到新数组中。

以上便是扩容的全进程，扩容公式为 $n e wC a p a c i t y = o l d C a p a c i t y + (o l d C a p a c i t y >> 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 的扩容机制的内容了，首要总结如下：

ArrayList 是根据动态数组完成的，能够扩容或缩短（缩短能够手动调用 trimToSize() 办法，ArrayList在元素小于一半长度时会自动缩短长度，这儿不作过多说明）数组的巨细然后完成可变长的数组。
ArrayList 中声明了 EMPTY_ELEMENTDATA 和 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 两个字段，虽然都是空数组，但是两者之间有着不同的作用。
ArrayList 的扩容机制选用的是新数组容量扩容为旧数组容量的 1.5 倍。

弥补： ArrayList 供给了 ensureCapacity(int minCapacity) 用于完成手动扩容到指定的容量，这样在需求增加很多数据时能够不用重复进行扩容操作，提高性能。

到这儿便是本篇的一切内容了，ArrayList 类中还有许多有意思的办法，有爱好的读者们能够自行去检查它们的源码。

感谢观看！！！

浅谈 ArrayList 的扩容机制

ArrayList 的结构函数

ArrayList 的扩容机制

总要有总结

相关文章

Docker的网络模式

Deno 1.4 支持 JS 最新的 Temporal API

2023年story的年中总结

支付宝异步通知(notify_url)与return_url.

作者信息