ArrayList介绍

ArrayList内部使用Object[] elementData数组作为数据载体，具有非常好的访问性能，但是随机插入数据的性能不好（涉及到扩容和数组元素移动）。适合用在插入少访问多的环境。

ArrayList的成员变量

成员变量的解释在代码注释中标出，如下所示：

/**
 * Default initial capacity.
 */
// 默认容量为10，如果创建ArrayList时没有指定容量，则使用默认容量
private static final int DEFAULT_CAPACITY = 10;

/**
 * Shared empty array instance used for empty instances.
 */
// 空数组。如果ArrayList内没有元素，使用这个常量作为数据载体。所有无元素的ArrayList共享这个常量
private static final Object[] EMPTY_ELEMENTDATA = {};

/**
 * Shared empty array instance used for default sized empty instances. We
 * distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when
 * first element is added.
 */
// 和EMPTY_ELEMENTDATA类似，在第一个元素加入需要扩容的时候用于计算数组长度，和EMPTY_ELEMENTDATA区分
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

/**
 * The array buffer into which the elements of the ArrayList are stored.
 * The capacity of the ArrayList is the length of this array buffer. Any
 * empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
 * will be expanded to DEFAULT_CAPACITY when the first element is added.
 */
// 数据载体，如果它的值为DEFAULTCAPACITY_EMPTY_ELEMENTDATA，添加第一个元素后会被扩容为DEFAULT_CAPACITY
transient Object[] elementData; // non-private to simplify nested class access

/**
 * The size of the ArrayList (the number of elements it contains).
 *
 * @serial
 */
// ArrayList目前存放的元素数量
private int size;

ArrayList的构造方法

ArrayList有3个构造方法，支持创建时指定初始容量，支持从已知Collection对象创建ArrayList。

// 指定初始容量的构造方法
public ArrayList(int initialCapacity) {
    if (initialCapacity > 0) {
        // 如果初始容量大于0，创建一个容量为初始容量的数组
        this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == 0) {
        // 如果初始容量等于0，使用EMPTY_ELEMENTDATA
        this.elementData = EMPTY_ELEMENTDATA;
    } else {
        throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
    }
}

