ArrayList 深入浅出

ArrayList

特点：按添加顺序排列、可重复、非线程安全；
底层实现：数组
扩容原理：初始化集合时，默认容量为 0，第一次添加元素时扩容为 10，容量不够时扩容为原来容量的 1.5 倍。

这里扩容指的是无参构造初始化时的场景。对于指定集合长度的构造函数初始化时，初始容量为指定长度，容量不够时再扩容为原来的 1.5 倍。

下面主要介绍无参构造初始化时的场景。

初始化-构造函数

参数定义：

transient Object[] elementData; // 实际存储数据的数组缓冲区

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; // 初始数组

默认初始化非常简单，调用无参构造器，初始化一个空数组。真正扩容的逻辑在每次添加元素执行。

/**
 * Constructs an empty list with an initial capacity of ten.
 */
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

添加元素-扩容

添加方法：

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

size：ArrayList 的长度，可用 List#size() 获取

添加方法一共做了两件事：

判断数组容量是否足够，不够则给数组扩容；
向数组中添加指定的元素；

添加元素不用多说，向数组中的下一个位置插入即可。下面着重介绍容量判断的逻辑：

1. 判断容量大小

首先判断当前集合容量大小是否足够，如果不够就调用扩容方法 grow(int minCapacity)。

// 确保集合可以添加下一个元素 minCapacity：当前需要的最小容量
private void ensureCapacityInternal(int minCapacity) {
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

// 计算添加元素需要的最小容量
private static int calculateCapacity(Object[] elementData, int minCapacity) {
    // 如果当前集合为空，判断所需最小容量和默认容量大小，返回较大值
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    return minCapacity;
}

// 确保集合可以满足需要的最小容量
private void ensureExplicitCapacity(int minCapacity) {
    modCount++;

    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

2. 扩容方法

private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    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);
}

旧容量为当前数组长度；
新容量为旧容量的 1.5 倍；（此处通过位运算计算，右移1位相当于除以 2，再加原来值即扩大1.5倍）
如果新容量小于所需最小容量，则将新容量赋值为所需最小容量；（这里主要执行场景为集合初始化时，旧容量为0，新容量扩大1.5倍后也为0，这时新容量将被赋值为默认容量 10）
如果新容量超过最大数组大小（int 最大值 - 8），这时会报内存溢出或扩容为 int 的最大取值。
最后将原来数组数据复制到扩容到新容量大小的数组中。

添加元素-实际流程

首先初始化一个 ArrayList，向里面循环添加 11 个元素。下面针对于第一次添加和第11次添加分别查看数组初始化和数组扩容的逻辑。

public static void main(String[] args) {
    List<string> list = new ArrayList<>();

    for (int i = 0; i < 11; i++) {
        list.add("items");
    }
}