ArrayList 源码

继承 & 属性

ArrayList不是线程安全的，只能在单线程环境中使用。

/**
 * RandomAccess: 实现该接口的 List 集合是支持快速随机访问
 * Cloneable: 可以被克隆
 * java.io.Serializable: 支持序列化，可以通过序列化传输
 */
public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
        
/**
 * 默认初始容量大小
 */
private static final int DEFAULT_CAPACITY = 10;

/**
 * 空数组（用于初始化空实例）
 */
private static final Object[] EMPTY_ELEMENTDATA = {};

/**
 * 用于默认大小的空实例的共享空数组实例。我们将其与 EMPTY_ELEMENTDATA 区分开来，以了解添加第一个元素时要膨胀多少。
 */
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

/**
 * 保存 ArrayList 数据的数组
 */
transient Object[] elementData;

/**
 * 数组中元素的个数
 */
private int size;

构造方法

指定容量

此方法接受一个初始化容量参数initialCapacity。如果初始化容量为 0，则初始化为一个空的常量数组EMPTY_ELEMENTDATA，小于 0 时则抛出异常。

public ArrayList(int initialCapacity) {
    if (initialCapacity > 0) {
        // initialCapacity > 0，创建对应大小的数组
        this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == 0) {
        // initialCapacity = 0，创建空数组 EMPTY_ELEMENTDATA
        this.elementData = EMPTY_ELEMENTDATA;
    } else {
        // 其他情况抛出异常
        throw new IllegalArgumentException("Illegal Capacity: " + initialCapacity);
    }
}

无参数

不指定初始化大小时，直接使用DEFAULTCAPACITY_EMPTY_ELEMENTDATA，该属性区别于EMPTY_ELEMENTDATA，在添加元素时容量会自动扩张为 10。

