【2021-07-02】了解 ArrayList 的扩容机制吗？扩容因子是多少？为什么？

每日一题 /

请移步至：每日一题查看更多的题目～

答：

我们来看下 ArrayList 的 add 方法：

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

private void ensureCapacityInternal(int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    ensureExplicitCapacity(minCapacity);
}

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

每次向 ArrayList 中添加一个元素时，都会先执行 ensureCapacityInternal 方法，确保 ArrayList 底层数组 elementData 的容量是够用的，如果 elementData 容量不为空，则执行 ensureExplicitCapacity 方法。

ensureExplicitCapacity 方法中进行判断：如果当前 ArrayList 的 size + 1 大于 elementData 的容量大小，则执行扩容方法 grow

grow

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);
}

我们看到，在 grow 方法中，声明了新容量的大小 newCapacity：

int newCapacity = oldCapacity + (oldCapacity >> 1);

其大小为旧容量（oldCapacity）的 1.5 倍，而扩容的操作实质是开辟了新的数组空间，使用 Arrays.copyOf 方法将旧数组的所有元素写入到新的数组中。

所以，ArrayList 的扩容因子为 1.5。

那么，为何扩容因子被设计成 1.5 倍呢？

假定，我们每次只向 ArrayList 中添加一个元素，如果此时 ArrayList 底层数组已满就使用增长因子 k 来进行扩容。