// 默认无参构造函数，使用默认的容量
public ArrayList() {
    // 使用DEFAULTCAPACITY_EMPTY_ELEMENTDATA
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

// 使用另一个集合创建ArrayList
public ArrayList(Collection<? extends E> c) {
    // 将另一个集合的数据转换为数组
    elementData = c.toArray();
    // 如果数组大小不为0
    if ((size = elementData.length) != 0) {
        // c.toArray might (incorrectly) not return Object[] (see 6260652)
        // (1)
        // 如果elementData不是Object类型数组，需要转换成Object类型数组，防止出现bug
        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    } else {
        // replace with empty array.
        // 初始化为EMPTY_ELEMENTDATA
        this.elementData = EMPTY_ELEMENTDATA;
    }
}

注意：(1)这个地方专门进行了类型检查和转换。英文注释说明了需要进行类型转换的原因：c.toArray()可能返回的不是Object[]类型。

为了证明这个判断的重要性，我们看下Arrays类的asList方法：

public static <T> List<T> asList(T... a) {
    return new ArrayList<>(a);
}

如果你认为这个ArrayList是本篇所说的java.util.ArrayList那就大错特错了。这里返回的ArrayList是Arrays的一个内部类。我们看一下它的部分代码：

private static class ArrayList<E> extends AbstractList<E>
    implements RandomAccess, java.io.Serializable {
    // ...
    private final E[] a;

    ArrayList(E[] array) {
        a = Objects.requireNonNull(array);
    }
    // ...
}

其中a是它的数据载体，是E[]类型而不是Object[]类型。我们再看一下它的toArray()方法：

@Override
public Object[] toArray() {
    return a.clone();
}

返回类型是Object[]，看着像是没什么问题。但是我们如果这么使用Arrays.asList(1, 2, 3).toArray();，实际上返回数组类型不是Object[]而是Integer[]。

下面我们分析下如果没有这个if判断和类型转换会存在什么问题。

我们这么创建ArrayList：

List<Object> list = new ArrayList<>(Arrays.asList(1, 2, 3));
list.add(new Object());

如果没有类型判断和转换，list中的elementData类型实际为Integer[]，在执行第二行add一个Object的时候就会抛出异常。为了避免这个问题存在，ArrayList构造方法中会把任何集合toArray调用返回类型不为Object[]的都转换为Object[]类型数组。

ArrayList的重要方法

add方法

add方法的作用为在数组末端加入一个元素。代码如下：

public boolean add(E e) {
    // 确保数据载体数组的容量超过size + 1，如果不够需要扩容
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    // 下标size的位置防止元素e，然后size自增
    elementData[size++] = e;
    return true;
}

扩容的逻辑位于ensureCapacityInternal方法：

private void ensureCapacityInternal(int minCapacity) {
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

这个方法又调用了ensureExplicitCapacity方法。不过在这个之前我们先分析下calculateCapacity方法。该方法负责计算数组容量。代码如下所示：

private static int calculateCapacity(Object[] elementData, int minCapacity) {
    // 如果ArrayList是未指定初始容量方式初始化，返回初始容量和minCapacity的最大值，否则返回minCapacity
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    return minCapacity;
}

接下来我们分析ensureExplicitCapacity方法：

private void ensureExplicitCapacity(int minCapacity) {
    // 该变量位于AbstractList类中
    // 用于fail-fast，即如果在遍历list的时候修改了数据，会抛出ConcurrentModificationException
    // 每次对集合的修改都会递增这个变量
    modCount++;

    // overflow-conscious code
    // 如果minCapacity大于elementData的长度（即容量），进行扩容操作
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

grow方法负责具体的扩容逻辑，代码如下所示：

private void grow(int minCapacity) {
    // overflow-conscious code
    // 获取原先的容量
    int oldCapacity = elementData.length;
    // 计算扩容后的新容量，新容量为原先容量的1.5倍
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    // 如果新容量比minCapacity小，直接扩容到minCapacity
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    // 如果新容量比MAX_ARRAY_SIZE(Integer.MAX_VALUE - 8)还大，使用hugeCapacity计算新容量
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // minCapacity is usually close to size, so this is a win:
    // 复制elementData内容到新数组，容量为newCapacity，赋值给elementData
    elementData = Arrays.copyOf(elementData, newCapacity);
}

最后是hugeCapacity方法：

private static int hugeCapacity(int minCapacity) {
    // 如果minCapacity小于0，说明发成溢出，抛出OutOfMemoryError
    if (minCapacity < 0) // overflow
        throw new OutOfMemoryError();
    return (minCapacity > MAX_ARRAY_SIZE) ?
        Integer.MAX_VALUE :
        MAX_ARRAY_SIZE;
}

add(int index, E element)方法

该方法在指定index插入元素。

public void add(int index, E element) {
    // 检查index是否越界，后面分析
    rangeCheckForAdd(index);

    // 数组扩容
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    // index及其后面的元素依次向后挪动
    System.arraycopy(elementData, index, elementData, index + 1,
                     size - index);
    // index位置存放element
    elementData[index] = element;
    // size自增
    size++;
}

检查index是否越界的逻辑位于rangeCheckForAdd方法：

private void rangeCheckForAdd(int index) {
    // 如果index超过size或者index为负，抛出异常
    if (index > size || index < 0)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

addAll(Collection<? extends E> c)方法

作用为将c的所有元素追加到ArrayList中。

public boolean addAll(Collection<? extends E> c) {
    Object[] a = c.toArray();
    int numNew = a.length;
    ensureCapacityInternal(size + numNew);  // Increments modCount
    // 将c的元素追加到elementData中
    System.arraycopy(a, 0, elementData, size, numNew);
    size += numNew;
    return numNew != 0;
}

addAll(int index, Collection<? extends E> c)

作用为将c的所有元素插入到ArrayList的index位置。

public boolean addAll(int index, Collection<? extends E> c) {
    rangeCheckForAdd(index);

    Object[] a = c.toArray();
    int numNew = a.length;
    ensureCapacityInternal(size + numNew);  // Increments modCount

    // 计算需要移动的距离
    int numMoved = size - index;
    elementData index位置之后的元素依次向后移动numMoved个位置
    if (numMoved > 0)
        System.arraycopy(elementData, index, elementData, index + numNew,
                         numMoved);

    // 插入a到elementData的index位置
    System.arraycopy(a, 0, elementData, index, numNew);
    size += numNew;
    return numNew != 0;
}

remove(int index)方法

删除指定index的元素。

public E remove(int index) {
    // 检查确保index必须小于size
    rangeCheck(index);

    // 确保fail-fast
    modCount++;
    // 取出需要移除的element，赋给oldValue
    E oldValue = elementData(index);

    // 计算需要有多少个元素需要移动，即被删除的元素后面还有多少个元素
    int numMoved = size - index - 1;
    // elementData之后的元素依次向前移动
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    index为size地方的元素设置为null，便于GC回收。然后size减1
    elementData[--size] = null; // clear to let GC do its work

    // 返回被移除的元素
    return oldValue;
}

remove(Object o)

从ArrayList中移除o对象。如果成功移除返回true，否则返回false。

public boolean remove(Object o) {
    if (o == null) {
        // 如果o是null，遍历查找第一个为null的元素，调用fastRemove移除，返回true
        for (int index = 0; index < size; index++)
            if (elementData[index] == null) {
                fastRemove(index);
                return true;
            }
    } else {
        // 如果o不为null，遍历找到第一个相同的元素，调用fastRemove移除，返回true
        for (int index = 0; index < size; index++)
            if (o.equals(elementData[index])) {
                fastRemove(index);
                return true;
            }
    }
    // 如果没有移除任何元素，返回false
    return false;
}

真正删除元素的逻辑位于fastRemove，逻辑如下所示：

private void fastRemove(int index) {
    // fail-fast
    modCount++;
    // 和remove(int index)方法逻辑相同，不再赘述
    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
}