Java编程拾遗『容器——ArrayList』

上篇文章简单介绍了一下Java集合框架中两个最常见的接口，表示集合的Collection和表示K-V映射的Map。本篇文章重点介绍一下Collection的一个重要实现类，动态数组容器类ArrayList。由于在上一篇文章已经介绍了Collection接口的通用方法，本篇文章会简单介绍一下ArrayList中的方法，重点介绍一下内部原理。

1. 使用规则

ArrayList是基于数组实现的一个动态数组，在使用过程中，如果容量不足，会进行动态扩容，声明如下：

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

继承AbstractList抽象类，实现泛型接口List的原因在上一篇文章已经说明——使用AbstractList抽象类更方便实现List接口(AbstractList中已经实现了很多List接口中的方法)。另外ArrayList实现了RandomAccess接口，支持快速随机访问(通过数组下标序号进行快速访问)；实现了Serializable接口，支持序列化，能够通过序列化传输；实现了Cloneable接口，可以被克隆。

2. 实现源码分析

查看ArrayList内部源码可以发现，ArrayList的实现最终要的两个成员就是用来存放元素的Object[]数组，还有一个用来表示实际元素个数的size，ArrayList内部所有的方法都试基于这两个成员实现的。如下所示：

transient Object[] elementData;
private int size;

除此之外，还有三个共享的静态常量，如下：

private static final int DEFAULT_CAPACITY = 10; //elementData数组默认容量

private static final Object[] EMPTY_ELEMENTDATA = {}; //空数组

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; //默认容量空元素数组

2.1 默认构造函数

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

先讲一个结论，通过默认构造函数构造的ArrayList，默认容量是10。通过上述源码可以看到默认构造函数实际上是将内部elementData数组初始化为DEFAULTCAPACITY_EMPTY_ELEMENTDATA，DEFAULTCAPACITY_EMPTY_ELEMENTDATA 的定义是一个容量为0的空数组，但是语义上却说这是个有着默认容量10的空数组，那么这个默认容量是怎么实现的？其实是通过Add方法来实现这个默认容量设置的。

2.2 add(E e)方法

add方法定义如下所示：

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

基本原理很简单，就是通过ensureCapacityInternall确保数组容量是够的，然后像内部数组中添加元素。ensureCapacityInternall源码如下：

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

ensureCapacityInternal方法内部调用了两个方法，分别是用来计算需要的最小容量的calculateCapacity方法，和用来分配容量的ensureExplicitCapacity方法，下面先来看一下calculateCapacity方法：

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

这里可以看到，假如elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA(通过默认构造函数构造的情况)，方法的返回值是肯定是DEFAULT_CAPACITY(因为此时calculateCapacity方法入参minCapacity是1)。接下来将返回值作为ensureExplicitCapacity方法的实参传入分配空间，如下：

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

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

modCount表示内部的修改次数，modCount++就表示增加修改次数，关于这个modCount，接下来会解释。如果计算得到的ArrayList需要的最小容量大于现elementData数组的length，说明需要进行扩容了。这里特殊提一下ArrayList通过默认构造函数构造然后add元素的过程，上面已经讲过，这种场景下计算得到的minCapacity是10，但是此时elementData是DEFAULTCAPACITY_EMPTY_ELEMENTDATA(长度为0的空数组)，所以肯定会执行grow函数进行扩容。下面看一下gorw扩容操作：

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

看核心的这一行，如下：

int newCapacity = oldCapacity + (oldCapacity >> 1);

右移一位相当于除2，所以，ArrayList扩容的逻辑是，newCapacity相当于oldCapacity的1.5倍。回到上面讲的通过默认构造函数构造的场景，可以得到newCapacity为10，也就是讲，通过ArrayList的默认构造函数，内部数组的容量默认为10。

2.3 add(int index, E element)方法

