Java：ArrayList源码解析

Java：ArrayList源码解析

导言

我们都知道ArrayList是一个可以实现自动扩容的List类，为了理解ArrayList是如何进行扩容的，我们就有必要对ArrayList的源码进行分析。本文中将着重研究源码中ArrayList是如何实现自动扩容的。

源码解析

ArrayList的初始化

我们从构造函数入手，ArrayList有三种构造函数：

• ArrayList(int initialCapacity):指定初始容量
• ArrayList():默认的构造函数
• ArrayList(Collection c):指定初始的数据集

可以看到第一个构造函数指定的是ArrayList的初始容量，我们来看看这个方法：

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);
    }
}
1
2
3
4
5
6
7
8
9
10

这里就涉及到了ArrayList中的几个成员变量：

• transient Object[] elementData:实际上存储元素的容器，ArrayList的容量就是这个数组缓冲区的容量。
• private static final Object[] EMPTY_ELEMENTDATA = {}:当容量指定为0时，ArrayList将直接用这个数组来充当存储数据的容器。
• private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}:当初始化时什么都没有指定时，ArrayList将直接使用这个数据充当存储数据的容器。

除此之外，其实这个方法也没有什么特殊之处，只是根据指定容量是否为零确定了存储元素的容器，可以看到是使用的Object数组。

接着我们来看第二个构造方法：

public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
1
2
3

这个方法更简单，当我们什么都没有指定时就会确定存储元素的数据为DEFAULTCAPACITY_EMPTY_ELEMENTDATA，这个我们在前面已经介绍过了。

第三个构造方法：

public ArrayList(Collection<? extends E> c) {
    elementData = c.toArray();
    if ((size = elementData.length) != 0) {
        // c.toArray might (incorrectly) not return Object[] (see 6260652)
        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    } else {
        // replace with empty array.
        this.elementData = EMPTY_ELEMENTDATA;
    }
}
1
2
3
4
5
6
7
8
9
10
11

这个构造方法接受一个集合，并会将其作为ArrayList的初始元素。可以看到默认情况下是直接将传入的集合转化为数组后赋值给elementData，也就是将其作为存储元素的容器。如果初始数据长度不为0的话还会对转化而来的数组进行一次额外的检查（防止返回的不是Object类型的数组）。初始数据长度为0则和第一个构造方法传入0值一样处理。

向ArrayList中添加元素

我们向ArrayList添加元素当然是调用add方法，所以接下来看add方法：

public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}
1
2
3
4
5

首先会调用ensureCapacityInternal方法，看名字也可以知道这个方法是用来对ArrayList的数据容器进行扩容的，会确保有足够的空间存储加入的元素。之后将这个元素存储到数据存储区elementData中，如果添加成功就会返回true。

ArrayList的扩容

上面说到会调用ensureCapacityInternal方法来进行扩容，所以接下来看这个方法的逻辑：

private void ensureCapacityInternal(int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }

    ensureExplicitCapacity(minCapacity);
}
1
2
3
4
5
6
7

首先会确认之前的数据存储区是否为DEFAULTCAPACITY_EMPTY_ELEMENTDATA,还记得它吗，如果调用不带任何参数的构造函数的话elementData数据存储区就会指向DEFAULTCAPACITY_EMPTY_ELEMENTDATA。也就是说如果在本次添加以前该ArrayList中没有存储任何数据的话就会进入第一个if块中，然后会比较出最小的容量将其赋值给minCapacity，主要是比较传入的容量值和DEFAULT_CAPACITY这两个常量的大小，并选出较小值。这个DEFAULT_CAPACITY的值是10：

这个确定出来的minCapacity是用来传导到接下来的方法中继续进行扩容过程的。这也就是我们经常会听到的ArrayList的最小初始容量的说法来源，因为默认情况下最小扩容量肯定是比这个DEFAULT_CAPACITY，也就是10大的。确定完minCapacity的值之后继续将其传递给下面的方法接着进行扩容：

private void ensureExplicitCapacity(int minCapacity) {
    modCount++;

    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}
1
2
3
4
5
6
7

这里出现了一个新的成员变量modCount,这个变量是用来记录ArrayList的结构性修改的次数的，结构修改是那些改变列表大小或以某种方式干扰列表的操作，以至于正在进行的迭代可能产生不正确的结果。具体来说，迭代器和列表迭代器的实现（通过iterator和listIterator方法返回）使用了这个字段。如果该字段的值意外更改，迭代器（或列表迭代器）将在响应next、remove、previous、set或add等操作时抛出ConcurrentModificationException异常。这提供了"快速失败"（fail-fast）的行为，而不是在迭代过程中出现并发修改时出现不确定性行为。

