.ArrayList源码三:数组扩容以及元素拷贝

数组扩容以及元素拷贝 这个 ArrayList 动态性的核心机制。

ArrayList 源码三：数组扩容以及元素拷贝

在之前的文章中，我们已经了解到 ArrayList 底层是基于数组 elementData 实现的。与普通数组不同的是，ArrayList 具有动态扩容的能力，可以根据元素的增加自动调整数组的大小。 这种动态扩容机制是 ArrayList 灵活性的关键，也是面试中常考的点。

本文我们将深入源码，详细分析 ArrayList 的数组扩容过程，以及元素是如何被拷贝到新的数组中的。

回顾：扩容的触发时机

在 ArrayList 中，扩容主要发生在以下两种情况：

1. add(E e) 和 add(int index, E element) 方法添加元素时，如果当前数组容量不足以容纳新元素。 这是最常见的扩容场景。
2. addAll(Collection c) 和 addAll(int index, Collection c) 方法批量添加元素时，如果添加后总元素数量超过当前数组容量。

在这些添加元素的方法中，都会先调用 ensureCapacityInternal(int minCapacity) 方法来确保容量足够，而 ensureCapacityInternal 方法最终会调用 grow(int minCapacity) 方法进行扩容。

1. ensureCapacityInternal(int minCapacity) 方法

我们先回顾一下 ensureCapacityInternal 方法，它负责初步的容量检查和计算：

java复制代码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++; // 结构修改计数器 + 1

    // overflow-conscious code
    if (minCapacity - elementData.length > 0) // 如果最小容量大于当前数组长度，则需要扩容
        grow(minCapacity); // 执行扩容
}

源码分析回顾:

• ensureCapacityInternal(int minCapacity): 入口方法，接收最小所需容量 minCapacity (通常是 size + 1 或 size + collection.size() )。
• calculateCapacity(elementData, minCapacity): 计算实际需要的容量。如果 elementData 是默认空数组 (DEFAULTCAPACITY_EMPTY_ELEMENTDATA)，则初始容量取 DEFAULT_CAPACITY (默认容量，通常为 10) 和 minCapacity 的最大值。否则，直接返回 minCapacity。
• ensureExplicitCapacity(int minCapacity): 显式确保容量。增加结构修改计数器 modCount。关键判断：if (minCapacity - elementData.length > 0): 如果最小所需容量 minCapacity 大于当前数组 elementData 的长度，则说明容量不足，需要调用 grow(minCapacity) 方法进行扩容。

总结 ensureCapacityInternal 的作用:

ensureCapacityInternal 方法的主要作用是判断是否需要扩容，并计算出最小需要的容量 minCapacity。 真正的扩容逻辑在 grow(int minCapacity) 方法中。

2. grow(int minCapacity) 方法 - 数组扩容的核心

grow(int minCapacity) 方法是 ArrayList 数组扩容的核心方法，负责计算新的容量，创建新的数组，并将旧数组的元素拷贝到新数组中。

java复制代码private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length; // 获取旧容量
    int newCapacity = oldCapacity + (oldCapacity >> 1); // 新容量 = 旧容量 + 旧容量/2 (大约 1.5 倍扩容)
    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. int oldCapacity = elementData.length;: 获取旧容量。 oldCapacity 记录了扩容前的数组长度。
