ArrayList 扩容源码浅析

ArrayList

一.概述

ArrayList是List接口下的一个实现类，它可以动态的修改数组，数组元素①有序②可重复；
ArrayList中维护了一个Object类型的数组 elementData ；
可以加入null，并且可以加入多个；
ArrayList基本等同于Vector，但是ArrayList是线程不安全的；

二.扩容

首先ArrayList底层是一个 Object[ ] elementData 数组；

add()

尝试插入一个元素的时候，会调用add方法，先判断是否需要扩容，将元素个数size+1作为参数传入 ensureCapacityInternal；

public boolean add(E e) {
    // 确认插入这个元素以后是否需要扩容 ？
    ensureCapacityInternal(size + 1);
    // 添加元素至数组尾部
    elementData[size++] = e;
    return true;
}

ensureCapacityInternal()

size+1作为参数 minCapacity 传进来后，在 calculateCapacity 方法中，和DEFAULT_CAPACITY (10)比较，10 > 1，所以calculateCapacity方法返回 10；
即如果数组为空，则初始化为10；

private void ensureCapacityInternal(int minCapacity) {
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
    
private static int calculateCapacity(Object[] elementData, int minCapacity) {
    // 如果当前的这个数组是DEFAULTCAPACITY_EMPTY_ELEMENTDATA，则直接扩容到DEFAULT_CAPACITY，也就是说，第一次add元素的时候会扩容到10
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
       return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    return minCapacity;
}

ensureExplicitCapacity()

将 calculateCapacity 的返回值作为参数 minCapacity ，调用 ensureExplicitCapacity() 方法，判断：如果minCapacity 大于elementData 长度时，触发扩容 grow方法；

private void ensureExplicitCapacity(int minCapacity) {
    modCount++;
    // 判断插入了当前元素后是否超过了数组的容量，是的话调用grow方法扩容 
    if (minCapacity - elementData.length > 0)
      grow(minCapacity);
}

private void grow(int minCapacity) {
    // overflow-conscious code
    // 记录原来数组的长度
    int oldCapacity = elementData.length;
    // 新的容量就是原来数组长度的 1.5 倍，这里使用右移效率更高
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    // 如果新的容量比最小容量小，就直接把最小容量赋值给新的容量
    // 如果不是，就不用变化
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    // 如果超出临界值，就调用 hugeCapacity 方法
    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);
}

// 临界值
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

总结：

add()添加元素时，先判断数组是否需要扩容，将size+1作为参数传入 ensureCapacityInternal，判断size+1是否小于10，如果当前是即数组为空，就将容量初始化为10；
ensureCapacityInternal 会执行 ensureExplicitCapacity ，参数是minCapacity也就是之前的siez+1，而当 minCapacity 大于elementData长度length时，触发扩容 grow；
使用>>1 右移操作将 length扩大为之前的1.5倍并创建新数组，使用Arrays.copyOf 将元素复制到新数组；

参考：
https://blog.csdn.net/efggfxfvhh/article/details/126432671
https://blog.csdn.net/m0_52462015/article/details/121552324
https://blog.csdn.net/m0_56085369/article/details/124182172

文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/89165.html