Rayjun

Java容器系列-ArrayList源码分析

ArrayList 是使用的最为广泛的一个容器。ArrayList 的类的继承层次图如下:

ArrayList 实现了 Collection 和 List 接口，同时也实现了 Cloneable、RandomAccess，所以 ArrayList 可以被拷贝以及具有随机访问的特性。

本文基于 JDK1.8

成员变量

在 ArrayList 类的头部，定义了以下几个成员变量。

private static final int DEFAULT_CAPACITY = 10;
private static final Object[] EMPTY_ELEMENTDATA = {};
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
transient Object[] elementData;
private int size;

这几个变量构成了 ArrayList 的基础。

DEFAULT_CAPACITY 表示 ArrayList 的初始容量。elementData 是存储具体数据的数组，也就是是说，ArrayList 底层数据结构就是一个数组，size 表示 ArrayList 中元素的个数。EMPTY_ELEMENTDATA 表示一个空的 ArrayList 对象，但 ArrayList 中没有数据时，elementData 指向的就是这个数组对象。DEFAULTCAPACITY_EMPTY_ELEMENTDATA 也表示空的 ArrayList，它只会在实例化一个不带参数的 ArrayList 的时候被使用一次：

ArrayList list = new ArrayList(); // 此时 elementData 指向的就是 DEFAULTCAPACITY_EMPTY_ELEMENTDATA

这些变量中需要注意的是 elementData 是不带访问修饰符的，这是为了让 ArrayList 的内部类可以方便的访问它，ArrayList 的内部类后面会讲到。elementData 变量是使用 transient 来修饰的，这表示在序列化的时候 elementData 是不会被序列化的，具体的序列化方式后面再讲。

初始化过程

在上面说到 DEFAULT_CAPACITY 是 ArrayList 的默认容量，值是10，但是需要注意的是，默认容量不一定用的上，在实例化 ArrayList 的时候分三种情况，第一种不给构造函数传参，但是此时会新建一个长度为 10 的对象数组。而是在添加第一个元素的时才会创建一个长度为 10 的数组，并把第一个元素添加进去。第二种情况会给构造参数传值 n，如果 n 大于0，那么就会直接创建一个长度为 n 的对象数组，如果 n 等于 0，那么就会把 EMPTY_ELEMENTDATA 赋值给 elementData。

第三种实例化特殊一点，是直接传入另一个容器对象 c 来初始化 ArrayList 对象，此时会先检查 c 的长度，如果 c 容器里面没有元素，直接把 EMPTY_ELEMENTDATA 赋值给 elementData，如果 c 不为空，就会 c 中的元素拷贝到 elementData 中。

扩容过程

扩容的过程可以用以下的流程图来表示：

扩容对 ArrayList 来说是一个很重要的过程，这也是为什么它比数组好用的原因。

ArrayList 的扩容有两种方式，一个是自动扩容，一种是手动扩容。自动扩容每次会把当前容器的大小扩大 1.5 倍，手动扩容需要指定大小。既然已经有了自动扩容，那为什么还需要手动扩容呢？设想一个场景，实例化一个 ArrayList 之后，你大概知道会填充一万个元素，如果这个时候自动扩容的话要经过多次扩容才能装下这么多元素，但是手动指定容器大小的话只需要一次就可以了。

具体把 ArrayList 扩容到多大是由下面这段代码决定的:

    private int newCapacity(int minCapacity) {
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity <= 0) {
            if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
                return Math.max(DEFAULT_CAPACITY, minCapacity);
            if (minCapacity < 0) // overflow
                throw new OutOfMemoryError();
            return minCapacity;
        }
        return (newCapacity - MAX_ARRAY_SIZE <= 0)
            ? newCapacity
            : hugeCapacity(minCapacity);
    }

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

newCapacity 是根据当前的元素的个数计算出来的，右移一位代表除以2，所以 newCapacity 为当前容量的 1.5 倍。然后这个值会与传入的值 minCapacity 进行对比，两个值哪个大就用哪个。

为什么每次自动扩容都能为当前大小的 1.5 倍呢？那是因为自动扩容的时候传入的 minCapacity 都只比当前的容量大 1，所以肯定小于 newCapacity。而 newCapacity 就是 当前容量大小的 1.5 倍。

