# 问题

1. ArrayList 的底层数据结构是什么?默认容量是多少?

# 标准答案

ArrayList 底层基于 动态数组(dynamic array) 实现,使用 Object[] 数组存储元素。默认情况下,JDK 1.8 及以后版本的 ArrayList 初始容量为 0,只有在第一次 add() 操作时才会扩容到 10(即 DEFAULT_CAPACITY = 10)。

# 答案解析

# 1. 底层数据结构

ArrayList 的底层数据结构是 动态数组,它与 LinkedList 的链表结构不同,依赖 连续的内存空间 存储数据。

  • 首次创建 ArrayList

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

    ArrayList 初始时 elementData 数组为 空数组,不会立即分配内存。

  • 第一次 add() 时触发初始化

    list.add(1);
    
    1

    ArrayList 扩容到 DEFAULT_CAPACITY = 10,实际存储数组 elementData 长度变为 10。

# 2. 默认容量(JDK 1.8+)

private static final int DEFAULT_CAPACITY = 10;
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
1
2
  • JDK 1.7 及以前:默认初始容量 10,直接分配 Object[10]
  • JDK 1.8 及以后:初始时 elementData 为空数组,只有在第一次 add() 时才扩容至 10,减少不必要的内存占用。

# 3. 扩容机制

ArrayList 需要存储的元素超出当前数组容量时,会触发 扩容,扩容规则如下:

int newCapacity = oldCapacity + (oldCapacity >> 1); // 1.5 倍扩容
1

例如:

  • 容量 10 扩容到 15
  • 容量 15 扩容到 22
  • 容量 22 扩容到 33

扩容过程:

  1. 创建一个 更大的数组
  2. 复制原数组的数据到新数组
  3. 丢弃旧数组,使用新数组

扩容涉及 数组拷贝System.arraycopy()),可能影响性能,因此建议在大量插入数据时 预分配足够的容量 以减少扩容次数:

List<Integer> list = new ArrayList<>(1000); // 预分配 1000 容量,避免频繁扩容
1

# 4. ArrayList 与 LinkedList 的对比

特性 ArrayList LinkedList
底层结构 动态数组 (Object[]) 双向链表 (Node)
访问速度 O(1) 随机访问快 O(n) 随机访问慢
插入删除 O(n) 移动数据,性能低 O(1) 修改指针,性能高
内存占用 较低,仅存储数据 较高,额外存储指针
适用场景 读多写少(如缓存) 写多读少(如队列)

# 深入追问

  1. 为什么 JDK 1.8 之后 ArrayList 初始容量变为 0,而不是直接 10?

    • 这样可以减少内存占用,只有在 add() 时才分配数组,适用于未必需要添加数据的情况。
  2. 扩容 1.5 倍的依据是什么?为什么不是 2 倍?

    • 1.5 倍是时间复杂度与空间利用率的折中。
    • 2 倍扩容会增加内存占用,而 1.5 倍减少了碎片化的浪费,避免 GC 压力。
  3. 如何减少 ArrayList 的扩容影响?

    • 预分配容量 new ArrayList<>(expectedSize)
    • 使用 ensureCapacity(int minCapacity) 主动扩容。

# 相关面试题

  • ArrayListLinkedList 的区别是什么?
  • 为什么 ArrayList 的扩容不是按固定大小增加?
  • 如何优化 ArrayList 的性能,减少扩容开销?