ArrayList 解析

ArrayList 类，是基于数组实现的 List,本质上对其的操作和对数组的操作相同。本文旨在简单介绍 Java8 中的部分实现、一些使用中应当注意的细节、以及 JDK8 中新添的“有趣”的特性。

下图为 ArrayList 类的继承关系：

官方介绍

ArrayList 是 List 接口的大小可变数组的实现。实现了所有可选列表操作，并允许包括 null 在内的所有元素。除了实现 List 接口外，此类还提供一些方法来操作内部用来存储列表的数组的大小。（此类大致上等同于 Vector 类，除了此类是不同步的。）

size、isEmpty、get、set、iterator 和 listIterator 操作都以固定时间运行。add 操作以分摊的固定时间运行，也就是说，添加 n 个元素需要 O(n) 时间。其他所有操作都以线性时间运行（大体上讲）。与用于 LinkedList 实现的常数因子相比，此实现的常数因子较低。

每个 ArrayList 实例都有一个容量。该容量是指用来存储列表元素的数组的大小。它总是至少等于列表的大小。随着向 ArrayList 中不断添加元素，其容量也自动增长。并未指定增长策略的细节，因为这不只是添加元素会带来分摊固定时间开销那样简单。

在添加大量元素前，应用程序可以使用 ensureCapacity 操作来增加 ArrayList 实例的容量。这可以减少递增式再分配的数量。

注意，此实现不是同步的。如果多个线程同时访问一个 ArrayList 实例，而其中至少一个线程从结构上修改了列表，那么它必须保持外部同步。（结构上的修改是指任何添加或删除一个或多个元素的操作，或者显式调整底层数组的大小；仅仅设置元素的值不是结构上的修改。）这一般通过对自然封装该列表的对象进行同步操作来完成。如果不存在这样的对象，则应该使用 Collections.synchronizedList 方法将该列表“包装”起来。这最好在创建时完成，以防止意外对列表进行不同步的访问：

List list = Collections.synchronizedList(new ArrayList(...));
​

此类的 iterator 和 listIterator 方法返回的迭代器是 Fail-fast 的：在创建迭代器之后，除非通过迭代器自身的 remove 或 add 方法从结构上对列表进行修改，否则在任何时间以任何方式对列表进行修改，迭代器都会抛出 ConcurrentModificationException。因此，面对并发的修改，迭代器很快就会完全失败，而不是冒着在将来某个不确定时间发生任意不确定行为的风险。

注意，迭代器的 Fail-fast 行为无法得到保证，因为一般来说，不可能对是否出现不同步并发修改做出任何硬性保证。Fail-fast 迭代器会尽最大努力抛出 ConcurrentModificationException。因此，为提高这类迭代器的正确性而编写一个依赖于此异常的程序是错误的做法：迭代器的快速失败行为应该仅用于检测 bug。

静态变量和实例变量

    // 默认的容量为10
    private static final int DEFAULT_CAPACITY = 10;

    // 默认容量空实例共用该空数组实例
    private static final Object[] EMPTY_ELEMENTDATA = {};

    // 默认容量空实例共用该空数组实例。使用DEFAULTCAPACITY_EMPTY_ELEMENTDATA的原因见下一个字段
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    // 容量的最大值，一些虚拟机在数组中保留一些header words，尝试分配更大的数组时可能导致OutOfMemoryError
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

    // 保存ArrayList元素的数组。数组的长度即为ArrayList容量。
    // 在elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA 且添加第一个元素时，
    // elementData 将被扩充到DEFAULT_CAPACITY 大小
    transient Object[] elementData;

    // ArrayList的size
    private int size;
​

构造函数

    // 带有初始容量，大于0时直接创建对应大小的数组
    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);
        }
    }

   // 未指定初始容量，使用DEFAULTCAPACITY_EMPTY_ELEMENTDATA代表空数组
    public ArrayList() {
        this.elementData = 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;
        }
    }
​

添加元素

    // 添加元素函数
    public boolean add(E e) {
        // 保证容量最小为 size + 1
        ensureCapacityInternal(size + 1);
        //元素添加到数组末尾
        elementData[size++] = e;
        return true;
    }


    // 私有函数，保证保存数组elementData容量最小为minCapacity
    private void ensureCapacityInternal(int minCapacity) {
        // 如果未指定初始容量,则第一次扩容为默认的10
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }

        ensureExplicitCapacity(minCapacity);
    }


    // 私有函数，提供明确的最小容量
    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;

        // 最小容量大于当前容量，扩容
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

    // 扩容函数
    private void grow(int minCapacity) {
        int oldCapacity = elementData.length;
        // 容量增加0.5倍
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        // 容量增加0.5倍后还是小于要求的容量，则使用要求的容量
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        // 扩容后的容量大于最大容量要求，需要校验，此处有两种可能：
        // 一种是扩容的容量确实大于最大容量
        // 另一种可能就是容量增加0.5倍导致newCapacity溢出，即超出int的最大值
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

    // 校验容量是否合法
    private static int hugeCapacity(int minCapacity) {
        // 容量超出int的最大值
        if (minCapacity < 0)
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }
​

Java8 新特性

在 Java8 版本中，增强了对函数式编程的支持，在 ArrayList 中当然也必不可少。下面介绍两个方便操作的方法，体会下函数式编程的魅力(此时推荐下《Java8 简明教程》)。

forEach

Java 中的 foreach 和此处的 forEach 虽然在运行的结果上来看区别不大，但是运行的机制可大不相同，具体代码如下:

public class ConsumerTest {

    public static void main(String[] args) {
        List<Integer> list = new ArrayList<>();
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(4);
        list.add(5);
        System.out.println("forEach:");
        list.forEach((a) -> System.out.printf(a + " "));

        System.out.println();
        System.out.println("foreach:");
        for (Integer a : list)
            System.out.printf(a + " ");
    }

}

​

执行结果：

forEach:
1 2 3 4 5
foreach:
1 2 3 4 5
​

removeIf

在 Java8 之前，如果你想删除 ArrayList 中符合特定条件的数据，会怎么做？
循环遍历删除的话，ArrayList 在删除时会改变索引。使用 foreach 删除？那你的程序运行的好吗（手动笑）。
使用 removeIf 方法，让我们来看看什么叫爽:

public class ConsumerTest {

    public static void main(String[] args) {
        List<Integer> list = new ArrayList<>();
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(4);
        list.add(5);
        System.out.println("removeIf 前:");
        list.forEach((a) -> System.out.printf(a + " "));

        list.removeIf((a) -> a % 2 == 0);

        System.out.println("");
        System.out.println("removeIf 后:");
        list.forEach((a) -> System.out.printf(a + " "));
    }

}
​

执行结果:

removeIf 前:
1 2 3 4 5
removeIf 后:
1 3 5
​

上述代码删除 ArrayList 中可以被 2 整除的整数，只需要一行代码搞定。