JAVA源码解释之ArrayList

简介

由于ArrayList类插入有序以及高性能的元素访问特性，使得它成为了我们最常用的一个集合类，我们先看下它的类图。可以看到它实现了以下几个接口

List接口，意味着它是JAVA结合框架的一部分
RandomAccess接口，说明ArrayList支持快速的随机访问，它内部任意位置的元素访问都是O(1)复杂度
Cloneable接口，表示ArrayList是可以被克隆的
java.io.Serializable接口，说明ArrayList是可以被序列化和反序列化的

重点属性

// 初始容量
private static final int DEFAULT_CAPACITY = 10;
// 用来存放数据的数组
transient Object[] elementData;
// 数组内数据到数量
private int size;

构造函数

// 第一种方式，创建一个空集合
public ArrayList() {
     this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

// 第二种方式，创建一个指定容量的空集合
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);
    }
}

// 第三种方式，基于给定的集合构建一个ArrayList，新的ArrayList中的元素以及元素的顺序都与原集合中的保持一致
public ArrayList(Collection<? extends E> c) {
    Object[] a = c.toArray();
    if ((size = a.length) != 0) {
        if (c.getClass() == ArrayList.class) {
            elementData = a;
        } else {
            elementData = Arrays.copyOf(a, size, Object[].class);
        }
    } else {
        // replace with empty array.
        elementData = EMPTY_ELEMENTDATA;
    }
}

关键方法

保存数据

add(E e)

在集合的尾部加入元素，如果数组已满则先触发一次扩容，再将数据添加到集合的尾部

public boolean add(E e) {
    // 用于快速失败，后面会单独介绍这个机制
    modCount++;
    add(e, elementData, size);
    return true;
}

private void add(E e, Object[] elementData, int s) {
    // 判断是否要扩容，满足条件之一即可：
    // 1、如果使用的是默认构造器，则会先触发扩容，再添加属性，这也是为什么建议创建集合时要指定集合大小
    // 2、检查数组是否已满，满了则先扩容
    if (s == elementData.length)
        elementData = grow();
    // 将元素加到数组的最后一个元素
    elementData[s] = e;
    size = s + 1;
}

add(int index, E element)

在指定的位置加入元素，原先位置的元素整体往后移一位。

public void add(int index, E element) {
    // 检测index是否合法，index必须在0~size-1之间
    rangeCheckForAdd(index);
    modCount++;
    final int s;
    Object[] elementData;
    // 还是检测是否先扩容，数组为空或数组已满时触发扩容
    if ((s = size) == (elementData = this.elementData).length)
        elementData = grow();
    // 复制数组内容
    System.arraycopy(elementData, index, elementData, index + 1, s - index);
    elementData[index] = element;
    size = s + 1;
}

这里面需要注意的是System.arraycopy()方法，它是一个native修饰的方法，意味着我们看不到它具体实现细节，这里只做简单介绍。

 
 /**
 * @param      src      原始数组
 * @param      srcPos   从原始数组的什么地方(srcPos)开始复制
 * @param      dest     复制到哪个数组中去(目标数组).
 * @param      destPos  被复制到元素，从目标数组的哪个位置开始添加到目标数组中.
 * @param      length   总共复制多少个元素.
 */
@IntrinsicCandidate
public static native void arraycopy(Object src,  int  srcPos,
                                    Object dest, int destPos,
                                    int length);

addAll(Collection<? extends E> c)

将指定集合c的所有元素添加到当前集合的尾部。这里的c是Collection类型，意味着c可是任何实现了Collection接口的类，比如HashSet，LinkedList等等。

public boolean addAll(Collection<? extends E> c) {
    Object[] a = c.toArray();
    // 即使是一次性添加多个，modCount也是加1
    modCount++;
    int numNew = a.length;
    if (numNew == 0)
        return false;
    Object[] elementData;
    final int s;
    // 如果当前数组的剩余元素小于c中的元素数量，则触发扩容
    if (numNew > (elementData = this.elementData).length - (s = size))
        elementData = grow(s + numNew);
    // 还是通过复制的方式添加元素，这里表示着从数组a的第0个位置开始复制numNew个元素，并从elementData的s位置开始依次加到尾部
    System.arraycopy(a, 0, elementData, s, numNew);
    size = s + numNew;
    return true;
}

设置数据

将指定位置的元素替换为element，并返回旧值。

public E set(int index, E element) {
    // 检查index是否合法，index必须在0~size-1之间
    Objects.checkIndex(index, size);
    // 获取原位置的值
    E oldValue = elementData(index);
    elementData[index] = element;
    return oldValue;
}

E elementData(int index) {
    return (E) elementData[index];
}

获取数据

public E get(int index) {
    // 校验index的合法性
    Objects.checkIndex(index, size);
    return elementData(index);
}

E elementData(int index) {
    // 根据索引返回数组指定位置的数据，时间复杂度为O(1)
    return (E) elementData[index];
}

删除数据

remove(int index)

删除指定位置的数据，并返回被删除的数据。

public E remove(int index) {
    Objects.checkIndex(index, size);
    final Object[] es = elementData;

    @SuppressWarnings("unchecked") E oldValue = (E) es[index];
    fastRemove(es, index);

    return oldValue;
}