总的来说这个modCount的主要目的是为了保证在迭代期间检测到并发修改，从而确保迭代器的安全性。

在这个方法中首先对该字段进行自增，然后会判断需要的最小容量和当前数据存储区的容量，如果当前数据存储区的容量不足的话调用grow方法继续进行扩容：

private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    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);
}
1
2
3
4
5
6
7
8
9
10
11

其实还是挺简单的：

• 首先，它获取当前 ArrayList 的容量，即 elementData.length。
• 然后，它计算新容量 newCapacity，通常是旧容量的 1.5 倍（oldCapacity + (oldCapacity >> 1)），这是一种常见的扩容策略，旨在在不过度浪费内存的情况下提供足够的空间。
• 接下来，它检查新容量是否仍然小于 minCapacity，如果是，则将新容量设置为 minCapacity，以确保容量足够。
• 最后，它检查新容量是否超过了 ArrayList 可以容纳的最大数组大小（MAX_ARRAY_SIZE），如果超过了，则调用 hugeCapacity 方法来计算一个合适的容量。
• 最终，它使用 Arrays.copyOf 方法将 elementData 数组的大小扩展为新容量，并将新数组赋给 elementData，从而完成了扩容操作。

访问ArrayList的元素

这里访问ArrayList有多种方法，首先就是直接调用get方法：

public E get(int index) {
    if (index >= size)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

    return (E) elementData[index];
}
1
2
3
4
5
6

这个很简单，没什么好说的。接下来看用迭代器访问的方式。我们要使用迭代器的话首先就需要获取迭代器：

public Iterator<E> iterator() {
    return new Itr();
}
1
2
3

可以看到默认返回的是Itr类，Itr类是ArrayList里的内部类，迭代器里重要的一点就是保证安全，也就是我们之前提到过的modCount参数有关的。来看一部分：

private class Itr implements Iterator<E> {
    // Android-changed: Add "limit" field to detect end of iteration.
    // The "limit" of this iterator. This is the size of the list at the time the
    // iterator was created. Adding & removing elements will invalidate the iteration
    // anyway (and cause next() to throw) so saving this value will guarantee that the
    // value of hasNext() remains stable and won't flap between true and false when elements
    // are added and removed from the list.
    protected int limit = ArrayList.this.size;

    int cursor;       // index of next element to return
    int lastRet = -1; // index of last element returned; -1 if no such
    int expectedModCount = modCount;

    public boolean hasNext() {
        return cursor < limit;
    }

    @SuppressWarnings("unchecked")
    public E next() {
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
        int i = cursor;
        if (i >= limit)
            throw new NoSuchElementException();
        Object[] elementData = ArrayList.this.elementData;
        if (i >= elementData.length)
            throw new ConcurrentModificationException();
        cursor = i + 1;
        return (E) elementData[lastRet = i];
    }

    public void remove() {
        if (lastRet < 0)
            throw new IllegalStateException();
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();

        try {
            ArrayList.this.remove(lastRet);
            cursor = lastRet;
            lastRet = -1;
            expectedModCount = modCount;
            limit--;
        } catch (IndexOutOfBoundsException ex) {
            throw new ConcurrentModificationException();
        }
    }

    @Override
    @SuppressWarnings("unchecked")
    public void forEachRemaining(Consumer<? super E> consumer) {
        Objects.requireNonNull(consumer);
        final int size = ArrayList.this.size;
        int i = cursor;
        if (i >= size) {
            return;
        }
        final Object[] elementData = ArrayList.this.elementData;
        if (i >= elementData.length) {
            throw new ConcurrentModificationException();
        }
        while (i != size && modCount == expectedModCount) {
            consumer.accept((E) elementData[i++]);
        }
        // update once at end of iteration to reduce heap write traffic
        cursor = i;
        lastRet = i - 1;

        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
    }
}
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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72

可以看到就将之前的modCount赋值给了expectedModCount，在之后的next方法和remove方法中，一旦modCount和expectedModCount不匹配就会抛出异常，说明该ArrayList已经被并发修改过了，并不安全可靠了。

总结

最后让我们总结一下ArrayList，首先它是一个可以实现自动扩容的容器。它的默认最小容量为10，每当当前容量已经无法容纳下新加入的元素时就会进行扩容。关于扩容，ArrayList会在修改数据存储区之前自增modCount的值，这个值是为了判断线程安全，实现Fast-Fail用的。

最后附上一张流程图：