深入理解 Java 中 ArrayList 的底层原理

奋斗的软件工程师 / 2024-08-23 / 原文

在这篇博客中，我们将深入探讨ArrayList的底层实现原理，并通过逐步剖析ArrayList的源码来理解其内部工作机制。我们将重点关注ArrayList的创建、元素添加、扩容机制等关键点。

创建ArrayList集合对象

ArrayList<String> list = new ArrayList<>();

使用空参构造器创建ArrayList集合对象时，会调用其内部的默认构造方法：

public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

深入解析

DEFAULTCAPACITY_EMPTY_ELEMENTDATA: 这是一个final修饰的静态常量，是一个空的Object数组：
```
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
```
elementData: ArrayList内部用于存储数据的数组。初始时，它指向一个空的Object数组。
```
transient Object[] elementData;
```

关键点总结

利用空参构造器创建ArrayList集合对象时，底层会创建一个长度为0的数组elementData。
DEFAULTCAPACITY_EMPTY_ELEMENTDATA是一个空数组，用于标记集合在添加第一个元素之前的状态。

向集合中添加元素

list.add("Hello World");

添加元素时，ArrayList内部会调用add方法：

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

深入解析

size: 表示ArrayList中当前元素的数量，初始值为0。
ensureCapacityInternal(size + 1): 确保ArrayList内部数组有足够的空间来存储新元素。如果没有足够空间，会触发扩容。
```
private void ensureCapacityInternal(int minCapacity) {
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
```

calculateCapacity: 计算新的容量，如果当前elementData指向DEFAULTCAPACITY_EMPTY_ELEMENTDATA，则返回默认初始容量10。

private static int calculateCapacity(Object[] elementData, int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    return minCapacity;
}

关键点总结

第一次添加元素时，ArrayList内部会创建一个默认长度为10的数组来存储数据。
size表示当前ArrayList中的元素数量，每次添加元素后都会增加。

扩容机制

当ArrayList内部数组的容量不足以容纳新元素时，会触发扩容机制：

private void grow(int minCapacity) {
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    elementData = Arrays.copyOf(elementData, newCapacity);
}

深入解析

扩容规则: ArrayList的容量会增加到原容量的1.5倍（即oldCapacity + (oldCapacity >> 1)）。
Arrays.copyOf: 创建一个新数组，将原数组中的数据复制到新数组中。

关键点总结

ArrayList每次扩容时，容量增加至原来的1.5倍。
扩容后的新数组会替换旧数组，继续存储新元素。

潜在优化与最佳实践

初始容量设置: 如果事先知道需要存储大量数据，可以通过指定初始容量来避免频繁扩容。例如：
```
ArrayList<String> list = new ArrayList<>(100);
```
扩容代价: 每次扩容都会进行数组复制，代价较高。在需要处理大量数据的场景中，建议提前设定合适的初始容量。

通过本文的解析，你应该对ArrayList的底层实现原理有了更加深入的理解。从空参构造到添加元素，再到扩容机制，ArrayList的每一步操作背后都隐藏着精妙的设计和实现逻辑。希望这篇博客能帮助你更好地掌握ArrayList的工作原理，写出更高效的代码。