Java ArrayList扩容机制原理深入分析

在 Java 中，ArrayList 是一种动态数组，它可以自动扩容以适应数据的增长。了解 ArrayList 扩容机制的原理，有助于我们更好地理解和使用 ArrayList，提高代码效率。

ArrayList 扩容机制

ArrayList 内部使用数组来存储元素，当向 ArrayList 中添加元素时，如果当前数组已满，就需要扩容。下面是 ArrayList 扩容的基本流程：

1. 获取当前 ArrayList 的容量 capacity 和当前 ArrayList 已存储的元素个数 size；
2. 判断当前数组是否已满，即 size == capacity；
3. 如果数组已满，创建一个新的容量是原来容量 1.5 倍的数组，并将原数组中的元素复制到新数组中；
4. 新数组成为 ArrayList 的内部数组。

下面是一个简单的示例：

import java.util.ArrayList;

public class Demo {
    public static void main(String[] args) {
        ArrayList<Integer> list = new ArrayList<>(3);
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(4);
        list.add(5);
        list.add(6);
    }
}

在上面的例子中，我们创建了一个容量为 3 的 ArrayList，并往里面添加了 6 个元素。在添加第 4 个元素时，由于数组已满，系统调用了 grow() 方法进行扩容。下面是 grow() 方法的源码：

private void grow(int minCapacity) {
    // 获取当前 ArrayList 容量
    int oldCapacity = elementData.length;
    // 计算新容量大小
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    // 如果新容量不足以满足最小容量需求，就使用最小容量作为新容量
    if (newCapacity < minCapacity)
        newCapacity = minCapacity;
    // 创建新的数组，并将原数组的元素复制到新数组中
    elementData = Arrays.copyOf(elementData, newCapacity);
}

可以看到，在扩容时，系统会计算出新的容量大小，并将原数组的元素复制到新数组中，从而保证数据的顺序不变。需要注意的是，在计算新容量大小时，采用了位运算 >> 来代替除法，以提高代码效率。

另外，在调用 grow() 方法扩容时，如果我们向 ArrayList 中添加大量元素，扩容的次数可能很多，从而导致效率降低。因此，我们在使用 ArrayList 时，尽量预留一定的容量，避免频繁扩容。

下面是一个添加 100 000 个元素的例子，可以看到，在初始容量为 100 000 的情况下，并不会出现扩容的情况：

import java.util.ArrayList;

public class Demo {
    public static void main(String[] args) {
        ArrayList<Integer> list = new ArrayList<>(100000);
        for (int i = 0; i < 100000; i++) {
            list.add(i);
        }
    }
}

阅读剩余 27%