这个方法没什么好讲的，就是在ArrayLIst内部elementData数组特定的index位置插入element元素，但是这里我还是想提一下，因为这边有一个我认为比较容易出错的地方，就是插入的位置index不能大于ArrayList中元素个数size。2.2节讲的add方法，相当于一次向ArrayList数组尾部插入元素，这时候我脑洞大开，想能不能通过add(int index, E element)方法构造一个如下的数组：

List<Integer> integerList = new ArrayList<>();
integerList.add(1, 1);
integerList.add(3, 2);

好像通过上述代码就可以构造出如上的ArrayList，但是很不幸的是，报了IndexOutOfBoundsException。来看一下add(int index, E element)方法的源码：

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

首先检查了index，然后通过ensureCapacityInternal保证数组有足够的容量，然后通过System.arraycopy做移位操作，讲index位置及以后的元素往后移一个位置，最后对index位置进行赋值。而上述的IndexOutOfBoundsException就是在检查index的rangeCheckForAdd方法中报的，如下：

private void rangeCheckForAdd(int index) {
    if (index > size || index < 0)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

也就是讲ArrayList的add(int index, E element)操作只能在size范围内进行插入。如果要构造出上图所示的ArrayList可以通过如下方式：

integerList1.add(1);
integerList1.add(2);
integerList1.add(0, null);
integerList1.add(2, null);

2.4 迭代器iterator

上面讲过通过iterator()方法可以获取ArrayList的迭代器，可以用来遍历ArrayList。在讲ArrayList迭代器之前，先明确两个接口的概念：Iterable、Iterator。Iterable接口表示可迭代，定义为：

public interface Iterable<T> {
    
    Iterator<T> iterator();

    default void forEach(Consumer<? super T> action) {
        Objects.requireNonNull(action);
        for (T t : this) {
            action.accept(t);
        }
    }

    default Spliterator<T> spliterator() {
        return Spliterators.spliteratorUnknownSize(iterator(), 0);
    }
}

所有实现了Iterable接口的类都要实现iterator()方法，iterator()方法返回一个Iterator对象，Iterator接口定义如下：

public interface Iterator<E> {
    
    boolean hasNext();

    E next();

    default void remove() {
        throw new UnsupportedOperationException("remove");
    }

    default void forEachRemaining(Consumer<? super E> action) {
        Objects.requireNonNull(action);
        while (hasNext())
            action.accept(next());
    }
}

• hasNext()：判断是否还有元素未访问
• next()：返回下一个元素
• remove()：删除最后返回的元素

可以通过Iterator对象对实现了Iterable接口的类进行迭代，如下：

Iterator<Integer> iterator = list.iterator();
while(iterator .hasNext()){
    System.out.println(iterator.next());
}

下面来看一下ArrayList类中，iterator()方法的实现：

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

可以看到方法返回的是一个Itr类的实例，Itr类是ArrayList中的一个内部类，定义如下：

private class Itr implements Iterator<E> {
    int cursor;       // index of next element to return
    int lastRet = -1; // index of last element returned; -1 if no such
    int expectedModCount = modCount;

    Itr() {}

    public boolean hasNext() {
        return cursor != size;
    }

    @SuppressWarnings("unchecked")
    public E next() {
        checkForComodification();
        int i = cursor;
        if (i >= size)
            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();
        checkForComodification();

        try {
            ArrayList.this.remove(lastRet);
            cursor = lastRet;
            lastRet = -1;
            expectedModCount = modCount;
        } 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;
        checkForComodification();
    }

    final void checkForComodification() {
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
    }
}

实现比较简单，就是通过cursor表示当前遍历到的元素的index，默认值为0(Iterator迭代器从index 0开始遍历)。然后通过cursor访问ArrayList内部ArrayList数组，实现上述Iterator接口的next、hasNext、remove方法。对于方法的实现这里不详细讲解了，重点来看一下Itr类的成员变量expectedModCount，表示期望修改的次数，初始值为modCount。对于modCount，上面讲过，是ArrayList类中的成员变量，每次ArrayList内部elementData数组改变都会进行modCount++操作。观察Itr实现可以发现，每次调用next、remove及forEachReminding方法访问ArrayList时，都会调用checkForComodification方法，比较modCount和expectedModCount值是否相等，不相等就会抛ConcurrentModificationException异常。所以在这我们可以很明确地得到一个结论：在使用迭代器遍历过程中，改变了容器结构，那么肯定会抛ConcurrentModificationException异常。如下：

List<Integer> integerList = new ArrayList<>();
integerList.add(1);
integerList.add(2);
integerList.add(3);
integerList.add(4);

for(Integer i : integerList) {
    if (i == 2) {
        integerList.remove(i);
    }
}

这里要注意的是，使用for(:)这种形式遍历容器，其实是一种语法糖，编译器会编译成如下形式：

Iterator var2 = integerList.iterator();
while(var2.hasNext()) {
    Integer i = (Integer)var2.next();
    if (i == 2) {
        integerList.remove(i);
    }
}

执行，会抛ConcurrentModificationException异常，也很好解释，因为当i==2时，调用integerList的remove方法，modCount会加1。在下次进入循环，调用迭代器的next方法时，expectedCount和modCount不再相等，抛ConcurrentModificationException异常。但是如果代码如下时，是不会抛异常的：

for(Integer i : integerList) {
    if (i == 3) {
        integerList.remove(i);
    }
}

看着好像很奇怪，命名在使用迭代器遍历时，修改了ArrayList结构，为什么没有抛ConcurrentModificationException异常？其实原因是，当i == 3时，确实执行了integerList的remove方法，modCount也自增了，但是同时ArrayList的size也减少了1，所以下次进行hasNext判断时，cusor == 3 == size，所以hasNext结果为false，不会进入循环体执行next操作，导致没有抛ConcurrentModificationException异常。普遍情况下，我们都认为，在使用迭代器进行迭代时，是不允许通过容器的方法修改容器的。假如有这种需求，在迭代的过程中删除某些特定元素，可以通过迭代器的remove方法实现，如下：

Iterator<Integer> it = integerList.iterator();
while(it.hasNext()){
    if(it.next() == 2){
        it.remove();
    }
}

在Java 8之后，可以调用Collection接口的新方法removeIf实现相同的效果，如下：

integerList.removeIf(integer -> integer == 2);

2.5 迭代器listIterator

除了iterator()，ArrayList中还提供了两个返回ListIterator接口的方法：

public ListIterator<E> listIterator()
public ListIterator<E> listIterator(int index)

理解了上述Iterator接口之后，ListIterator就比较好理解了。ListIterator扩展了Iterator接口，支持双向遍历。增加了一些方法，向前遍历、添加元素、修改元素、返回索引位置等，如下：

public interface ListIterator<E> extends Iterator<E> {
    
    boolean hasNext();
    E next();
    boolean hasPrevious();
    E previous();
    int nextIndex();
    int previousIndex();
    void remove();
    void set(E e);
    void add(E e);
    
}

比较好理解，这里不多解释了。listIterator()方法返回的迭代器从0开始，而listIterator(int index)方法返回的迭代器从指定位置index开始，比如，从容器末尾往前遍历可以通过如下方式实现：

ListIterator<Integer> iterator = list.listIterator(list.size());
while(iterator.hasPrevious()){
    System.out.println(iterator.previous());
}

3. ArrayList特点

通过上面介绍的ArrayList的内部实现（基于数组实现），可以总结出ArrayList有如下特点：

• 支持随机访问，按照索引位置进行访问效率很高，时间复杂度为O(1)
• 插入和删除元素的效率比较低，时间复杂度为O(N)，因为数组内部要进行移位
• 查找元素效率比较低，如果在未排序的前提下，时间复杂度为O(N)，如果已排序，可以通过二分查找，时间复杂度为O(logN)

所以如果需求中，容器的变动比较大，有大量的插入删除操作，尽量不要使用ArrayList，可以选用下节要讲的LinkedList容器。

参考链接：

1. 《Java编程的逻辑》
2. 《Java核心技术 卷Ⅰ》
3. JDK源码