ArrayList 源码分析

ArrayList 源码分析

1. ArrayList 概述

ArrayList 是 Java 集合框架中实现 List 接口的动态数组类。它的特点是：

• 内部使用动态数组 elementData 存储元素。
• 提供了按索引快速访问的能力。
• 支持动态扩容，自动管理数组大小。

ArrayList 适合读多写少的场景，尤其是需要随机访问的情况。

---

2. ArrayList 类的声明

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable

特点分析

• AbstractList<E>: 提供了 List 接口的一些基础实现。
• List<E>: 定义了集合的基本操作，如增删改查。
• RandomAccess: 标识支持快速随机访问。
• Cloneable: 支持浅拷贝。
• Serializable: 支持序列化。

---

3. 关键成员变量

ArrayList 中的重要字段如下：

// 存储元素的数组，transient 修饰不直接序列化
transient Object[] elementData;

// 当前 ArrayList 中的元素个数
private int size;

// 默认初始容量
private static final int DEFAULT_CAPACITY = 10;

// 空数组（无初始容量的构造方法使用）
private static final Object[] EMPTY_ELEMENTDATA = {};

// 空数组（默认容量的延迟加载）
private static final Object[] DEFAULT_CAPACITY_EMPTY_ELEMENTDATA = {};

解释

• elementData 是核心存储结构，存储所有元素。
• size 记录当前元素的数量，而不是数组的容量。
• 默认初始化容量为 10，但实际分配是在添加第一个元素时完成。

---

4. 构造方法

(1) 无参构造方法

public ArrayList() {
    this.elementData = DEFAULT_CAPACITY_EMPTY_ELEMENTDATA;
}

默认创建一个空数组，但不会立即分配容量，直到第一次添加元素时分配容量。

(2) 指定初始容量的构造方法

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: " + initialCapacity);
    }
}

当传入容量为正数时，直接初始化指定容量的数组；若为 0 则使用 EMPTY_ELEMENTDATA。

(3) 通过集合初始化

public ArrayList(Collection<? extends E> c) {
    elementData = c.toArray();
    if ((size = elementData.length) != 0) {
        if (elementData.getClass() != Object[].class) {
            elementData = Arrays.copyOf(elementData, size, Object[].class);
        }
    } else {
        this.elementData = EMPTY_ELEMENTDATA;
    }
}

• 将传入集合转为数组存储。
• 如果集合为空，使用 EMPTY_ELEMENTDATA。

---

5. add(E e) 方法

源码

public boolean add(E e) {
    ensureCapacityInternal(size + 1); // 确保数组容量
    elementData[size++] = e;         // 添加元素
    return true;
}

核心分析

1. ensureCapacityInternal()：
   确保数组容量足够，不够时会触发扩容。
2. 添加元素到数组中，更新 size。

---

6. 扩容机制

(1) ensureCapacityInternal(int minCapacity)

private void ensureCapacityInternal(int minCapacity) {
    if (elementData == DEFAULT_CAPACITY_EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    ensureExplicitCapacity(minCapacity);
}

• 如果是延迟加载的默认空数组，则初始化为默认容量。

(2) ensureExplicitCapacity(int minCapacity)

private void ensureExplicitCapacity(int minCapacity) {
    modCount++;
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

• modCount++：记录修改次数，防止并发操作问题。
• 若需要的最小容量超过当前数组容量，则调用 grow() 扩容。

(3) grow(int minCapacity)

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)
        newCapacity = hugeCapacity(minCapacity);
    elementData = Arrays.copyOf(elementData, newCapacity);
}

• 扩容规则：当前容量的 1.5 倍，若仍不满足需求，则直接使用最小容量。
• 上限检查：若超过 MAX_ARRAY_SIZE（Integer.MAX_VALUE - 8），调用 hugeCapacity 处理。

---

7. get(int index) 方法

源码

public E get(int index) {
    rangeCheck(index);                // 检查索引合法性
    return (E) elementData[index];    // 返回对应索引的元素
}

核心分析

• rangeCheck(index)：

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

  检查索引是否在合法范围 [0, size) 内。

---

8. remove(int index) 方法

源码

public E remove(int index) {
    rangeCheck(index); // 检查索引合法性

    modCount++;
    E oldValue = (E) elementData[index];

    int numMoved = size - index - 1;  // 移动的元素个数
    if (numMoved > 0)
        System.arraycopy(elementData, index + 1, elementData, index, numMoved);
    elementData[--size] = null;       // 清空最后一个元素
    return oldValue;
}

核心分析

1. 检查索引：确保索引合法。
2. 移动数组：通过 System.arraycopy() 将删除位置后的元素向前移动。
3. 清理引用：防止内存泄漏。

---

9. 其他常用方法

(1) size()

public int size() {
    return size;
}

返回当前元素的个数。

(2) clear()

public void clear() {
    modCount++;
    for (int i = 0; i < size; i++)
        elementData[i] = null; // 清空所有元素
    size = 0;
}

---

10. ArrayList 的优缺点

优点

1. 随机访问效率高，时间复杂度为 O(1)。
2. 提供动态扩容，使用灵活。
3. 内部实现简单，操作方便。

缺点

1. 插入和删除效率低，尤其是中间位置，时间复杂度为 O(n)。
2. 扩容时性能开销大，需要复制数组。
3. 线程不安全，需要手动同步或使用 CopyOnWriteArrayList。

---

11. 总结

ArrayList 是一种基于动态数组的集合，具有高效的随机访问能力和自动扩容机制。其内部实现通过一系列优化方法（如扩容策略、数组拷贝等）平衡了性能和易用性，在实际开发中应用广泛。