ArrayList源码阅读

发表于 更新于 分类于

成员变量和静态常量

不考虑从AbstractList中继承成的modCount之类的字段,ArrayList具有以下成员变量:

字段名 类型 说明
elementData Object[] 存储元素的数组缓冲区
size int 当前元素数量

包含静态常量的完整定义如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

@java.io.Serial
  private static final long serialVersionUID = 8683452581122892189L;

  /**
   * Default initial capacity.
   * 默认初始容量。
   */
  private static final int DEFAULT_CAPACITY = 10;

  /**
   * Shared empty array instance used for empty instances.
   */
  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 区分开来，以便在添加第一个元素时知道应该扩容多少。
   */
  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.
   * ArrayList用于存储元素的数组缓冲区。ArrayList的容量即为该数组的长度。
   * 任何elementData为DEFAULTCAPACITY_EMPTY_ELEMENTDATA的空ArrayList，
   * 在添加第一个元素时会扩容到DEFAULT_CAPACITY。
   */
  transient Object[] elementData; // non-private to simplify nested class access

  /**
   * The size of the ArrayList (the number of elements it contains).
   * ArrayList的实际元素个数。
   *
   * @serial
   */
  private int size;

serialVersionUID，DEFAULT_CAPACITY，elementData，size这四个属性整体中规中矩，一看就知道什么意思。
具有迷惑性的还是如何区分EMPTY_ELEMENTDATA```和```DEFAULTCAPACITY_EMPTY_ELEMENTDATA。
简单来说，就是 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 和 EMPTY_ELEMENTDATA 虽然都是空数组，但用途不同。
前者用于默认构造的 ArrayList，更多的是标识此List是通过无参构造器构造的；后者用于容量为0的特殊情况。

构造器

ArrayList有三个构造器

传入一个初始容量的构造器

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
 * Constructs an empty list with the specified initial capacity.
 *
 * @param  initialCapacity  the initial capacity of the list
 * @throws IllegalArgumentException if the specified initial capacity
 *         is negative
 */
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);
    }
}

代码整体比较简单，就三种情况。传入一个初始容量:

  • 如果大于0就创建一个指定大小的数组
  • 如果等于0就使用共享的表示空List的变量EMPTY_ELEMENTDATA
  • 如果小于0就抛出异常,因为数组的索引不能为零。

此时，ArrayList的初始size已经变为了对应传入大小。注意与下文无参构造器的对比。

无参构造器

1
2
3
4
5
6
/**
 * Constructs an empty list with an initial capacity of ten.
 */
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

无参构造器就是简单的讲数组元素赋值为默认的表示无参构造器构造的DEFAULTCAPACITY_EMPTY_ELEMENTDATA。
注意，尽管源码上的注释都写着初始化一个初始容量为10的空数组，但其实此时ArrayList的size为0，
目的是为了保持延迟初始化。只有在添加第一个元素时才会扩容到默认的容量10。

Collection的构造器

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * Constructs a list containing the elements of the specified
 * collection, in the order they are returned by the collection's
 * iterator.
 *
 * @param c the collection whose elements are to be placed into this list
 * @throws NullPointerException if the specified collection is null
 */
public ArrayList(Collection<? extends E> c) {
    Object[] a = c.toArray();
    if ((size = a.length) != 0) {
        if (c.getClass() == ArrayList.class) {
            elementData = a;
        } else {
            elementData = Arrays.copyOf(a, size, Object[].class);
        }
    } else {
        // replace with empty array.
        elementData = EMPTY_ELEMENTDATA;
    }
}

通过传入的 Collection 创建一个新的 ArrayList，并按集合的迭代器顺序保存元素。
具体步骤很简单:

  1. 首先将集合 c 转为数组 a。
  2. 如果集合不为空,会判断集合的类型，如果本身就是 ArrayList 类型，直接修改引用指向复用其内部数组（提升效率）。
    否则，复制一份新数组，防止外部修改影响内部数据。
    如果集合为空，则使用共享的空数组 EMPTY_ELEMENTDATA。

此时，ArrayList若是不为空，则size已经调整为传入集合的大小。

具体用于复制数组的Arrays类的copyOf源码也很简单:

  • 如果 newLength 大于原数组长度，则新数组多余部分用 null 填充。
  • 如果 newLength 小于原数组长度，则只复制前 newLength 个元素。
  • 新数组的类型由 newType 决定，支持任意数组类型。
  • 对于 Object[] 类型，直接 new；否则用反射创建。
  • 用 System.arraycopy 进行高效复制。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
