ArrayList源码分析

参考

ArrayList源码分析

1. 概述

以数组实现，默认容量为10，如果超过则扩容为之前的1.5倍。

• 优势是查询快，因为这是数组的特点；
• 劣势是根据索引index来插入或移除指定的元素比较慢，因为涉及到该元素之后的元素的迁移，导致性能变差。

2. 初始化

无参构造方法默认为一个空数组，并在第一次添加元素时会扩容到长度为10，后详见add方法。

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

在有参构造方法中，可以指定一个initialCapacity容量大小的数组作为初始数组大小。如果知道需要多大容量的集合，最好通过该方法指定容量大小。

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. add(E e) 将元素e添加到集合末尾

在add(E e)方法中，大致的流程为：

调用add()方法添加元素 -> 计算最新的容量来判断是否需要扩容 -> 需要则扩容，不需要则直接添加元素 -> 并发统计数modCount+1 -> 添加元素到数组中，并且size+1。

源码分析如下：

public boolean add(E e) {
    // 确保容量正确的方法
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

可以看到首先会调用ensureCapacityInternal()方法来确保数组容量大小正确，最终会将元素添加至集合的尾部。ensureCapacityInternal()是自动扩容机制的核心，看下它的内部实现：

private void ensureCapacityInternal(int minCapacity) {
    // 首先调用calculateCapacity()方法计算最新需要的容量
    // 然后调用ensureExplicitCapacity()决定是否需要扩容
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
private static int calculateCapacity(Object[] elementData, int minCapacity) {
    // 可以看到，如果调用了无参构造方法来创建ArrayList，第一次添加元素时则默认会指定容量为 DEFAULT_CAPACITY=10
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    // 否则返回当前size+1的容量大小
    return minCapacity;
}
private void ensureExplicitCapacity(int minCapacity) {
    // 并发修改统计变量+1
    // 在使用迭代器遍历元素时，如果modCount不一致，则会引起并发修改异常
    modCount++;
    // overflow-conscious code
    // 如果最新计算的集合size大于当前数组的长度，则调用grow方法进行扩容操作
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

代码走到了这里，可以很清晰地看到整个逻辑过程：

1. 先计算最新的集合size
2. 然后将modCount+1
3. 接下来判断最新的size是否超过了当前数组的大小
   
   • 是则进行扩容
   • 否则回到add()方法中
4. 执行elementData[size++] = e直接将元素添加到数组中

最后看下数组扩容的代码逻辑：

private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    // oldCapacity >> 1 操作即原大小除以2
    // 所以newCapacity = oldCapacity + oldCapacity / 2，即1.5倍
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    // 如果1.5倍不满足，则直接扩容为指定值
    // 只发生在第一次添加元素的时候，此时old为0，new也为0，min为10
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // minCapacity is usually close to size, so this is a win:
    // 最终通过Arrays.copyOf()方法，将之前的数组内容复制到一个容量为newCapacity的新数组中
    elementData = Arrays.copyOf(elementData, newCapacity);
}

在扩容的逻辑中，可以看到扩容大小是之前的1.5倍，这便是ArrayList集合自动扩容的原理。

4. add(int index, E element) 将元素element添加至集合指定索引位置index

原理比较简单，因为扩容原理和add(E e)是相同的。源码如下：

public void add(int index, E element) {
    rangeCheckForAdd(index);
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    System.arraycopy(elementData, index, elementData, index + 1,
                     size - index);
    elementData[index] = element;
    size++;
}
private void rangeCheckForAdd(int index) {
    if (index > size || index < 0)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

首先调用rangeCheckForAdd(int index)检查index是否越界，是则抛出IndexOutOfBoundsException异常。

接下来确认是否需要扩容，代码逻辑同add(E e)，不再重复分析。

然后调用System.arraycopy()方法，将index之后的元素全部复制后移一位，空出index这个位置。

最后调用elementData[index] = element 将元素element添加到数组的index位置。

5. set/get 赋值或访问

set/get方法比较简单，首先对index进行越界判断，然后执行赋值或访问操作：

public E set(int index, E element) {
    rangeCheck(index);
    E oldValue = elementData(index);
    elementData[index] = element;
    return oldValue;
}
public E get(int index) {
    rangeCheck(index);
    return elementData(index);
}
private void rangeCheck(int index) {
    if (index >= size)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

6. remove(int index) 删除集合索引为index的元素

也比较简单，首先对要删除的索引index进行越界判断，将index之后的所有元素赋值往前移动一位，最后将集合末尾的元素指向为null，具体源码分析如下：

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);
    // 因为调用的是arraycopy方法，将index之后的元素全部复制往前移动一位
    // 例如原数组为{1, 2, 3, 4, 5}，删除第二个元素之后，新数组为{1, 3, 4, 5, 5}，所以需要将size-1的数组元素置为null
    elementData[--size] = null; // clear to let GC do its work
    return oldValue;
}

7. remove(Object object) 删除集合中的元素object

这个移除操作有个特点：如果集合中不存在元素object，则原集合不变化，否则只移除集合中第一个值与object相等的元素。例如集合中的元素为["A", "B", "C", "B", "D"]，要移除的元素为"B"，则移除后的集合为["A", "C", "B", "D"]。具体源码如下：

public boolean remove(Object o) {
    // 分为元素为null和不为null两种情况
    if (o == null) {
        for (int index = 0; index < size; index++)
            // 遇到第一个null则返回
            if (elementData[index] == null) {
                fastRemove(index);
                return true;
            }
    } else {
        for (int index = 0; index < size; index++)
            // 遇到第一个值与object相等的元素则返回
            if (o.equals(elementData[index])) {
                fastRemove(index);
                return true;
            }
    }
    return false;
}
/**
 * 该方法和remove(int index) 主要差别是不进行越界判断和无返回值，其余代码逻辑一致
 */
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; // clear to let GC do its work
}