当然有一个情况例外，那就是如果在实例化 ArrayList 没有指定大小的话，ArrayList 会至少扩容到 10。这一机制是靠以下代码实现的:

 if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
    return Math.max(DEFAULT_CAPACITY, minCapacity);

扩容的时候，都是使用 Arrays.copyOf 将元素拷贝到新的容器中。所以基本都是 $O(N)$ 的时间复杂度，代价很大。所以尽可能减少扩容的次数。

注意：ArrayList 没有缩容的过程。

具体实现

ArrayList 中有了很多的方法，这些方法核心都是围绕 elementData 操作的。

siez() 和 isEmpty() 方法想着简单，一个用来返回容器中的元素的数量，一个用来判断容器是否为空。

clone() 、 toArray() 和 toArray(T[] a) 这三个方法本质上都是对容器当前的元素做一个备份，都用到了 Arrays.copyOf() 方法。但是需要注意的是 toArray(T[] a) 的实现:

public <T> T[] toArray(T[] a) {
    if (a.length < size)
        // Make a new array of a's runtime type, but my contents:
        return (T[]) Arrays.copyOf(elementData, size, a.getClass());
    System.arraycopy(elementData, 0, a, 0, size);
    if (a.length > size)
        a[size] = null;
    return a;
}

在这个方法中除了使用 Arrays.copyOf() 还用到了 System.arraycopy()，其实 Arrays.copyOf() 底层就是使用 System.arraycopy() 方法实现的。但是区别在于前者会返回一个一个新的数组，后者则是直接在原数组上进行操作。

ArrayList 中的 add()、get() 、set()、remove() 等方法用于元素的增删改查，实现并不复杂，只是在操作元素之前需要对容器的 size 进行检查，如果不满足操作要求，就会报出异常。

euqal() 类的方法主要都是对比每个元素的类型、顺序和值是否一致。

在 JDK1.8 以后，出现了 removeIf() 方法，这个方法使得从容器中删除元素变得很简单。

迭代器

ArrayList 中有两个内部类 Itr 和 ListItr，主要方法如下：

private class Itr implements Iterator<E> {
    Itr() {}

    public boolean hasNext() {
    }

    public E next() {
      
    }

    public void remove() {
    }
}

private class ListItr extends Itr implements ListIterator<E> {
    ListItr(int index) {
        super();
        cursor = index;
    }

    public boolean hasPrevious() {
    }

    public int nextIndex() {
    }

    public int previousIndex() {
    }

    public E previous() {
    }

    public void set(E e) {
    }

    public void add(E e) {
    }
}

ListItr 继承了 Itr，这两个内部类都实现了迭代器模式，用于遍历 ArrayList 的元素。从上面的方法可知，Itr 和 ListItr 最大的区别在于 ListItr 可以从两个方向对容器的元素进行遍历。而 Itr 只能使用顺着一个方向进行遍历。

在 JDK1.8 以后，ArrayList 中有一个 ArrayListSpliterator 内部类，这个类用于分割容器。用于提升多线程环境中的处理效率：

ArrayList<Integer> list = new ArrayList<>();
for (int i = 0; i < 10; i++) {
    list.add(i);
}
Spliterator<Integer> s0 = list.spliterator();
System.out.println(s0.estimateSize()); // 5
Spliterator<Integer> s1 = s0.trySplit();
System.out.println(s1.estimateSize()); // 5

s0 中有 10 个元素，在调用 s0.trySplit() 方法之后，s0 和 s1 中各有 5 个元素。然后可以对分割开的元素进行处理:

s0.forEachRemaining(i -> System.out.println(i));

SubList

ArrayList 中还有一个内部类 SubList。SubList 用于返回 ArrayList 的一部分元素，内部的操作方法与 ArrayList 基本一致，但是需要注意的是，对 SubList 的操作会直接影响到原 ArrarList。

fail-fast 机制

在 ArrayList 中，checkForComodification() 和 ConcurrentModificationException() 使用的频率很高。这个和 fail-fast 机制有关。

ArrayList 不是线程安全的，所以在对容器操作的过程中，容器的元素倍其他的操作或者线程修改之后，就会出现 ConcurrentModificationException 异常。checkForComodification() 方法就是用来检查元素是否被修改。这个机制就称之为 fail-fast。

后续会有其他的文章来介绍 fail-fast。

(完)

©2024 Rayjun    PowerBy Hexo