private void fastRemove(Object[] es, int i) {
    modCount++;
    final int newSize;
    // 如果i不是最后位置的下标，则将i后面的元素复制过来
    if ((newSize = size - 1) > i)
        System.arraycopy(es, i + 1, es, i, newSize - i);
    // 删除最后一个元素
    es[size = newSize] = null;
}

remove(Object o)

删除集合中第一个内容等于o的数据，注意不是删除结合中所有等于o的元素哦。

public boolean remove(Object o) {
    final Object[] es = elementData;
    final int size = this.size;
    int i = 0;
    // 计算删除元素的索引
    found: {
        if (o == null) {
            for (; i < size; i++)
                if (es[i] == null)
                    break found;
        } else {
            for (; i < size; i++)
                if (o.equals(es[i]))
                    break found;
        }
        return false;
    }
    // 根据索引快速删除它
    fastRemove(es, i);
    return true;
}

removeAll(Collection<?> c)

删除当前集合中每个与c中内容相等的数据。

1
2
3

public boolean removeAll(Collection<?> c) {
    return batchRemove(c, false, 0, size);
}

retainAll(Collection<?> c)

删除当前集合中每个与c中内容相不等的数据。

1
2
3

public boolean retainAll(Collection<?> c) {
    return batchRemove(c, true, 0, size);
}

可以看到removeAll与retainAll方法都是调用的batchRemove方法，区别知识第二个参数不同，我们看下这个方法

boolean batchRemove(Collection<?> c, boolean complement,
                    final int from, final int end) {
    Objects.requireNonNull(c);
    final Object[] es = elementData;
    int r; // 第一个符合条件的元素的位置
    // 快速检查是否有满足条件的数据存在，如果没有就直接返回false
    for (r = from;; r++) {
        if (r == end)
            return false;
        if (c.contains(es[r]) != complement)
            break;
    }
    // w表示不符合条件的数据存放的位置
    int w = r++;
    try {
        for (Object e; r < end; r++)
            if (c.contains(e = es[r]) == complement)
                // retainAll时将不符合条件的数据记录下来
                es[w++] = e;
    } catch (Throwable ex) {
        // 如果出现了异常，需要将数组还原回来
        System.arraycopy(es, r, es, w, end - r);
        w += end - r;
        throw ex;
    } finally {
        modCount += end - w;
        shiftTailOverGap(es, w, end);
    }
    return true;
}

扩容机制

我们知道ArrayList中数据是存放在一个数组中的，当数组已满并且需要继续往面来添加数据时，就需要先对数组进行扩容，以存放更多的数据。

有两个方法能触发自动扩容，分别是add()、addAll()、他们在添加数据时都会检查是否触发扩容，还有一个手动扩容的方式，即主动调用ensureCapacity() 方法。这三种方式的底层都是调用grow()方法来实现的。

private Object[] grow(int minCapacity) {
    int oldCapacity = elementData.length;
    if (oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        // 如果是数组已满触发的扩容，会由这个算法计算出扩容后的值。
        int newCapacity = ArraysSupport.newLength(oldCapacity,
                minCapacity - oldCapacity, /* minimum growth */
                oldCapacity >> 1           /* preferred growth */);
        // 计算完新的容量后，将原先数组中的数据复制到新的数组中去
        return elementData = Arrays.copyOf(elementData, newCapacity);
    } else {
        // 如果是空数组触发的扩容，直接用初始容量完成数组的初始化，初始容量为10
        return elementData = new Object[Math.max(DEFAULT_CAPACITY, minCapacity)];
    }
}

// 这个方法用来计算新容量值
// 比如正常add(E e)触发的扩容 oldLength = 10, minGrowth = 1， prefGrowth = 5， 则结果为15
// addAll(Collection<? c> 触发的扩容 oldLength = 10, minGrowth = 19， prefGrowth = 5， 则结果为29
public static int newLength(int oldLength, int minGrowth, int prefGrowth) {
    // preconditions not checked because of inlining
    // assert oldLength >= 0
    // assert minGrowth > 0
	// 10 + 5
    int prefLength = oldLength + Math.max(minGrowth, prefGrowth); // might overflow
    // SOFT_MAX_ARRAY_LENGTH = Integer.MAX_VALUE - 8;
    if (0 < prefLength && prefLength <= SOFT_MAX_ARRAY_LENGTH) {
        return prefLength;
    } else {
        // put code cold in a separate method
        // 这里主要是处理超大值，如果oldLength + minGrowth 超过了Integer.MAX_VALUE, 就会抛出异常
        return hugeLength(oldLength, minGrowth);
    }
}

快速失败机制

ArrayList中的操作都是非现成安全的，这意味着当多个线程对一个集合进行操作时，如果某一个线程通过迭代器（Iterator）在遍历集合的过程中，其他线程修改了集合的长度（增加或删除元素，不包括通过迭代器自身的方法修改集合），那么这个正在遍历的迭代器会立即抛出ConcurrentModificationException异常，这就是所谓的快速失败。

在ArrayList中，快速失败的实现主要依赖于一个叫做modCount的字段，这个字段用来记录ArrayList结构性修改的次数。结构性修改是指改变ArrayList大小，或者打乱ArrayList元素的顺序的操作。每当进行一次结构性修改，modCount就会增加1。当获取ArrayList的迭代器并开始遍历时，会将当前的modCount值记录到迭代器的expectedModCount字段中。在每次迭代获取元素的过程中，都会检查modCount和expectedModCount是否相等，如果不相等，就会立即抛出ConcurrentModificationException。

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