Java集合—ArrayList

1. 原理

我们先看看 ArrayList 的类继承体系。

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{

如图所示，ArrayList 实现了 RandomAccess、Cloneable、Serializable。通过实现的接口，我们可以大致判断出一个类有哪些功能，这也是一种思维方式。

• RandomAccess：支持随机访问
• Cloneable：支持克隆
• Serializable：支持序列化

ArrrayList 底层是数组，所以无论是优点还是缺点，都是源于数组的特点。

数组天然的缺点：

1. 数组的长度固定，当插入数据长度达到数组容量时，需要扩容，而扩容是新建一个数组，将值赋值到新数组中，性能差，所以使用 ArrayList 时不要频繁插入数据
2. 在数组中间插数据时，需要将后面的元素进行移位操作，性能同样差；

额，这样看来，ArrayList 只适合查询，不要进行频繁的插入和删除。

数组天然的优点：

1. 支持随机访问，可以根据角标快速的取出数据，时间复杂度 O(1)
2. 顺序性

备注：有很多文章说数组的查询时间复杂度是 O(1) ，我认为这种说法是不准确的。没有哪一种查找算法的时间复杂度能达到 O(1) 的。可能有人会说了，那 ArrayList 的 get 方法的时间复杂度确实是 O(1) 啊。是的，但是 get 方法的本质并不是查询，而是直接拿数据。就像是在你在人群中，我并不是去通过什么方法去找到你，而是我一眼就认出了你。 而这种实现的本质是数组支持随机访问。

2. 源码分析

2.1 构造函数

构造函数有下面两个：

ArrayList() 、ArrayList(int initialCapacity)

一个是没有指定初始化容量的，一个指定了初始容量，建议使用有初始容量的构造函数。

如果没有初始容量，那么 elementData 的值为空数组，在第一次 add 数据时，会设置初始化容量为 10 ，如果你要添加的数据个数大于 10 ，就会执行扩容操作，扩容操作会影响性能，详情见 add 方法分析。

小结：使用 ArrayList 时，你心理要有点数，大概要往里面放多少条数据，就初始化容量是多少，避免扩容。

2.2 add(e)

这个方法是往数组的尾部添加数据，代码入下:

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

第2 行代码是判断是否需要扩容操作，第 3 行代码是实际的尾部赋值操作，扩容参见下面的 2.2.1 。

2.2.1 ensureCapacityInternal

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

minCapacity 的值为 size + 1，即原先数组长度 + 1，通过 calculateCapacity 方法计算新数组长度。

private static int calculateCapacity(Object[] elementData, int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    return minCapacity;
}

如果之前数组为空数组，返回默认数组长度和新数组长度的最大值，这种情况只会在使用 ArrayList() 无初始容量构造函数，然后第一次执行 add 操作时发生。其他情况均返回 minCapacity 。

然后我们看 ensureExplicitCapacity 方法。

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

    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

关于 modCount ，之前篇文章已经讲过了，可以参考 集合中的modCount。如果当前容量大于了数组的长度，开始扩容。下面是扩容的方法：

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);
}

扩容方法很简单，其中判断了最小长度和最大长度，比较有意思的地方有两个。

oldCapacity + (oldCapacity >> 1)

oldCapacity >> 1 位移算法，其实相当于除以 2 ，所以数组扩容是在之前的容量上乘以 1.5 。

Arrays.copyOf(elementData, newCapacity)

这是调用底层数组复制的方法 System.arraycopy ，就是它，那个影响性能的罪魁祸首。该方法在 2.3 中会有详解。

注意： size 的大小和 elementData.length 的大小是不一样的，size 是实际有数据的个数，新 new 一个初始容量为 10 的数组，此时 size 也为 0，只有在执行 add 方法，往 ArrayList 里面塞数据之后，size 才会增加。

2.3 add(index,e)

这个方法是在数组中间添加数据，区别于 add 方法的是需要判断边界，是否发生数组越界。数组复制的逻辑稍有区别，其他的，和 add 方法差不多。具体看代码：

public void add(int index, E element) {
    rangeCheckForAdd(index);

    ensureCapacityInternal(size + 1);  // Increments modCount!!
    System.arraycopy(elementData, index, elementData, index + 1,
                     size - index);
    elementData[index] = element;
    size++;
}

第 2 行代码是校验传来的 index 是否在数组范围内，很简单。

第 4 行代码和 add 方法中的一模一样，进行扩容。

比较重要的是第 5 行数组复制代码，我们来仔细研究下。

System.arraycopy详解

我们看一下 System.arraycopy 方法的 API 。

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

• src : 原数组
• srcPos : 原数组复制起始位置
• dest : 目标数据
• destPos : 目标数组起始位置
• length : 复制的长度。

下面举个例子来说明：

假设有个数组：[“a”,”b”,”c”,”d”] ，现在调用 add(2,”e”) ，我们看下，执行第 5 行代码时效果如下：

System.arraycopy(elementData, index, elementData, index + 1,
                 size - index);

elementData = [“a”,”b”,”c”,”d”] index = 2 index + 1 = 3 size - index = 4 - 2 = 2

从 elementData 的 index 为 2 的元素开始复制（也就是从 “c” 开始），复制的长度为 2 ，目标数组还是 elementData ，从 index 为 3 的位置开始。复制之后就变成了 [“a”,”b”,”c”,”c”,”d”] 。

执行第 7 行代码，elementData[index] = element ，即 elementData[2] = “e” 。最后 elementData 变成了 [“a”,”b”,“e”,”c”,”d”] 。

2.4 remove

其实 remove 方法和 add(index ,e) 方法比较类似，本质都是改变了数组的结构，导致数组需要移位，移位就调用底层的复制方法 System.arraycopy 。

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;
}

第 2 行代码校验是否是否越界，第 7 8 9 10 行代码是数组复制操作，接着上面 add 的例子往下讲。

elementData = [“a”,”b”,“e”,”c”,”d”] ，假设现在 remove(3) ，numMoved = size - index - 1 = 5 - 3 - 1 = 1，index + 1 = 4，复制方法实际为 System.arraycopy(elementData, 4, elementData, 3, 1) 。解释一下就是，从 index 为 4 的位置开始复制（即从“d”开始），复制长度为1，目标数组同样是 elementData ，从 index 为 3 的位置（即从“c”开始）。复制后的结果变成了 [“a”,”b”,“e”,”d”,”d”] 。

然后执行第 11 行代码 ，将最后一个值赋值为 null ，便于gc 回收，数组变成了 [“a”,”b”,“e”,”d”]，size 减 1 之后变成了 4 。

3. 总结

其实 ArrayList 的底层就是在数组的基础上，加了部分特性（比如 modCount）。所以只要搞清楚数组这个基础的数据结构，ArrayList 理解起来很简单。

至于源码中其他的方法，例如 get 、set 等，就比较简单，不一一赘述了。

4. 相关链接

transient Object[] elementData;

如代码所示，ArrayList 中存储数据的数组 elementData 用 transient 关键字修饰，是不被序列化的。

关于手动序列化可以参见 transient关键字 ，Java序列化—Externalizable 。