ArrayList源码深入解析

ArrayList是Java集合框架中的一个重要类，实现了List接口。它基于动态数组实现，提供了自动扩容、快速随机访问等特性。在本文中，我们将更加详细地解析ArrayList的源码，特别关注其扩容机制、迭代器实现和一些关键细节。

1. ArrayList的基本结构

ArrayList基于动态数组实现，它可以根据需要动态调整数组的大小。以下是ArrayList的主要属性：

transient Object[] elementData;  // 存储元素的数组，transient表示该字段不参与序列化
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};  // 空数组，用于初始时的默认值
private static final int DEFAULT_CAPACITY = 10;  // 默认初始容量
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;  // 数组的最大容量
private int size;  // 实际元素个数

2. 构造方法

ArrayList有多个构造方法，其中最常用的是默认构造方法和带初始容量参数的构造方法。

// 无参构造方法，初始容量为0
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

// 带初始容量参数的构造方法
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);
    }
}

3. 添加元素

ArrayList提供了多个添加元素的方法，其中最常用的是add方法。在添加元素时，会先确保数组的容量足够，如果不够则进行扩容。

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

// 确保容量足够，如果不够则进行扩容
private void ensureCapacityInternal(int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }

    ensureExplicitCapacity(minCapacity);
}

// 确保容量足够，如果不够则进行扩容
private void ensureExplicitCapacity(int minCapacity) {
    if (minCapacity - elementData.length > 0) {
        grow(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 > 0) {
        newCapacity = hugeCapacity(minCapacity);
    }

    // 将原数组拷贝到新数组
    elementData = Arrays.copyOf(elementData, newCapacity);
}

4. 获取元素

ArrayList提供了多个方法用于获取元素，其中最常用的是get方法。

// 获取指定索引位置的元素
public E get(int index) {
    rangeCheck(index);  // 检查索引是否越界
    return elementData(index);
}

// 检查索引是否越界
private void rangeCheck(int index) {
    if (index >= size) {
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }
}

// 获取指定索引位置的元素
E elementData(int index) {
    return (E) elementData[index];
}

5. 删除元素

ArrayList提供了多个方法用于删除元素，其中最常用的是remove方法。

// 删除指定索引位置的元素
public E remove(int index) {
    rangeCheck(index);  // 检查索引是否越界

    modCount++;  // 修改次数加一
    E oldValue = elementData(index);

    int numMoved = size - index - 1;
    if (numMoved > 0) {
        // 将删除位置后的元素向前移动
        System.arraycopy(elementData, index + 1, elementData, index, numMoved);
    }
    elementData[--size] = null;  // 将最后一个位置置为null，便于垃圾回收

    return oldValue;
}

6. 扩容机制

ArrayList的扩容机制是其一个重要特点。当添加元素时，如果当前数组容量不足，就需要进行扩容。默认情况下，扩容是将原数组的容量扩容为原来的1.5倍。

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);
}

此处涉及到位运算和阈值的计算，这样的设计能够在大多数情况下，平衡了内存利用率和频繁扩容的次数。同时，通过Arrays.copyOf方法，实现了数组的复制。

7. 迭代器实现

ArrayList提供了一个内部类Itr用于实现迭代器，通过这个迭代器可以在集合上进行遍历。迭代器是通过modCount字段来判断在迭代过程中集合是否发生了结构性改变，如果发生了改变，就抛出ConcurrentModificationException异常。

private class Itr implements Iterator<E> {
    int cursor;       // 下一个元素的索引
    int lastRet = -1;  // 上一个元素的索引
    int expectedModCount = modCount;

    // ... 省略其他方法 ...

    public E next() {
        checkForComodification();
        int i = cursor;
        if (i >= size) {
            throw new NoSuchElementException();
        }
        Object[] elementData = ArrayList.this.elementData;
        if (i >= elementData.length) {
            throw new ConcurrentModificationException();
        }
        cursor = i + 1;
        return (E) elementData[lastRet = i];
    }

    final void checkForComodification() {
        if (modCount != expectedModCount) {
            throw new ConcurrentModificationException();
        }
    }
}

8. toArray方法

ArrayList的toArray方法用于将集合转换为数组。其中的toArray方法有两个重载，分别是无参和带参的，带参的方法可以指定数组类型。在转换时，如果指定的数组大小不足，就会创建一个新的数组。

// 无参的toArray方法
public Object[] toArray() {
    return Arrays.copyOf(elementData, size);
}

// 带参的toArray方法
public <T> T[] toArray(T[] a) {
    if (a.length < size) {
        return (T[]) Arrays.copyOf(elementData, size, a.getClass());
    }
    System.arraycopy(elementData, 0, a, 0, size);
    if (a.length > size) {
        a[size] = null;
    }
    return a;
}

这样的设计能够方便用户进行集合与数组之间的转换。

9. 删除元素的细节

在删除元素时，ArrayList通过System.arraycopy方法，将删除位置后的元素向前移动。这样的设计在删除元素时，只需要移动部分数组，而不是整个数组，提高了删除操作的效率。

public E remove(int index) {
    rangeCheck(index);  // 检查索引是否越界

    modCount++;  // 修改次数加一
    E oldValue = elementData(index);

    int numMoved = size - index - 1;
    if (numMoved > 0) {
        // 将删除位置后的元素向前移动
        System.arraycopy(elementData, index + 1, elementData, index, numMoved);
    }
    elementData[--size] = null;  // 将最后一个位置置为null，便于垃圾回收

    return oldValue;
}

10. 总结

通过深入解析ArrayList的源码，我们不仅了解了其基本结构和关键方法的实现，还熟悉了其特有的扩容机制、迭代器实现以及删除元素的细节。ArrayList作为Java集合框架中常用的类之一，其源码解读不仅有助于理解动态数组的实现，也能提升我们对集合框架的整体认识。