2. int newCapacity = oldCapacity + (oldCapacity >> 1);: 计算新容量。
3. oldCapacity >> 1 相当于 oldCapacity / 2 (右移一位，位运算效率更高)。
4. newCapacity = oldCapacity + (oldCapacity >> 1); 扩容到大约 1.5 倍。 这是 ArrayList 默认的扩容策略，每次扩容大约增加 50% 的容量。 例如，如果旧容量是 10，新容量就是 10 + 5 = 15。
5. if (newCapacity - minCapacity < 0): 处理新容量仍然不足的情况。
6. 有些情况下，例如一次性添加大量元素，按照 1.5 倍扩容可能仍然小于所需的最小容量 minCapacity。
7. 如果 newCapacity < minCapacity，则 newCapacity = minCapacity; 直接将新容量设置为最小容量 minCapacity，确保容量至少能够容纳所需的元素。
8. if (newCapacity - MAX_ARRAY_SIZE > 0): 处理新容量超过最大数组大小的情况。
9. MAX_ARRAY_SIZE 通常为 Integer.MAX_VALUE - 8，是数组可以分配的最大大小限制 (减 8 是为了保留一些空间给 JVM)。
10. 如果计算出的新容量 newCapacity 超过 MAX_ARRAY_SIZE，则调用 hugeCapacity(minCapacity) 方法进一步处理超大容量。
11. elementData = Arrays.copyOf(elementData, newCapacity);: 数组复制，完成扩容的关键步骤！
12. Arrays.copyOf(elementData, newCapacity) 方法是 Java 提供的一个用于数组复制的工具方法。
13. 作用:创建一个新的数组，长度为 newCapacity。将旧数组 elementData 中的元素复制到新数组中。返回新数组的引用。
14. elementData = Arrays.copyOf(...): 将 Arrays.copyOf 返回的新数组的引用赋值给 elementData，使得 ArrayList 的内部数组 elementData 指向了新的、扩容后的数组。 旧的数组会被垃圾回收器 (GC) 回收 (如果没有其他引用指向它)。

3. hugeCapacity(int minCapacity) 方法 - 超大容量处理

hugeCapacity(int minCapacity) 方法处理当计算出的新容量超过 MAX_ARRAY_SIZE 时的情况。

java复制代码private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0 overflow throw new outofmemoryerror return mincapacity> MAX_ARRAY_SIZE) ?
        Integer.MAX_VALUE : // 如果最小容量超过最大数组大小，则返回 Integer.MAX_VALUE
        MAX_ARRAY_SIZE; // 否则返回最大数组大小
}

源码分析:

• if (minCapacity < 0): 溢出检查。 如果 minCapacity 小于 0，说明计算过程中发生了溢出，抛出 OutOfMemoryError。
• return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;: 确定最终容量。如果 minCapacity 仍然大于 MAX_ARRAY_SIZE，则返回 Integer.MAX_VALUE (理论上的最大容量)。 这意味着 ArrayList 尽最大努力去满足容量需求，即使超过了 MAX_ARRAY_SIZE，也尝试分配接近 Integer.MAX_VALUE 的容量。否则 (如果 minCapacity 没有超过 MAX_ARRAY_SIZE)，则返回 MAX_ARRAY_SIZE。 将容量限制在 MAX_ARRAY_SIZE 以内。

总结 grow 方法的扩容步骤:

1. 计算新容量 newCapacity: 通常扩容到旧容量的 1.5 倍，并考虑最小容量 minCapacity 和最大数组大小 MAX_ARRAY_SIZE 的限制。
2. 使用 Arrays.copyOf 创建新数组并复制元素: 这是扩容的核心步骤，将旧数组的数据复制到新数组中。
3. 更新 elementData 指向新数组: 使 ArrayList 内部使用新的、扩容后的数组。

4. Arrays.copyOf(Object[] original, int newLength) - 元素拷贝的关键

Arrays.copyOf 方法是 Java 标准库中用于数组复制的非常重要的工具方法。 我们来简单了解一下它的原理。

Arrays.copyOf 方法的源码 (简化版，实际是 native 方法)：

java复制代码public static  T[] copyOf(T[] original, int newLength) {
    Class copyType = original.getClass();
    T[] copy = (T[]) Array.newInstance(copyType.getComponentType(), newLength); // 创建新数组
    System.arraycopy(original, 0, copy, 0, Math.min(original.length, newLength)); // 元素拷贝
    return copy;
}

源码分析 (简化版):

