数组：从连续内存到 ArrayList 扩容

我真正开始理解“数组：从连续内存到 ArrayList 扩容”，不是在背完某段代码之后，而是在一次次写错之后。最明显的问题是：数组看起来是最简单的数据结构，但我以前只记住下标访问快，没有认真想过连续内存、扩容复制和缓存局部性。把这些错误重新摊开来看，我才找到比口诀更可靠的理解方式。

数组的核心能力不是“能装很多元素”，而是通过连续存储和固定步长，把下标直接换算成位置。这就是随机访问 O(1) 的来源。

它从哪里来

数组没有单一的“发明时刻”。它来自数学表格与连续存储的直接结合：同类数据按固定宽度排在一起，就能用序号计算位置。二十世纪五十年代的 Fortran 等早期高级语言把数组变成语言级能力，此后它一直是数值计算、图像处理和其他结构的内存底座。

为什么下标访问很快

假设数组起始地址为 base，每个元素占 w 个字节，那么第 i 个元素的位置可表示为：

数组连续内存、地址计算、扩容和搬移图

图：数组的随机访问、扩容复制与中间插入

计算不依赖数组长度，因此访问时间不会随数据量线性增长。连续布局也更容易被 CPU 预取和缓存命中，这一点是复杂度表看不到、却会影响真实性能的优势。

动态数组解决了什么

普通数组创建后容量固定。ArrayList 在它外面增加了三个概念：

size：已经保存的元素数。
capacity：底层数组当前容量。
扩容策略：容量不足时申请更大的数组并复制元素。

public final class SimpleArrayList<E> {
    private Object[] elements = new Object[8];
    private int size;

    public void add(E value) {
        ensureCapacity(size + 1);
        elements[size++] = value;
    }

    @SuppressWarnings("unchecked")
    public E get(int index) {
        rangeCheck(index);
        return (E) elements[index];
    }

    public void add(int index, E value) {
        if (index < 0 || index > size) throw new IndexOutOfBoundsException();
        ensureCapacity(size + 1);
        System.arraycopy(elements, index, elements, index + 1, size - index);
        elements[index] = value;
        size++;
    }

    private void ensureCapacity(int required) {
        if (required <= elements.length) return;
        int next = Math.max(required, elements.length + (elements.length >> 1));
        elements = java.util.Arrays.copyOf(elements, next);
    }

    private void rangeCheck(int index) {
        if (index < 0 || index >= size) throw new IndexOutOfBoundsException();
    }
}

为什么追加是“摊销 O(1)”

动态数组追加摊销复杂度图

图：扩容峰值分摊到连续追加后的总体成本

大部分追加只写入下一个空槽，成本是 O(1)；少数追加会触发扩容，需要复制已有的 n 个元素，单次成本为 O(n)。由于容量按比例增长，扩容不会每次发生，把多次追加的总成本平均后仍可视为摊销 O(1)。

如果每次只增加一个槽位，连续追加 n 个元素就会发生大量重复复制，总成本接近 O(n²)。所以增长因子是在内存浪费和复制频率之间取平衡。

插入、删除为什么需要搬移

数组必须保持连续。向中间插入时，后面的元素整体右移；删除后则整体左移。System.arraycopy 虽然很快，但搬移数量仍随尾部元素数量增长。

操作	复杂度
按下标读取或修改	`O(1)`
尾部追加	摊销 `O(1)`
中间插入、删除	`O(n)`
按值查找	`O(n)`

删除实现除了搬移，还要主动释放末尾引用：

@SuppressWarnings("unchecked")
public E remove(int index) {
    rangeCheck(index);
    E old = (E) elements[index];
    int moved = size - index - 1;
    if (moved > 0) {
        System.arraycopy(elements, index + 1, elements, index, moved);
    }
    elements[--size] = null;
    return old;
}

如果不清空槽位，逻辑上已经删除的对象仍被数组引用，垃圾回收器无法回收，这类问题常被称为“过期引用滞留”。

数组的内存模型

Java 对象数组保存的是引用，不是对象本体。new User[100] 创建了一百个引用槽位，并没有创建一百个 User。基本类型数组则直接保存值，因此 int[] 比 Integer[] 紧凑得多。

二维数组在 Java 中实际是“数组的数组”，每一行可以有不同长度：

int[][] triangle = {
    {1},
    {2, 3},
    {4, 5, 6}
};

它不保证所有数据构成一整块矩形连续内存。进行矩阵计算时，访问顺序仍会影响局部性，按行遍历通常更自然。

扩容策略怎样选择

增长太小会频繁复制，增长太大又长期占用未使用空间。常见策略是 1.5 倍或 2 倍，但没有脱离场景的最佳值：

数据最终规模可预估：直接设置接近目标的初始容量。
内存紧张且增长缓慢：较小增长因子更节省空间。
高吞吐追加：较大增长因子减少复制频率。
低尾延迟：避免运行时集中扩容，或使用分段结构。

缩容同样不能在每次删除后发生，否则容量会在阈值附近反复抖动。通常要设置更低的缩容阈值，形成迟滞区间。

稀疏数据不一定适合大数组

如果索引范围是十亿，但只保存几百个值，直接分配巨大数组会浪费空间。此时可使用 Map、稀疏数组或压缩坐标。反过来，索引紧凑且访问频繁时，数组通常比 Map 更快、更省元数据。

迭代与并发修改

自定义动态数组若提供迭代器，应记录结构修改次数 modCount。迭代开始时保存期望值，每次 next 检查是否变化，从而快速失败。它不是线程安全机制，只是尽早暴露错误用法。

多线程共享动态数组时，要明确读写所有权。CopyOnWriteArrayList 适合读多写极少，因为每次写入都会复制数组；它不适合高频更新。

测试清单

初始容量为 0、1 和普通值。
恰好填满后再追加，验证扩容与元素顺序。
在头、中间、尾插入和删除。
删除后检查末尾槽位为 null。
非法负索引、index == size 的读写边界。
大量随机操作与 java.util.ArrayList 对照。

工程中的选择

元素数量大致可知时，提前设置初始容量，减少扩容与瞬时内存峰值。
需要频繁按索引读取时，ArrayList 通常是默认选择。
只在两端进出时，用 ArrayDeque 表意更准确。
需要按键查找时，不要循环扫描数组，应考虑 Map 或建立索引。
对原始数值进行密集计算时，int[] 往往比 List<Integer> 更省空间，因为没有装箱对象开销。

数组最容易被低估的优势是简单、紧凑、缓存友好。很多高性能结构最终仍然回到数组上，只是在它上面增加索引、环形边界或堆序关系。

自测

size 与 capacity 有什么区别？
为什么按比例扩容能保证追加的摊销复杂度？
删除元素后为什么通常要清空最后一个槽位？
ArrayList 与 LinkedList 之间不能只根据大 O 作判断的原因是什么？