Java中ArrayList底层扩容原理以及扩容操作的示例分析

发布时间：2022-02-28 10:55:39 作者：小新
来源：亿速云阅读：218

# Java中ArrayList底层扩容原理以及扩容操作的示例分析

## 1. ArrayList概述

### 1.1 ArrayList简介
ArrayList是Java集合框架中最常用的动态数组实现，位于`java.util`包中。它基于数组实现，能够动态地增长和缩减容量，提供了快速随机访问的能力。

与普通数组相比，ArrayList具有以下优势：
- 自动扩容：无需手动处理数组扩容
- 丰富API：提供丰富的操作方法（add/remove/get等）
- 类型安全：通过泛型保证类型安全

### 1.2 核心特性
- **动态扩容**：当元素数量超过当前容量时自动扩容
- **非线程安全**：不适合多线程环境（可使用Vector或Collections.synchronizedList）
- **快速随机访问**：通过索引访问元素时间复杂度为O(1)
- **有序集合**：保持元素插入顺序

```java
// 基本使用示例
List<String> list = new ArrayList<>();
list.add("Java");
list.add("Python");
String item = list.get(0);  // 随机访问

2. 底层数据结构

2.1 核心成员变量

// JDK 1.8源码片段
transient Object[] elementData; // 实际存储元素的数组
private int size;              // 当前元素数量
private static final int DEFAULT_CAPACITY = 10; // 默认初始容量

2.2 数组与ArrayList的关系

ArrayList本质上是对Object数组的封装，所有操作都基于这个数组： - 添加元素：向数组尾部插入 - 删除元素：需要移动后续元素 - 扩容操作：创建新数组并拷贝数据

// 构造方法源码分析
public ArrayList(int initialCapacity) {
    if (initialCapacity > 0) {
        this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == 0) {
        this.elementData = EMPTY_ELEMENTDATA;
    } else {
        throw new IllegalArgumentException("Illegal Capacity");
    }
}

3. 扩容机制详解

3.1 触发扩容的条件

当执行add操作时，会先检查容量：

public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // 关键扩容检查
    elementData[size++] = e;
    return true;
}

3.2 扩容核心流程

容量检查：ensureCapacityInternal()
计算新容量：grow()
数组拷贝：Arrays.copyOf()

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

3.3 扩容因子分析

默认扩容倍数：1.5倍（oldCapacity + oldCapacity >> 1）
特殊场景：
- 首次扩容：直接跳转到DEFAULT_CAPACITY(10)
- 超大容量：检查MAX_ARRAY_SIZE(Integer.MAX_VALUE - 8)

4. 扩容性能分析

4.1 时间复杂度对比

操作	平均时间复杂度	最坏情况
add()	O(1)	O(n)
add(index)	O(n)	O(n)
get()	O(1)	O(1)

4.2 空间复杂度

每次扩容需要额外空间： - 临时新数组占用内存 - 旧数组等待GC回收

4.3 优化建议

预分配容量：已知大小时使用ArrayList(int initialCapacity)
批量操作：使用addAll()减少多次扩容
避免频繁修改：考虑使用LinkedList

5. 实战示例分析

5.1 基础扩容演示

public class ExpansionDemo {
    public static void main(String[] args) {
        ArrayList<Integer> list = new ArrayList<>();
        
        // 打印扩容过程
        for (int i = 0; i < 100; i++) {
            System.out.printf("Size: %2d, Capacity: %2d%n", 
                list.size(), getCapacity(list));
            list.add(i);
        }
    }
    
    // 反射获取实际容量
    static int getCapacity(ArrayList<?> list) {
        try {
            Field field = ArrayList.class.getDeclaredField("elementData");
            field.setAccessible(true);
            return ((Object[]) field.get(list)).length;
        } catch (Exception e) {
            return -1;
        }
    }
}

输出结果示例：

Size:  0, Capacity:  0  // 初始空数组
Size:  1, Capacity: 10  // 首次插入扩容到10
...
Size: 10, Capacity: 10  
Size: 11, Capacity: 15  // 第一次1.5倍扩容
...
Size: 15, Capacity: 15
Size: 16, Capacity: 22  // 第二次扩容

5.2 指定初始容量对比

// 测试不同初始容量的性能差异
public static void testPerformance() {
    final int COUNT = 1000000;
    
    // 无初始容量
    long start1 = System.nanoTime();
    List<Integer> list1 = new ArrayList<>();
    for (int i = 0; i < COUNT; i++) {
        list1.add(i);
    }
    long time1 = System.nanoTime() - start1;
    
    // 预分配容量
    long start2 = System.nanoTime();
    List<Integer> list2 = new ArrayList<>(COUNT);
    for (int i = 0; i < COUNT; i++) {
        list2.add(i);
    }
    long time2 = System.nanoTime() - start2;
    
    System.out.printf("默认容量耗时：%.2fms%n", time1/1e6);
    System.out.printf("预分配容量耗时：%.2fms%n", time2/1e6);
}

典型输出结果：

默认容量耗时：45.32ms
预分配容量耗时：12.67ms

6. 特殊场景分析

6.1 超大集合处理

当接近Integer.MAX_VALUE时：

// 测试最大容量
try {
    List<Integer> hugeList = new ArrayList<>(Integer.MAX_VALUE);
} catch (OutOfMemoryError e) {
    System.out.println("超出虚拟机内存限制");
}

6.2 并发修改问题

// 并发修改异常示例
List<String> list = new ArrayList<>(Arrays.asList("A","B","C"));
for (String s : list) {
    if ("B".equals(s)) {
        list.remove(s);  // 抛出ConcurrentModificationException
    }
}

解决方案： 1. 使用Iterator的remove方法 2. 使用CopyOnWriteArrayList 3. 加同步锁

7. 与其它集合对比

7.1 ArrayList vs LinkedList

特性	ArrayList	LinkedList
底层结构	动态数组	双向链表
随机访问	O(1)	O(n)
头部插入	O(n)	O(1)
内存占用	更小（连续内存）	更大（节点开销）

7.2 ArrayList vs Vector

主要区别： 1. 线程安全：Vector方法同步 2. 扩容策略：Vector默认2倍扩容 3. 性能：ArrayList更高效

8. 最佳实践建议

初始化优化： “`java // 已知大小的情况 List list = new ArrayList<>(expectedSize);

// 从已有集合创建 List copy = new ArrayList<>(existingCollection);


2. **批量操作**：
   ```java
   // 优于循环add
   list.addAll(Arrays.asList("a", "b", "c"));

内存敏感场景：

// 及时释放未用容量
list.trimToSize();

只读场景：

// 不可变列表
List<String> immutable = Collections.unmodifiableList(list);

9. 总结

ArrayList的扩容机制体现了空间换时间的设计思想： 1. 1.5倍平衡增长：避免频繁扩容又减少空间浪费 2. System.arraycopy优化：native方法实现高效数据迁移 3. fail-fast机制：通过modCount检测并发修改

理解扩容原理有助于： - 合理预估集合大小 - 优化内存使用 - 避免性能瓶颈 - 选择合适的集合类型

附录：相关面试题

ArrayList的默认初始容量是多少？
扩容时新容量是如何计算的？
为什么建议预分配ArrayList容量？
ArrayList的remove(int)和remove(Object)哪个效率更高？
如何实现线程安全的ArrayList？

”`