# 14. 为什么扩容时会创建一个更大的数组，而不是直接动态扩展？

# 标准答案

ArrayList 扩容时采用创建新数组并拷贝旧数据的方式，而不是动态扩展，主要原因是 Java 数组在内存中是连续存储的，不能动态增长。如果要支持动态扩展，就需要使用链式结构（如 LinkedList），但这会牺牲随机访问性能。因此，ArrayList 采用 1.5 倍扩容策略，在平衡内存占用和性能的同时，减少扩容带来的性能损耗。

# 答案解析

# 1. 为什么不能直接动态扩展数组？

（1）Java 数组是固定长度的
在 Java 语言中，int[] arr = new int[10] 表示 arr 只能存储 10 个元素，无法再扩展。原因是：

• 数组是连续内存块，长度一旦确定，就不能调整。
• JVM 不支持动态增长数组，只能创建新数组并拷贝数据。

（2）如果允许动态扩展，会带来哪些问题？

• 内存碎片问题：如果数组要动态增长，需要在原数组后面留出额外空间，但这在堆内存管理中难以保证。
• CPU 缓存友好性下降：链式结构（如 LinkedList）虽然能动态增长，但指针存储额外消耗 8-16 字节，同时降低 CPU 缓存命中率，导致查询效率变差。
• JVM 不支持：Java 没有像 C 语言的 realloc() 函数，无法对数组进行原地扩展。

# 2. ArrayList 扩容的底层实现

private void grow(int minCapacity) {
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1); // 扩容 1.5 倍
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    elementData = Arrays.copyOf(elementData, newCapacity);
}

扩容过程：

1. 计算新容量 newCapacity = oldCapacity + (oldCapacity >> 1)，约为 1.5 倍。
2. 调用 Arrays.copyOf() 创建更大的新数组，并拷贝数据。
3. 旧数组变为垃圾，等待 GC 释放。

扩容的性能代价

• O(n) 时间复杂度：需要拷贝 n 个元素到新数组。
• GC 压力：旧数组被丢弃，可能导致垃圾回收（GC 暂停）。

# 3. 为什么扩容是 1.5 倍，而不是 2 倍？

• 空间利用率 vs 复制成本：
  • 2 倍扩容会导致更大的内存浪费，特别是在大量 ArrayList 实例时，会影响整体可用内存。
  • 1.5 倍扩容在 减少复制次数 和 节约内存 之间做了折中。
• JVM 内存分配机制优化：
  • 1.5 倍扩容使得数组在堆上存储时更容易找到合适的连续内存块，减少碎片化问题。

# 4. 为什么不使用 LinkedList 替代 ArrayList？

LinkedList 采用链表结构，可以动态扩展，但存在严重的性能缺陷：

• 遍历速度慢：LinkedList 由于非连续存储，会导致CPU 缓存命中率低，查询性能远低于 ArrayList。
• 额外内存开销：每个节点存储 next 和 prev 指针，占用额外 16 字节（64 位 JVM）。
• 不适合大规模数据：大量小对象分散在堆中，容易增加 GC 开销。

# 常见错误

1. 误解 Java 数组可以动态增长
   • Java 数组不能动态扩展，必须创建新数组进行扩容。
2. 误认为 LinkedList 适用于所有插入场景
   • LinkedList 在小数据量时性能较差，仅在大量插入、删除时有优势。

# 最佳实践

• 提前预分配空间，避免频繁扩容：

  List<Integer> list = new ArrayList<>(1000);
  

  1
  
• 如果数据增长可预估，使用 ensureCapacity()：

  list.ensureCapacity(5000);
  

  1
  
• 批量插入数据时，尽量避免 LinkedList，优先使用 ArrayList。

# 深入追问

• Vector 为什么是 2 倍扩容，而 ArrayList 是 1.5 倍？
• ensureCapacity() 方法在 JVM 层面如何优化扩容操作？

# 相关面试题

• ArrayList 扩容与 HashMap 扩容有哪些相似和不同之处？
• 为什么 ArrayList 不能像 LinkedList 那样支持动态插入？