/**
 * Copies the specified array, truncating or padding with nulls (if necessary)
 * so the copy has the specified length.  For all indices that are
 * valid in both the original array and the copy, the two arrays will
 * contain identical values.  For any indices that are valid in the
 * copy but not the original, the copy will contain {@code null}.
 * Such indices will exist if and only if the specified length
 * is greater than that of the original array.
 * The resulting array is of the class {@code newType}.
 *
 * 复制指定的数组，如有必要会截断或用 null 填充，使复制后的数组具有指定长度。
 * 原数组和新数组中索引都有效的位置，值完全相同。
 * 新数组中多出来的部分（如果有）会用 null 填充。
 * 只有当 newLength 大于原数组长度时才会出现这种情况。
 * 返回的新数组类型为 newType。
 *
 * @param <T> the class of the objects in the returned array
 *            返回数组中对象的类型
 * @param <U> the class of the objects in the original array
 *            原数组中对象的类型
 * @param original the array to be copied
 *                 要复制的原数组
 * @param newLength the length of the copy to be returned
 *                  返回的新数组长度
 * @param newType the class of the copy to be returned
 *                返回的新数组类型
 * @return a copy of the original array, truncated or padded with nulls
 *     to obtain the specified length
 *     复制后的新数组，长度为 newLength
 * @throws NegativeArraySizeException if {@code newLength} is negative
 *         如果 newLength 为负数，抛出异常
 * @throws NullPointerException if {@code original} is null
 *         如果 original 为 null，抛出异常
 * @throws ArrayStoreException if an element copied from
 *     {@code original} is not of a runtime type that can be stored in
 *     an array of class {@code newType}
 *     如果原数组元素类型与新数组类型不兼容，抛出异常
 * @since 1.6
 */
@IntrinsicCandidate
public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
    @SuppressWarnings("unchecked")
    // 判断目标类型是否为 Object[]，是则直接 new，否则用反射创建
    T[] copy = ((Object)newType == (Object)Object[].class)
        ? (T[]) new Object[newLength]
        : (T[]) Array.newInstance(newType.getComponentType(), newLength);
    // 复制原数组内容到新数组，长度为原数组和新数组长度的较小值
    System.arraycopy(original, 0, copy, 0,
                     Math.min(original.length, newLength));
    return copy;
}

公共方法

trimToSize

该方法主要是将内部数组容量缩减为当前元素数量以释放多余内存。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/**
 * Trims the capacity of this {@code ArrayList} instance to be the
 * list's current size.  An application can use this operation to minimize
 * the storage of an {@code ArrayList} instance.
 */
public void trimToSize() {
    modCount++;
    if (size < elementData.length) {
        elementData = (size == 0)
          ? EMPTY_ELEMENTDATA
          : Arrays.copyOf(elementData, size);
    }
}

  1. 首先递增来自于父类的 modCount 来标记结构性修改（主要是用于 fail-fast 检测以便尽可能快速地抛出ConcurrentModificationException）。

  2. 仅在当前容量大于实际大小时进行操作:

    • 若 size == 0，把 elementData 指向共享的 EMPTY_ELEMENTDATA 空数组
    • 否则用 Arrays.copyOf 按当前大小复制数组。
      该方法在需要复制时，时间复杂度为 O(n)

    该方法与 ArrayList 的其它方法一致，线程不安全，在并发环境需外部同步，否则可能抛出 ConcurrentModificationException 或产生不确定行为。

ensureCapacity

这个方法主要的作用就是在我们明确知道要添加多少元素时，可以提前扩容以减少多次扩容带来的性能损耗。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
 * Increases the capacity of this {@code ArrayList} instance, if
 * necessary, to ensure that it can hold at least the number of elements
 * specified by the minimum capacity argument.
 *
 * 如有必要，增加此ArrayList实例的容量，以确保它至少能容纳minCapacity指定数量的元素。
 *
 * @param minCapacity the desired minimum capacity
 *                   所需的最小容量
 */
public void ensureCapacity(int minCapacity) {
    if (minCapacity > elementData.length
        && !(elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
             && minCapacity <= DEFAULT_CAPACITY)) {
        modCount++;
        grow(minCapacity);
    }
}

