b. ArrayList类

更新日期：2020-06-14

1. 概述

ArrayList是一个非常常用的类。我们创建List的时候绝大多数情况下都会创建这个类，与之相对的是LinkedList类，也就是链表。学习它的源代码能够帮我们了解这个类的底层实现，这样在使用的时候就会知其所以然。

2. List的底层实现

如同我们在数据结构课程中学习的那样，ArrayList在底层使用数组来实现，具体来说就是Object[]。这个Object[]能放任何对象进去，包括null。

它的定义如下：

/**
    * 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.
    */
transient Object[] elementData; // non-private to simplify nested class access

ArrayList的所有操作都围绕着这个数组来进行，而数组的一些特性将决定ArrayList的特性。

3. ArrayList的扩容

由于在Java中数组的长度是固定的，一旦创建就不能改变大小。所以ArrayList也有一个容量的说法。当我们往List里面插入新的元素的时候，数组的空间可能会不够用。这个时候就需要扩容。

而ArrayList的扩容操作的开销是很大的。因为数组长度是固定的，要想得到一个长度更长的数组。只能是创建一个新的数组，然后将元数组的内容全部复制到新的数组中。

在JDK中，使用Arrays.copyOf来从元数组复制出一个新的数组出来。扩容函数如下：

/**
    * Increases the capacity to ensure that it can hold at least the
    * number of elements specified by the minimum capacity argument.
    *
    * @param minCapacity the desired minimum capacity
    * @throws OutOfMemoryError if minCapacity is less than zero
    */
private Object[] grow(int minCapacity) {
    return elementData = Arrays.copyOf(elementData,
                                        newCapacity(minCapacity));
}

主动扩容

在通常的使用过程中，我们很少主动去对ArrayList进行扩容。此时，如果空间不够，会自动扩容。而自动扩容每次将扩展1个元素大小的容量。

当我们需要连续插入大量元素的时候，主动扩容的效率是比较低的。因为每插入一个元素，就需要扩一次容量，就要把数组中的内容全部复制一遍。

如果我们已经知道了自己将插入大量的元素。并且也知道这个数组通常情况下会存储多少个元素。那么我们可以指定初始容量或者是在大量插入数据前主动扩容。

压缩容量

既然有扩容，那自然也有压缩容量。如果我们的数组一开始就存有大量元素，然后会有大量的元素被删除。此时如果想节省下数组所占用的空间，就可以主动进行容量的压缩。

默认的压缩将使数组的容量等于当前数组中元素的个数。

容量上限

ArrayList中数组的大小是有限制的。JDK中定义的List的最大大小如下：

/**
 * The maximum size of array to allocate (unless necessary).
 * Some VMs reserve some header words in an array.
 * Attempts to allocate larger arrays may result in
 * OutOfMemoryError: Requested array size exceeds VM limit
 */
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

而这个值具体是多少呢?

2147483647 [0x7fffffff] - 8

更直观一点，就是2^31 - 8。

如果数组每个元素占一个字节，那么这个数组总共将占据2G左右的空间。通常情况下我们创建不了这么大的数组，内存一般都是不够的。

4. 插入与删除数据

数组的元素是严格按照先后位置来排列的，位置即是索引。如果在数组的正中间插入或者删除元素，这个元素之后的所有元素都需要进行一次平移。

我们在数据结构课程中应该已经学过这个知识了，而JDK中也正是这样来实装的。

由于一次平移的开销是很大的，所以ArrayList并不适合在需要大量随机插入和删除元素的场景下使用，而链表型List会是更好的选择。

下面是JDK中向指定位置插入新元素的函数源码，可以看到一次add既要扩容又要平移，相当于要复制两边所有元素，效率可想而知。

/**
    * Inserts the specified element at the specified position in this
    * list. Shifts the element currently at that position (if any) and
    * any subsequent elements to the right (adds one to their indices).
    *
    * @param index index at which the specified element is to be inserted
    * @param element element to be inserted
    * @throws IndexOutOfBoundsException {@inheritDoc}
    */
public void add(int index, E element) {
    rangeCheckForAdd(index);
    modCount++;
    final int s;
    Object[] elementData;
    if ((s = size) == (elementData = this.elementData).length)
        elementData = grow();
    System.arraycopy(elementData, index,
                        elementData, index + 1,
                        s - index);
    elementData[index] = element;
    size = s + 1;
}

5. 随机存取元素

数组有一个能快速随机存取数据的特性，ArrayList便同样具有这样的特性。

在ArrayList中提供了get和set函数可以读取或者替换指定位置的元素。这个操作的开销非常小，这个读和写几乎等同于如下操作：

rst = array[index]
array[index] = "xxxx"

这个特性正是ArrayList最大的优点。

6. 其它功能

作为了解，我注意到了，JDK还为ArrayList实现了如下功能。

转成数组
取得子List的视图（类似于数组库中的视图概念）
按条件删除元素
数组的相等比较（类似String的equals函数）
计算哈希值（将使用每个元素的哈希值来计算）
排序
对Stream的支持