1. Class copyType = original.getClass();: 获取原始数组 original 的类型。
2. T[] copy = (T[]) Array.newInstance(copyType.getComponentType(), newLength);: 创建新的数组 copy。
3. Array.newInstance(componentType, length) 是 Java 反射机制中用于动态创建数组的方法。
4. copyType.getComponentType() 获取数组元素的类型 (例如，如果 original 是 String[]，则 componentType 就是 String.class)。
5. newLength 是新数组的长度。
6. Array.newInstance 会根据指定的元素类型和长度，创建一个新的数组。
7. System.arraycopy(original, 0, copy, 0, Math.min(original.length, newLength));: 使用 System.arraycopy 进行元素拷贝。
8. System.arraycopy 是一个 native 方法，由 JVM 底层实现，效率非常高，专门用于数组元素拷贝。
9. src: original (源数组，即旧数组)。
10. srcPos: 0 (源数组的起始位置，从索引 0 开始拷贝)。
11. dest: copy (目标数组，即新数组)。
12. destPos: 0 (目标数组的起始位置，从索引 0 开始存放)。
13. length: Math.min(original.length, newLength) (要拷贝的元素数量，取原始数组长度和新数组长度的最小值，防止越界)。
14. System.arraycopy 会将 original 数组中的元素，从索引 0 开始，拷贝到 copy 数组中，从索引 0 开始，拷贝 length 个元素。
15. return copy;: 返回新数组 copy 的引用。

Arrays.copyOf 的关键点:

• 创建新数组: Arrays.copyOf 会创建一个全新的数组，而不是在原数组上进行修改。
• System.arraycopy 高效拷贝: 使用 System.arraycopy 进行元素拷贝，效率很高，底层优化。
• 浅拷贝 (Shallow Copy): Arrays.copyOf 执行的是 浅拷贝。对于基本数据类型 (int, long, float, double, boolean, byte, char, short)，是直接拷贝值。对于引用数据类型 (对象)，拷贝的是对象的引用，而不是对象本身。 这意味着新数组和旧数组中的引用指向的是同一个对象。 如果对象是可变的，修改其中一个数组中的对象，会影响到另一个数组。

5. 扩容的性能影响

ArrayList 的扩容操作虽然实现了动态性，但也带来一定的性能开销。

• 时间复杂度: grow 方法和 Arrays.copyOf 方法的时间复杂度都是 O(n)，其中 n 是旧数组的长度。 因为需要创建新数组，并将旧数组的所有元素都拷贝到新数组中。
• 内存开销: 扩容会创建新的数组，占用额外的内存空间。 虽然旧数组会被 GC 回收，但在扩容过程中，会短暂地存在两个数组，增加内存压力。

扩容的均摊时间复杂度:

虽然单次扩容操作是 O(n) 的，但由于扩容是指数级增长 (大约 1.5 倍)，所以对于多次 add(E e) 操作，均摊下来的时间复杂度接近 O(1)。 也就是说，大部分 add(E e) 操作都是 O(1) 的，只有少数操作会触发扩容，导致 O(n) 的开销。

优化扩容性能的策略:

• 预估容量，设置初始容量: 如果在创建 ArrayList 时，能够预估到大概需要存储多少元素，可以通过构造器 ArrayList(int initialCapacity) 设置初始容量。 这样可以减少扩容次数，提高性能。
• 使用 ensureCapacity(int minCapacity) 方法: 如果事先知道要添加大量元素，可以使用 ensureCapacity(int minCapacity) 方法提前扩容，一次性分配足够的空间，避免多次小幅度的扩容。

总结

本文我们深入分析了 ArrayList 的数组扩容机制，重点理解了 grow(int minCapacity) 方法和 Arrays.copyOf 方法的工作原理。

核心要点回顾:

• 扩容触发: 添加元素时，容量不足会触发扩容。
• grow(int minCapacity) 方法: 扩容的核心方法，计算新容量，调用 Arrays.copyOf 拷贝元素。
• 扩容策略: 默认扩容到旧容量的 1.5 倍左右。
• Arrays.copyOf(Object[] original, int newLength): 数组复制的关键方法，创建新数组，使用 System.arraycopy 高效拷贝元素，执行浅拷贝。
• 性能影响: 扩容操作是 O(n) 的，但均摊时间复杂度接近 O(1)。
• 优化策略: 预估容量，设置初始容量，使用 ensureCapacity 方法。

理解 ArrayList 的扩容机制，有助于我们更好地掌握 ArrayList 的特性，并在实际开发中根据场景选择合适的初始容量，优化性能。

在下一篇文章中，我们可以继续探讨 ArrayList 的迭代器、fail-fast 机制以及其他更高级的特性，进一步深入 ArrayList 源码的世界。