ArrayList 扩容机制是什么？为什么查询快、插入慢？

简化版

ArrayList 底层是一个连续的对象数组。按下标查询能直接算出地址，是 O(1)，所以查询快；中间插入/删除要把后面的元素整体搬移，是 O(n)，所以慢。数组装满了就扩容：新建一个 1.5 倍大的数组，把旧元素全拷过去。

详细版

ArrayList 内部维护一个 Object[] elementData。「查询快」是因为数组内存连续，get(i) 直接用「首地址 + i × 元素大小」算出位置，一步到位；「插入慢」是因为数组要求元素紧挨着排列，在第 0 位插入一个元素，后面所有元素都得右移一格。

扩容流程（以常见实现为准，细节随版本略有差异）：

add 时先检查容量够不够；
不够就调 grow()，新容量 = 旧容量 + 旧容量 >> 1，即约 1.5 倍；
Arrays.copyOf 把旧数组元素复制到新数组。

单次扩容是 O(n)（要拷贝），但连续 add 时扩容并非每次都发生（容量翻倍式增长让扩容次数呈对数级），所以尾部追加的均摊复杂度是 O(1)。

// 已知大概要放 1000 个 → 构造时给容量，避免反复扩容拷贝
List<String> list = new ArrayList<>(1000);

⚠️ 容量（capacity）不是长度（size）。new ArrayList<>(1000) 只是预留了 1000 个槽位，此时 size() 仍是 0。

完整版教学

一、为什么是数组 → 决定了它的全部性能特征

理解 ArrayList 只需抓住一句：它就是一个会自动扩容的数组。数组的物理特性直接决定了它的每一条性能：

随机访问 O(1)：连续内存 + 下标寻址，CPU 缓存也友好（局部性好），实际比链表快得多。
尾部追加均摊 O(1)：有空位直接写，偶尔扩容。
中间/头部插入删除 O(n)：必须搬移元素维持连续性。
按值查找 O(n)：得逐个 equals 比对。

二、扩容为什么选 1.5 倍

扩容倍数是个权衡：

倍数太小（如每次 +1）→ 扩容太频繁，退化成 O(n²)；
倍数太大（如每次 ×2）→ 内存浪费严重，且释放的旧数组无法被后续新数组复用。

1.5 倍是「时间 vs 空间」的折中：既保证均摊 O(1)，又比 2 倍更省内存，而且多次 1.5 倍增长后，累计释放的空间有机会满足下一次扩容的分配需求。

三、为什么预设容量能提升性能

如果你要往一个默认容量 10 的 ArrayList 里加 10 万个元素，它会经历十几次「扩容 + 全量拷贝」，每次拷贝都是 O(n)。而 new ArrayList<>(100000) 一次性分配到位，全程零扩容零拷贝。

记忆点：只要能预估数据量，就在构造时给容量。这是最廉价的性能优化之一。

四、遍历时删除的坑：ConcurrentModificationException

// 错误示例：for-each 里直接 remove，会抛 ConcurrentModificationException
for (String s : list) {
    if (s.isEmpty()) list.remove(s);
}

for-each 底层是迭代器，它会记录一个 modCount（修改次数）。你用 list.remove() 改了 modCount，迭代器下次检查发现对不上，就抛 ConcurrentModificationException（这是 fail-fast 机制）。正确做法：

Iterator<String> it = list.iterator();
while (it.hasNext()) {
    if (it.next().isEmpty()) it.remove();   // 用迭代器自己的 remove
}
// 或 Java 8+： list.removeIf(String::isEmpty);

五、用数字推演扩容与搬移成本

从默认首次容量 10 开始，连续追加时容量大致经历 10 → 15 → 22 → 33 → 49 → 73 → 109。放入第 100 个元素前，旧数组已经被复制多次；这些复制总量仍与最终元素数同阶，所以尾部追加的均摊复杂度是 O(1)，但某一次触发扩容的 add 仍会出现 O(n) 延迟尖峰。

新容量 = 旧容量 + (旧容量 >> 1)
10 + 5 = 15
15 + 7 = 22
22 + 11 = 33

操作	需要移动的元素数（size=1000 示例）	复杂度
`get(700)`	0	O(1)
尾部 `add` 且有空位	0	O(1)
在索引 500 插入	约 500	O(n)
删除索引 0	约 999	O(n)
容量已满时追加	复制约 1000	单次 O(n)

ensureCapacity(n) 适合列表已创建后才知道规模的情况；trimToSize() 可以收缩长期闲置容量，但它同样会复制数组，不能在热路径频繁调用。空间优化也有执行成本，应在数据稳定后再做。

六、常见误区与追问

误区：所有 add 都是 O(1)。 尾部追加只有在不扩容时是常数操作，触发扩容的单次调用要复制整个数组。
误区：new ArrayList<>(1000) 后 size() 就是 1000。 构造参数只是容量，逻辑元素数仍为 0。
误区：删除元素后底层数组自动缩小。 ArrayList 通常保留容量以便复用，需要明确调用 trimToSize() 才收缩。
追问：为什么扩容后旧数组能回收？ elementData 改指向新数组，旧数组无其他引用时才成为 GC 候选；扩容瞬间两份数组会同时占内存。
追问：remove(int) 与 remove(Object) 有什么坑？ List<Integer> 中 remove(1) 删除索引 1，若要删除数值 1 应传 Integer.valueOf(1)。
追问：ArrayList 是否线程安全？ 不是；同步包装只能保护单次方法，复合操作仍需外部同步或选择合适并发集合。

记忆钩子：容量决定“能装多少”，size 决定“已经装了多少”；扩容解决容量，搬移维持连续性。

容量增长还受数组最大长度和 JVM 可用内存限制。一次申请超大数组可能直接抛 OutOfMemoryError，预设容量应来自可信上限，不能把未经校验的用户输入直接当作构造容量。

set(index, value) 只替换已有槽位，不改变 size，也通常不触发结构修改；它和会搬移元素并增加 size 的 add(index, value) 不能混为一谈。

七、加强记忆

ArrayList 的所有行为都由动态数组推导：下标直接寻址带来 O(1) 随机访问，连续布局带来缓存友好，也迫使中间增删搬移元素。容量不足时按约 1.5 倍申请新数组并复制，单次扩容 O(n)，连续尾部追加靠几何增长获得均摊 O(1)。能预估规模就预设容量，遍历删除使用迭代器或 removeIf，并始终区分容量、size 和线程安全三个边界。

简化版

详细版