ArrayList源码分析

提示

本文将深入分析Java中ArrayList的实现原理、性能特点及使用场景，帮助你更好地理解和使用这一常用集合类。

1. ArrayList简介

ArrayList是Java集合框架中最常用的集合类之一，它实现了List接口，底层基于数组实现，允许存储任何类型的对象，包括null值。ArrayList具有以下特点：

• 基于动态数组实现，支持随机访问
• 容量可自动增长
• 非线程安全
• 允许存储重复元素和null值

2. 类继承体系

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

从继承关系可以看出：

• ArrayList继承自AbstractList，获得了List接口的默认实现
• 实现了List接口，提供了增删改查等操作
• 实现了RandomAccess接口，表明支持快速随机访问
• 实现了Cloneable接口，可以被克隆
• 实现了Serializable接口，支持序列化

3. 核心属性

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

/**
 * 用于空实例的共享空数组实例
 */
private static final Object[] EMPTY_ELEMENTDATA = {};

/**
 * 用于默认大小的空实例的共享空数组实例
 * 与EMPTY_ELEMENTDATA区分，以便知道添加第一个元素时要膨胀多少
 */
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

/**
 * 存储ArrayList元素的数组缓冲区
 * ArrayList的容量是此数组缓冲区的长度
 * 当添加第一个元素时，任何具有elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA的空ArrayList都将扩展为DEFAULT_CAPACITY
 */
transient Object[] elementData;

/**
 * ArrayList的大小（它包含的元素数量）
 */
private int size;

4. 构造方法

ArrayList提供了三种构造方法：

4.1 指定初始容量构造

/**
 * 构造具有指定初始容量的空列表
 */
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);
    }
}

4.2 默认构造方法

/**
 * 构造一个初始容量为10的空列表
 */
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

4.3 集合参数构造方法

/**
 * 构造一个包含指定集合元素的列表，按照集合的迭代器返回元素的顺序
 */
public ArrayList(Collection<? extends E> c) {
    elementData = c.toArray();
    if ((size = elementData.length) != 0) {
        // c.toArray可能不会返回Object[]，见bug 6260652
        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    } else {
        // 替换为空数组
        this.elementData = EMPTY_ELEMENTDATA;
    }
}

5. 核心方法分析

5.1 添加元素

/**
 * 将指定元素追加到此列表的末尾
 */
public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // 确保容量足够
    elementData[size++] = e;           // 添加元素并增加size
    return true;
}

/**
 * 在指定位置插入元素
 */
public void add(int index, E element) {
    rangeCheckForAdd(index);           // 检查索引是否合法
    
    ensureCapacityInternal(size + 1);  // 确保容量足够
    // 将index及其之后的元素后移一位
    System.arraycopy(elementData, index, elementData, index + 1, size - index);
    elementData[index] = element;      // 在index位置插入元素
    size++;
}

5.2 扩容机制

/**
 * 确保内部容量足够
 */
private void ensureCapacityInternal(int minCapacity) {
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

/**
 * 计算容量
 */
private static int calculateCapacity(Object[] elementData, int minCapacity) {
    // 如果是空数组，返回默认容量和最小容量中的较大值
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    return minCapacity;
}

/**
 * 确保明确容量
 */
private void ensureExplicitCapacity(int minCapacity) {
    modCount++; // 修改计数加1
    
    // 如果最小容量大于数组长度，进行扩容
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

/**
 * 要分配的最大数组大小
 */
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

/**
 * 增加容量，至少确保能容纳minCapacity个元素
 */
private void grow(int minCapacity) {
    // 旧容量
    int oldCapacity = elementData.length;
    // 新容量 = 旧容量的1.5倍
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    // 如果新容量仍小于最小需要容量，则使用最小需要容量
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    // 如果新容量超过最大数组大小，则使用最大容量
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // 复制到新的更大数组
    elementData = Arrays.copyOf(elementData, newCapacity);
}

/**
 * 处理巨大容量
 */
private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) // overflow
        throw new OutOfMemoryError();
    return (minCapacity > MAX_ARRAY_SIZE) ?
        Integer.MAX_VALUE :
        MAX_ARRAY_SIZE;
}

5.3 删除元素

/**
 * 删除指定位置的元素
 */
public E remove(int index) {
    rangeCheck(index); // 检查索引是否合法
    
    modCount++;
    E oldValue = elementData(index); // 获取旧值
    
    int numMoved = size - index - 1;
    if (numMoved > 0)
        // 将index+1及之后的元素前移一位
        System.arraycopy(elementData, index+1, elementData, index, numMoved);
    // 将最后一个元素置为null，帮助GC
    elementData[--size] = null;
    
    return oldValue;
}

/**
 * 删除第一次出现的指定元素
 */
public boolean remove(Object o) {
    if (o == null) {
        // 查找第一个null元素并删除
        for (int index = 0; index < size; index++)
            if (elementData[index] == null) {
                fastRemove(index);
                return true;
            }
    } else {
        // 查找第一个等于o的元素并删除
        for (int index = 0; index < size; index++)
            if (o.equals(elementData[index])) {
                fastRemove(index);
                return true;
            }
    }
    return false;
}

/**
 * 快速删除，跳过边界检查且不返回删除的值
 */
private void fastRemove(int index) {
    modCount++;
    int numMoved = size - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index, numMoved);
    elementData[--size] = null;
}

5.4 查找元素

/**
 * 返回指定位置的元素
 */
public E get(int index) {
    rangeCheck(index); // 检查索引是否合法
    return elementData(index);
}

/**
 * 返回elementData数组中指定位置的元素
 */
@SuppressWarnings("unchecked")
E elementData(int index) {
    return (E) elementData[index];
}

/**
 * 检查给定索引是否在范围内
 */
private void rangeCheck(int index) {
    if (index >= size)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

6. 性能分析

6.1 时间复杂度

• 访问元素: O(1) - 通过索引直接访问
• 添加元素(末尾): 平均 O(1) - 如果需要扩容则为 O(n)
• 添加元素(指定位置): O(n) - 需要移动元素
• 删除元素: O(n) - 需要移动元素
• 查找元素: O(n) - 需要遍历数组

6.2 空间复杂度

ArrayList的空间复杂度为O(n)，其中n为数组的容量。由于扩容机制，实际使用的空间可能大于元素数量。

7. 使用场景与注意事项

7.1 适用场景

• 频繁随机访问元素
• 元素数量变化不大
• 不需要频繁在中间插入或删除元素

7.2 不适用场景

• 频繁在中间插入或删除元素
• 需要线程安全的场景(可使用Vector或Collections.synchronizedList)
• 存储基本类型数据(可考虑使用专门的数组或第三方库如Trove)

7.3 注意事项

• 尽量指定初始容量，避免频繁扩容
• 删除元素时考虑使用迭代器
• 多线程环境下需要外部同步
• 大量删除操作后考虑调用trimToSize()释放多余空间

8. 总结

ArrayList是一个基于动态数组实现的List集合，它提供了快速的随机访问能力，适合需要频繁访问元素的场景。了解其内部实现原理，可以帮助我们更高效地使用这一集合类。

在实际应用中，应根据具体需求选择合适的集合类，对于ArrayList，应尽量避免频繁的中间插入和删除操作，以获得最佳性能。