1. ArrayList扩容步骤

主要分两步:

  1. 扩容: 将数组复制到另一个长度更大的数组中
  2. 添加元素: 把新元素添加到扩容以后的数组中

2. 扩容源码解析

相关参数

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 = {};

/**
 * 保存ArrayList数据的数组
 */
transient Object[] elementData; // non-private to simplify nested class access

/**
 * ArrayList 所包含的元素个数
 */
private int size;

构造方法

/**
 * 带初始容量参数的构造函数(用户可以在创建ArrayList对象时自己指定集合的初始大小)
 */
public ArrayList(int initialCapacity) {
    if (initialCapacity > 0) {
        //如果传入的参数大于0,创建initialCapacity大小的数组
        this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == 0) {
        //如果传入的参数等于0,创建空数组
        this.elementData = EMPTY_ELEMENTDATA;
    } else {
        //其他情况,抛出异常
        throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
    }
}

/**
 *默认无参构造函数
 *DEFAULTCAPACITY_EMPTY_ELEMENTDATA 为0.初始化为10,
 *也就是说初始其实是空数组 当添加第一个元素的时候数组容量才变成10
 */
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

扩容的方法: add(E e)addALL(Collection<? extends E> c)

主要看下add(E e)

public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // 第一步: 增加数组长度
    elementData[size++] = e;           // 第二步: 添加元素到数组
    return true;
}

调用ensureCapacityInternal 得到最小扩容量,这个方法会判断ArrayLists是否初始化,如果未初始化,则将数组大小初始化为默认大小DEFAULT_CAPACITY ,即 10 ,否则容量设置为传入的minCapacity

private void ensureCapacityInternal(int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        // 获取“默认的容量”和“传入参数”两者之间的最大值
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    ensureExplicitCapacity(minCapacity);
}

最后调用ensureExplicitCapacity方法,先判断是否需要扩容,如果需要扩容则调用grow()方法进行扩容

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

grow(int minCapacity) 是扩容的核心方法

private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;    // oldCapacity为旧容量,newCapacity为新容量
    int newCapacity = oldCapacity + (oldCapacity >> 1); // 新容量更新为旧容量的 1.5 倍
     //然后检查新容量是否大于最小需要容量,
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
         //再检查新容量是否超出了ArrayList所定义的最大容量,
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // minCapacity is usually close to size, so this is a win:
    elementData = Arrays.copyOf(elementData, newCapacity);
}

3. ArrayList扩容机制总结

初始化一个ArrayList集合还没有添加元素时,其实它是个空数组,只有当我们添加第一个元素时,内部会返回最小容量10,也就是说ArrayList初始化容量为10。当最小容量大于当前数组的长度时,便开始可以扩容了,ArrayList扩容的真正计算是在一个grow()方法里面,新数组大小是旧数组的1.5倍,如果扩容后的新数组大小还是小于最小容量,那新数组的大小就是最小容量的大小,后面会调用一个Arrays.copyof()方法,这个方法是真正实现扩容的步骤。

最后修改:2022 年 05 月 05 日
请博主喝杯咖啡~~~