关于ArrayList的动态扩容机制解读

2022-11-13 18:11:20 扩容机制解读

1. 前言

对于 ArrayList 的动态扩容机制想必大家都听说过，之前的文章中也谈到过，不过由于时间久远，早已忘却。

所以利用这篇文章做做笔记，加深理解记忆

2. ArrayList 的动态扩容机制

要了解其动态扩容机制就必须先看它的源码，源码是基于 jdk 1.8 的

2.1. ArrayList 的主要属性

// 如果不指定容量（空构造器）,则在添加数据时的空构造器默认初始容量最小为 10
private static final int DEFAULT_CAPACITY = 10;
// 出现在需要用到空数组的地方，其中一处是使用自定义初始容量构造方法时候如果你指定初始容量为0的时候，那么elementData指向该数组
// 另一处是使用包含指定collection集合元素的列表的构造方法时，如果被包含的列表中没有数据，那么elementData指向该数组
private static final Object[] EMPTY_ELEMENTDATA = {};
// 如果使用默认构造方法，那么elementData指向该数组
// 在添加元素时会判断是否是使用默认构造器第一次添加，如果是数组就会扩容至10个容量
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
// 默认未初始化的储存 ArrayList集合元素的底层数组,其长度就是 ArrayList的容量
transient Object[] elementData;
// 私有的elementData数组中具体的元素对象的数量,可通过size方法获得。默认初始值为0，在add、remove等方法时size会改变
private int size;

可以看到 ArrayList 底层核心是一个 Object[] elementData 的数组

2.2. ArrayList 的构造器

// 默认的构造器
public ArrayList() {
	// Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {} 空数组
	this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
// 自定义容量大小的构造器
public ArrayList(int initialCapacity) {
	if (initialCapacity > 0) {
		this.elementData = new Object[initialCapacity];
	} else if (initialCapacity == 0) {
		this.elementData = EMPTY_ELEMENTDATA;
	} else {
		throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
	}
}

从上面的构造器中，可以得出以下结论

如果使用 ArrayList 的默认构造器时，它的初始容量就是 0
如果使用 ArrayList 的有参构造器时，它的初始容量就是你传入的参数 initialCapacity的值

2.3. ArrayList 的动态扩容

根据上面的两个结论，不管是使用默认或有参构造器时，我们可以使其初始容量为 0，那么它的动态扩容发生在哪里？

可以肯定就发生在 add() 方法中，那么查看 add() 方法源码如下

public boolean add(E e) {
	// ensureCapacityInternal() 如下
	ensureCapacityInternal(size + 1);  // Increments modCount!!
	elementData[size++] = e;
    return true;
}

按照我们第一次 add， size 肯定是 0 了，所以 ensureCapacityInternal 这个函数传入的是 1

// 第一次 add 时，参数 minCapacity = 1
private void ensureCapacityInternal(int minCapacity) {
	ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
// calculateCapacity() 方法
private static int calculateCapacity(Object[] elementData, int minCapacity) {	
	// 如果是第一次 add 元素
	if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
		// minCapacity 设置为 DEFAULT_CAPACITY 与 minCapacity 的最大值
		return Math.max(DEFAULT_CAPACITY, minCapacity);
	}
    return minCapacity;
}
// ensureExplicitCapacity() 方法
private void ensureExplicitCapacity(int minCapacity) {
        modCount++;
	// overflow-conscious code
	if (minCapacity - elementData.length > 0)
		grow(minCapacity);
}

elementData.length 是数组长度，它是随着数组扩容而动态变化的

如果是第一次 add 元素时，它为 0
之后它是随着 oldCapacity + (oldCapacity >> 1) 而动态变化的

首先看 calculateCapacity() 方法

如果是第一次 add 元素，那么 minCapacity 设置为 DEFAULT_CAPACITY 与 minCapacity 的最大值，即 10 与 1 取最大值，这里返回最大值 10
否则，直接返回 minCapacity

再看 ensureExplicitCapacity() 方法

如果是第一次 add 元素，由上面方法可知 minCapacity = 10，即 10 - 0 > 0 返回 true，再调用 grow() 方法
只要 minCapacity - elementData.length > 0 为 true，就会再调用 grow() 方法

private void grow(int minCapacity) {
    // 原容量
    int oldCapacity = elementData.length;
    // 扩容后的容量，扩大到原容量的 1.5 倍左右，右移一位相当于原数值除以 2 的商
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    // 如果新容量减去最小容量的值小于 0
    if (newCapacity - minCapacity < 0)
        // 新容量等于最小容量
        newCapacity = minCapacity;
    // 如果新容量减去建议最大容量的值大于 0
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        // 调整新容量上限或者抛出 OutOfMemoryError
        newCapacity = hugeCapacity(minCapacity);
        
     // 最终进行新数组的构建和重新赋值，此后原数组被摒弃
     // elementData:原数组; newCapacity:新数组容量
    elementData = Arrays.copyOf(elementData, newCapacity);
}

elementData.length 是数组长度，它是随着数组拷贝而动态变化的

如果是第一次 add 元素时，它为 0
之后它是随着 oldCapacity + (oldCapacity >> 1) 而动态变化的

如果是第一次 add 元素，由上面的方法可知参数 minCapacity = 10，第一次 add 元素 oldCapacity = 0，可得知 newCapacity = 0 + 0，由于 newCapacity - minCapacity < 0，所以 newCapacity = minCapacity = 10 重新赋值，最终进行新数组的构建和拷贝赋值

3. 小结

3.1. 初始容量

如果使用 ArrayList 的默认无参构造器时，它的初始容量就是 0

如果使用 ArrayList 的有参构造器时，它的初始容量就是你传入的参数 initialCapacity的值

3.2. 动态扩容大小

ArrayList 的初始容量为 0，当第一次 add 元素时，才会发生扩容操作，它的扩容大小是 10

当第一次 add 元素完成后，此时的 elementData.length = 10，后面要想发生扩容操作，必须 minCapacity - elementData.length > 0 为 true，即 minCapacity 最小为 11，也就是说当 ArrayList 第十一次 add 时，才会接着发生扩容操作，且扩容大小为 15 = 10 + 5

3.3. 动态扩容大小测试

public class TestArrayList {
    public static void main(String[] args) {
        List<Integer> list = new ArrayList<>();
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(4);
        list.add(5);
        list.add(6);
        list.add(7);
        list.add(8);
        list.add(9);
        list.add(10);
        list.add(11);// 打上断点
    }
}

add() 方法打上断点