ArrayList 源码学习

ArrayList 源码分析

当前分析的源码版本为

jdk 1.7.0_80

ArrayList 是一个动态数组容器类。下方的代码为 ArrayList 的定义。

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

一、add() 方法的扩容原理是什么

先看源码

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

代码中的 elementData 和 size 是 ArrayList 类的两个成员变量。

transient Object[] elementData; // non-private to simplify nested class access
private int size;

代码注释中的 Increments modCount!! 在遍历的方法中再讲。modCount 代表容器被修改的次数。
首先调用 ensureCapacityInternal(size + 1) 方法确保容量是够的。然后对 elementData[size++] 进行赋值，最后 size 加 1。以下为 ensureCapacityInternal() 方法的代码。

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

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

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

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

grow() 方法的主要内容为

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。可以看出容器的容量扩大了原来的 1.5 倍。

二、remove() 方法

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

private void rangeCheck(int index) {
    if (index >= size)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

remove() 方法的代码相对简单，主要是调用了 System.arraycopy() 方法对数组 elementData 自身进行复制，起始位置从 index+1 复制到 index 。然后将索引位置在 size-- 的元素的引用置为 null， 最后 size 减一。

三、ArraysList 中的向前遍历

ArrayList 类中维护了一个私有的内部类 ListItr，ListItr 实现了 ListIterator 接口。以下为 ListItr 的定义。

private class ListItr extends Itr implements ListIterator<E> {
    // TODO ...
}

接口 ListIterator 继承了 Iterator 接口，并新增了几个新的方法。下面是 ListIterator 的方法。

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

来看一个简单的降序遍历的例子。

public static void main(String[] args) {
    List<Integer> list = new ArrayList<>(Arrays.asList(1, 2, 3));
    ListIterator<Integer> descItr = list.listIterator(list.size());
    while (descItr.hasPrevious()) {
        Integer previous = descItr.previous();
        System.out.println(previous);
    }
}

输出

3
2
1

四、modCount 有什么作用

modCount 是 AbstractList 中的一个成员变量，记录容器类结构发生变化的次数，使容器结构发生变化的方法比如有 add() 和 remove() 方法。

protected transient int modCount = 0;

接下要从方法 iterator() 说起。

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

Itr 是 ArrayList 中的一个内部类，实现了 Iterator 接口。

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;
    
    public boolean hasNext(){...}
    public E next() {...}
    public void remove() {...}
    final void checkForComodification() {...}
}

cursor 是下一个要返回的元素的索引值。lastRet 是最后一次要返回的元素的索引值。expectModCount 表示期望地修改次数。在初始化迭代器的时候复赋值为 modCount。

下面代码中要通过迭代器删除 list 中的一个元素，并解释迭代器中每个方法的工作原理。

public static void main(String[] args) {
    List<Integer> list = new ArrayList<Integer>();
    list.add(1);
    list.add(2);
    list.add(3);
    Iterator<Integer> iterator = list.iterator();
    Integer next;
    while(iterator.hasNext()) {
        next = iterator.next();
        if (next == 3) {
            iterator.remove();
        }
    }
    System.out.println(list.size());
}

while 循环中，先执行 hasNext() 方法，判断元素的索引位置是否超过容器容量。

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

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

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

next() 方法先调用 checkForComodification() 检查容器的结构是否发生变化。在方法 checkForComodification() 中，如果 modCount != expectedModCount 就抛出异常 throw new ConcurrentModificationException(); 。检查成功后对下一个元素的索引变量 cursor 进行赋值，然后赋值给变量 lastRet，最后返回当前索引位置所在的元素。

下面是删除方法 remove() 的源代码。

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

执行 remove() 方法的第一步就是对 lastRet 的检查。所以在使用迭代器遍历时，调用 remove() 方法前一定要调用 next() 方法。在 next() 方法的结尾处会对 lastRet 方法进行赋值，否则 lastRet 的初始值为 -1，就会抛出异常 java.lang.IllegalStateException。

接下来调用 ArrayList 的 remove() 方法。然后对 expectModCount 进行赋值，保证容器结构的一致。

五、为什么在 foreach 方法中删除元素会抛异常

下面使用 foreach 语法删除一个元素。

public static void main(String[] args) {
    List<Integer> list = new ArrayList<>(5);
    list.add(1);
    list.add(2);
    list.add(3);
    list.add(4);
    list.add(5);
    for (Integer i : list) {
        if (i == 5) {
            list.remove(i);
        }
    }
}

运行后控制台抛出异常。

Exception in thread "main" java.util.ConcurrentModificationException

foreach 是 java 中的一颗语法糖，编译后的字节码文件是这样的。

public static void main(String[] args) {
    List<Integer> list = new ArrayList();
    list.add(1);
    list.add(2);
    list.add(3);
    Iterator<Integer> iterator = list.iterator();
    System.out.println(list.size());
    List<Integer> list1 = new ArrayList();
    list1.add(1);
    list1.add(2);
    list1.add(3);
    Iterator i$ = list1.iterator();

    while(i$.hasNext()) {
        Integer integer = (Integer)i$.next();
        if (integer == 3) {
            list1.remove(integer);
        }
    }
}

上面代码中的 remove() 方法如下。

public boolean remove(Object o) {
    if (o == null) {
        for (int index = 0; index < size; index++)
            if (elementData[index] == null) {
                fastRemove(index);
                return true;
            }
    } else {
        for (int index = 0; index < size; index++)
            if (o.equals(elementData[index])) {
                fastRemove(index);
                return true;
            }
    }
    return false;
}

private void fastRemove(int index) {
    modCount++;
    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
}

程序最后走到了 fastRemove() 方法中。fastRemove() 方法和迭代器中的 remove() 方法不同，程序中并没有维护 expectedModCount = modCount。所以在 next() 方法中执行 checkForComodification()，发现 expectedModCount 和 modCount 不同，容器的结构发生了变化，就会抛出异常 throw new ConcurrentModificationException()。

六、ArrayList 中的其他方法

在开发过程中还有一些 ArraysList 中的常用方法。

// 构造器方法
public ArrayList(int initialCapacity) {...}
public ArrayList() {...}
public ArrayList(Collection<? extends E> c) {...}
// 判断容器中元素的个数
public int size() {...}
// 判断元素是否为空
public boolean isEmpty() {...}
// 是否包含某个元素
public boolean contains(Object o) {...}
// 找出元素的索引位置
public int indexOf(Object o) {...}
public int lastIndexOf(Object o) {...}
// 将容易转换为数组
public Object[] toArray() {...}
public <T> T[] toArray(T[] a) {...}
// 获取元素
public E get(int index) {...}
// 替换元素
public E set(int index, E element) {...}

（完）