public ArrayList() {
    // DEFAULTCAPACITY_EMPTY_ELEMENTDATA 区别于 EMPTY_ELEMENTDATA，
    // 当添加第一个元素时，该数组容量变为 10
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

集合为参数

使用集合为参数时，先将集合转化为数组，然后判断长度和是否为Object数组。

public ArrayList(Collection<? extends E> c) {
    // 将集合转化为数组
    elementData = c.toArray();
    // 如果数组的长度 != 0
    if ((size = elementData.length) != 0) {
        // 如果数组中的元素不是 Object 类型
        if (elementData.getClass() != Object[].class)
            // 将不是原本数组中的内容重新赋值为新的 Object 类型的 elementData 数组
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    } else {
        // 其他情况使用常量空数组代替
        this.elementData = EMPTY_ELEMENTDATA;
    }
}

边界检查

边界检查通常用来判断方法中的给定索引是否超过数组的长度，超过数组边界时抛出边界异常。

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

/**
 * add 和 addAll 使用的 rangeCheck 的一个版本
 */
private void rangeCheckForAdd(int index) {
    if (index > size || index < 0)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

复制元素

ArrayList中的许多方法都需要对当前数组内的元素进行复制，复制的方法主要为System.arraycopy()和Arrays.copyOf()。

arraycopy

arraycopy() 需要目标数组，它将原数组拷贝到自己定义的数组里或者原数组，而且可以选择拷贝的起点和长度以及放入新数组中的位置。

/**
 * 复制数组
 * @param src 源数组
 * @param srcPos 源数组中的起始位置
 * @param dest 目标数组
 * @param destPos 目标数组中的起始位置
 * @param length 要复制的数组元素数量
 */

public static native void arraycopy(Object src, int srcPos,
                                    Object dest, int destPos,
                                    int length)

copyOf

copyOf()内部其实也是调用System.arraycopy()方法实现的。系统自动在内部新建一个数组，并返回复制后的该数组。

public static int[] copyOf(int[] original, int newLength) {
    // 申请一个新的数组
    int[] copy = new int[newLength];
    // 调用 System.arraycopy 将源数组中的数组进行拷贝，然后返回新数组
    System.arraycopy(original, 0, copy, 0,
                     Math.min(original.length, newLength));
    return copy;
}

扩容机制（JDK1.8）

当向数组中添加元素时，数组需要判断自身是否需要扩容。ArrayList的扩容机制可以自动调整数组的大小，在添加元素时自动扩容。

ensureCapacityInternal

ensureCapacityInternal方法是扩容机制开始的起点，该函数随后会调用calculateCapacity和ensureExplicitCapacity两个方法判断数组是否需要扩容及具体的扩容方式。

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

calculateCapacity

calculateCapacity方法主要处理数组是通过空数组构造函数构造的情况，如果elementData不是默认的空数组，则直接返回 minCapacity。

private static int calculateCapacity(Object[] elementData, int minCapacity) {
    // 如果使用默认空数组构造函数，添加元素时判断传入参数和默认容量的较大值
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
    // 当 add 第一个元素时，minCapacity 为 1，比较后 minCapacity 为 10
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
  	return minCapacity;
}

ensureExplicitCapacity

ensureExplicitCapacity主要实现了两个功能：

• 记录当前数组的修改记录。当多线程时，如果有其它线程修改数组，那么就会导致modCount与迭代器初始化时的modCount不同，从而抛出异常。本质上，就是防止一个线程正在迭代遍历，另一个线程修改了这个列表的结构。
• 根据minCapacity和elementData的长度比较判断是否需要对数组进行扩容，如果需要扩容则调用grow方法。

private void ensureExplicitCapacity(int minCapacity) {
    // 记录修改记录，防止一个线程正在迭代遍历，另一个线程在修改列表
    modCount++;
    
    // 添加第一个元素时，minCapacity=10 & elementData.length=0 (empty list)
    if (minCapacity - elementData.length > 0) {
        grow(minCapacity);
    }
}

grow

grow方法是数组扩容的实现方法。它首先计算新数组的容量，公式为newCapacity = oldCapacity + (oldCapacity >> 1)，然后根据不同的情况扩张数组：

• newCapacity < minCapacity：直接将newCapacity大小设置为minCapacity；
• newCapacity > MAX_ARRAY_SIZE：因为公式计算的newCapacity超过了MAX_ARRAY_SIZE，所以需要通过hugeCapacity方法比较minCapacity和MAX_ARRAY_SIZE来决定newCapacity的大小；

/**
 * 数组最大 size
 */
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

private void grow(int minCapacity) {
    int oldCapacity = elementData.length;
    // 位运算速度快于整除，newCapacity 的容量为 oldCapacity 的 1.5 倍左右（奇数去掉小数点，偶数为 1.5 倍）
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    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:
    elementData = Arrays.copyOf(elementData, newCapacity);    
}

hugeCapacity

hugeCapacity方法比较minCapacity和MAX_ARRAY_SIZE之间的大小来决定返回值：

private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0)
        throw new OutOfMemoryError();
    // if minCapacity > MAX_ARRAY_SIZE, newCapacity = Integer.MAX_VALUE
    // if minCapacity < MAX_ARRAY_SIZE, newCapacity = MAX_ARRAY_SIZE
    return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;
}

add

add是ArrayList的核心方法，添加元素的过程中数组需要使用扩容机制去判断是否需要对数组进行扩容。

添加元素到列表末尾

/**
 * 添加元素到列表末尾
 */
public boolean add(E e) {
    // Increments modCount
    ensureCapacityInternal(size + 1);
    // 本质是为数组复制
    elementData[size++] = e;
    return true;
}

将元素添加到指定位置

首先对指定位置的索引进行越界检查，然后判断是否需要扩容，最后将指定位置之后的元素右移一位并将元素添加到指定位置。

public void add(int index, E element) {
    // 越界检查
    rangeCheckForAdd(index);
    
    ensureCapacityInternal(size + 1);
    // 把 index 及之后的元素右一位
    System.arraycopy(elementData, index, elementData, index + 1,
                     size - index);
    // 添加元素到 index
    elementData[index] = element;
    size++;
}

addAll

将集合中的元素全部添加到末尾

首先将Collection对象转化为Object数组，然后根据长度需要进行扩容，最后使用System.arraycopy将元素添加到数组的末尾。

public boolean addAll(Collection<? extends E> c) {
    // 转为 Object 数组
    Object[] a = c.toArray();
    int numNew = a.length;
    // 根据长度进行扩容
    ensureCapacityInternal(size + numNew);
    // 将元素添加到数组末尾
    System.arraycopy(a, 0, elementData, size, numNew);
    size += numNew;
    return numNew != 0;
}