首先递增来自于父类的 modCount 来标记结构性修改。
仅在当前容量大于实际大小时进行操作:
只有当请求容量大于当前数组长度时才会扩容；并且当当前数组是用于默认构造器的DEFAULTCAPACITY_EMPTY_ELEMENTDATA且请求容量不超过默认容量 DEFAULT_CAPACITY 时，（也就是通过无参构造器构造的时候）保持延迟初始化（不提前分配），以便首次添加元素时按默认策略扩容

grow

grow是ArrayList的私有方法，主要用于实际执行扩容逻辑。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
 * Increases the capacity to ensure that it can hold at least the
 * number of elements specified by the minimum capacity argument.
 *
 * 增加容量以确保至少能容纳minCapacity指定数量的元素。
 *
 * @param minCapacity the desired minimum capacity
 *                   所需的最小容量
 * @throws OutOfMemoryError if minCapacity is less than zero
 *                          如果minCapacity小于0会抛出内存溢出错误
 */
private Object[] grow(int minCapacity) {
    // 获取老容量，也就是当前容量
    int oldCapacity = elementData.length;
    // 如果当前容量大于0 或者 元素不是默认构造器的占位符DEFAULTCAPACITY_EMPTY_ELEMENTDATA
    if (oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        int newCapacity = ArraysSupport.newLength(oldCapacity,
                minCapacity - oldCapacity, /* minimum growth 最小增长量 */
                oldCapacity >> 1           /* preferred growth 推荐增长量 */);
        // 复制原数组到新容量
        return elementData = Arrays.copyOf(elementData, newCapacity);
    } else {
        // 如果原数组为空，则分配默认容量或minCapacity中较大的值
        return elementData = new Object[Math.max(DEFAULT_CAPACITY, minCapacity)];
    }
}

这个方法是ArrayList中相当重要的的一个方法，主要是实现了扩容的功能。因此，我们要重点分析一下它的实现。

首先，它是记录了一下当前容量的大小，然后再进行下面的操作。

如果当前容量大于0，或者当前数组不是DEFAULTCAPACITY_EMPTY_ELEMENTDATA，前面说明过，DEFAULTCAPACITY_EMPTY_ELEMENTDATA是一个被final修饰的空数组，在三个构造方法中，只有无参构造方法中elementData被赋予了DEFAULTCAPACITY_EMPTY_ELEMENTDATA。

首先先看else分支，它只会处理的唯一的一种情况——用默认无参构造方法创建的数组的初始扩容情况
此时的容量为0，添加一个元素时会创建一个新的数组，其大小为max(DEFAULT_CAPACITY, minCapacity)。
从上面的源码变量信息中可得知DEFAULT_CAPACITY是一个常量，其值为10，而minCapacity的值为（0+1） 。
所以添加一个元素时，max(DEFAULT_CAPACITY, minCapacity)的值必为10。也就是说，当我们用默认无参构造方法创建的数组在添加元素前，ArrayList的容量为0，添加一个元素后，ArrayList的容量就变为10了。

看完了else，我们在看看if，来看看能处理其余的扩容情况的if语句是怎么做的。

我们来看一下if里面的操作，先创建一个新的数组，然后将旧数组拷贝到新数组并赋给elementData返回。ArraysSupport.newLength函数的作用是创建一个大小为oldCapacity + max（minimum growth， preferred growth）的数组。

minCapacity是传入的参数，我们上面看过，它的值是当前容量（老容量）+1，那么minCapacity - oldCapacity的值就恒为1，minimum growth的值也就恒为1。

oldCapacity >> 1的功能是将oldCapacity 进行位运算，右移一位，也就是减半，preferred growth的值即为oldCapacity大小的一半。

也就是说，在用户没有干预，没有添加大量元素的情况下，自动扩容的规则是:第一次容量增长为10，后续每一次扩容都是当前容量的1.5倍（只是近似，因为右移碰上奇数会舍弃小数部分）

grow扩容的一点题外话

当oldCapacity为0时，右移后还是0，也就是说此时扩容的大小为0+max（1,0）=1，容量从0扩展到1。那么什么时候是这种情况呢？

  1. 用户调用了传容量的构造方法，并且传入的是0，此时elementData被赋予的是EMPTY_ELEMENTDATA，此时数组容量为0，添加元素时，符合if的条件，会进入此扩容情况，容量从0扩展到1。

  2. 传Collection元素列表的构造方法被传入空列表时，elementData被赋予的是EMPTY_ELEMENTDATA，数组容量为0，此时添加元素时，符合if的条件，会进入此扩容情况，容量从0扩展到1。