将集合中的元素全部添加到列表指定位置

原理和将元素添加到指定位置类似。

public boolean addAll(int index, Collection<? extends E> c) {
    rangeCheckForAdd(index);
    
    Object[] a = c.toArray();
    int numNew = a.length;
    ensureCapacityInternal(size + numNew);
    
    int numMoved = size - index;
    if (numMoved > 0)
        System.arraycopy(elementData, index, elementData, index + numNew,
                         numMoved);
    
    System.arraycopy(a, 0, elementData, index, numNew);
    size += numNew;
    return numNew != 0;
}

get

先进行边界检查，然后通过下标获取到数组对应的元素。

/**
 * 获取指定位置的元素
 */
public E get(int index) {
    // 边界检查
    rangeCheck(index);
    
    return elementData(index);
}

E elementData(int index) {
    return (E) elementData[index];
}

set

同样首先进行边界判断，然后设置对应下标的元素，并返回被替换的元素。

/**
 * 替换指定位置的元素
 */
public E set(int index, E element) {
    // 边界检查
    rangeCheck(index);
    
    E oldValue = elementData(index);
    elementData[index] = element;
    
    // 返回被替换的元素
    return oldValue;
}

remove

移除指定下标的元素

首先将被删除元素之后的元素全部左移一位，并将size减一。注意这里需要将数组末尾的的元素设置为null从而 GC 可以回收。

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; // clear to let GC do its work
    
    // 返回列表中删除的元素
    return oldValue;
}

移除指定元素

/**
 * 从列表中删除指定元素的第一次出现
 * 如果列表包含该元素，返回 true；否则返回 false
 */
public boolean remove(Object o) {
    // 当被删除元素为 null
    if (o == null) {
        for (int index = 0; index < size; index++) 
            if (elementData[index] == null) {
                fastRemove(index);
                return ture;
            }
    } else {
        // 如果不为空
        for (int index = 0; index < size; index++)
            if (o.equals(elementData[index])) {
                fastRemove(index);
                return ture;
            }
    }
    return false;
}

/**
 * fastRemove 不检查下标，也不返回删除的元素
 */
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
}

IndexOf

第一次出现的位置

/**
 * contains 通过 indexOf 判断元素是否存在
 */
public int indexOf(Object o) {
    if (o == null) {
        for (int i = 0; i < size; i++)
            if (elementData[i]==null) {
                return i;
            }
    } else {
        for (int i = 0; i < size; i++)
            if (o.equals(elementData[i]))
                return i;
    }
    // 元素不存在则返回-1
    return -1;
}

最后一次出现的位置

public int lastIndexOf(Object o) {
    if (o == null) {
        for (int i = size - 1; i >= 0; i--) 
            if (elementData[i]==null)
                return i;
    } else {
        for (int i = size - 1; i >= 0; i--)
            if (o.equals(elementData[i]))
                return i;
    }
    return -1;
}

EnsureCapacity

EnsureCapacity方法本质上通过扩容机制保证数组至少可以容纳当前参数的元素数量。

/**
 * 该方法可以保证 arraylist 至少可以容纳 minCapacity 参数指定的元素数
 *
 * @param minCapacity 所需要的最小容量
 */
public void ensureCapacity(int minCapacity) {
    int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
        // any size if not default element table
        ? 0
        // larger than default for default empty table. It's already
        // supposed to be at default size.
        : DEFAULT_CAPACITY;

    if (minCapacity > minExpand) {
        ensureExplicitCapacity(minCapacity);
    }
}

在add大量元素之前最好使用ensureCapacity，可以减少增量重新分配的次数。对比如下：

public class Test {
    public static void main(String[] args) {
        ArrayList<Object> list = new ArrayList<>();
        final int N = 10000000;
        long startTime = System.currentTimeMillis();
        
        // list.ensureCapacity(N);
        
        for (int i = 0; i < N; i++) {
            list.add(i);
        }
        long endTime = System.currentTimeMillis();
        System.out.println(endTime - startTime);
    }
}

/**
 * 使用 ensureCapacity 前：2434
 * 使用 ensureCapacity 后：1969
 */

参考

1. javaguide-arraylist 简介
2. ArrayList 源码分析