Java8 ArrayList<E>源码解读

2016-05-01 12 分钟读完 (大约 1816 个字)

ArrayList<E>是能够自动扩容版本的数组实现，它继承了AbstractList<E>抽象类，实现了List<E>, RandomAccess, Cloneable, Serializable等几个接口：

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

ArrayList<E>初探

ArrayList<E>内部以一个Object数组存储元素，以一个整型size成员记录元素的个数：

private static final int DEFAULT_CAPACITY = 10;
private static final Object[] EMPTY_ELEMENTDATA = {};
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
transient Object[] elementData;  //transient表名了elementData不参与序列化
private int size;
protected transient int modCount = 0;   // 从AbstractList<E>继承

其有三个构造函数：

无参构造函数：
1
2
3
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
- 初始化的是一个空对象数组，其实际数组长度此时为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);
    }
}

initialCapacity大于0时，初始化的是一个参数指定容量长度的对象数组

从另一个集合对象构造ArrayList<E>

public ArrayList(Collection<? extends E> c) {
    elementData = c.toArray();
    if ((size = elementData.length) != 0) {
        // defend against c.toArray (incorrectly) not returning Object[]
        // (see e.g. https://bugs.openjdk.java.net/browse/JDK-6260652)
        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    } else {
        // replace with empty array.
        this.elementData = EMPTY_ELEMENTDATA;
    }
}

从参数集合对象拷贝成对象数组，其长度是原集合对象的长度

modCount从AbstractList<E>继承而来，用来标记ArrayList<E>实例被结构性改变（如元素删除等）的次数，其被用来在迭代器中判断迭代过程中数组是否被做了修改，如果被修改则抛出ConcurrentModificationException。

延迟初始化与扩容

可以看到对于ArrayList<E>的默认构造函数，并没有在对象构造的时候就初始化一定的空间容量，而是延迟到了往里面添加元素或者调用ensureCapacity(int)的时候才去分配容量：

private void add(E e, Object[] elementData, int s) {
    if (s == elementData.length)
        elementData = grow();
    elementData[s] = e;
    size = s + 1;
}

public boolean add(E e) {
    modCount++;
    add(e, elementData, size);
    return true;
}

public void add(int index, E element) {
    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;
}

其中的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 {
        return elementData = new Object[Math.max(DEFAULT_CAPACITY, minCapacity)];
    }
}

private Object[] grow() {
    return grow(size + 1);
}

public void ensureCapacity(int minCapacity) {
    if (minCapacity > elementData.length
        && !(elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
             && minCapacity <= DEFAULT_CAPACITY)) {
        modCount++;
        grow(minCapacity);
    }
}

//-------------------------- 以下来自ArraysSupport --------------------------

public static int newLength(int oldLength, int minGrowth, int prefGrowth) {
    // assert oldLength >= 0
    // assert minGrowth > 0

    int newLength = Math.max(minGrowth, prefGrowth) + oldLength;
    if (newLength - MAX_ARRAY_LENGTH <= 0) {
        return newLength;
    }
    return hugeLength(oldLength, minGrowth);
}

private static int hugeLength(int oldLength, int minGrowth) {
    int minLength = oldLength + minGrowth;
    if (minLength < 0) { // overflow
        throw new OutOfMemoryError("Required array length too large");
    }
    if (minLength <= MAX_ARRAY_LENGTH) {
        return MAX_ARRAY_LENGTH;
    }
    return Integer.MAX_VALUE;
}

首次调用add方法添加元素或初始化后调用ensureCapacity扩容时，走以上代码第9行的逻辑，扩容至少DEFAULT_CAPACITY即10个元素的空间长度；
当原来的数组有值但空间不足或手动调用ensureCapacity扩容时，计算扩容空间的逻辑：

最少扩容空间(minGrowth)为传入参数与已有容量之差(大于0)，建议容量(prefGrowth)为已用用量的一半，MAX_ARRAY_LENGTH为整型最大值减8（减8的原因是某些VM在数组中保留一些头部信息）
- 在扩容后的长度小于MAX_ARRAY_LENGTH的情况下，取最小扩容容量和建议容量值之间的最大者；也就是说单次扩容容量起码是已分配空间的一半
- 当扩容后的长度大于MAX_ARRAY_LENGTH时，可能是由于增长了prefGrowth导致的，则改为按minGrowth重新计算扩容后的长度：
  - 如果扩容后的长度已经整型溢出，则抛异常
  - 如果扩容后的长度小于等于MAX_ARRAY_LENGTH，则返回MAX_ARRAY_LENGTH
  - 否则返回Integer.MAX_VALUE

batchRemove分析

removeAll和retainAll都使用了batchRemove方法来处理，其代码如下：

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

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

boolean batchRemove(Collection<?> c, boolean complement,
                    final int from, final int end) {
    Objects.requireNonNull(c);
    final Object[] es = elementData;
    int r;
    // Optimize for initial run of survivors
    for (r = from;; r++) {
        if (r == end)
            return false;
        if (c.contains(es[r]) != complement)
            break;
    }
    int w = r++;
    try {
        for (Object e; r < end; r++)
            if (c.contains(e = es[r]) == complement)
                es[w++] = e;
    } catch (Throwable ex) {
        // Preserve behavioral compatibility with AbstractCollection,
        // even if c.contains() throws.
        System.arraycopy(es, r, es, w, end - r);
        w += end - r;
        throw ex;
    } finally {
        modCount += end - w;
        shiftTailOverGap(es, w, end);
    }
    return true;
}

private void shiftTailOverGap(Object[] es, int lo, int hi) {
    System.arraycopy(es, hi, es, lo, size - hi);
    for (int to = size, i = (size -= hi - lo); i < to; i++)
        es[i] = null;
}

complement是补数、补充、辅助的意思，其为true时计算的是与集合c的并集，其为false时计算的是与集合c的差集，这里使用了双指针的技巧来计算差集并集：

第13行定义一个下标指针r（可理解为read），接下来初始化为参数的from即数组第一个元素下标，它将负责从头到尾遍历对象数组；
第15~20行，找到第一个不在c（求并集）或第一个在c（求差集）中出现的元素记录其下标到w，如果指针r最终指向了数组末尾，则说明c是数组的子集（求并集）或c与数组不存在交集，直接返回false；
第21~25行，继续指针r遍历对象数组的剩余部分，对于不在c（求并集）或在c（求差集）中出现的元素将其拷贝到w指向的位置然后将w往右移动一个元素，直到剩余元素遍历完成；
第26~31行，兼容处理c.contains可能抛出异常的情况；
第33~34行，修改本ArrayList实例的modCount，并且置空w往后的元素空间为null

简单总结

ArrayList<E>没有加锁同步，它不是线程安全的；
使用默认构造函数新建一个ArrayList<E>对象在未使用之前它是空的，直到调用ensureCapacity或者add方法时才去扩容数组空间，至少为10个元素容量大小；
已分配过空间再进行扩容的机制：尝试扩容为已有容量的1.5倍，如果扩容超出整型最大值的情况下（可能是按已有容量一半进行扩容的）重新判断，尝试按最小扩容量进行扩容，如果还是超出整型最大值则抛异常，否则如果没超出MAX_ARRAY_LENGTH则返回MAX_ARRAY_LENGTH，否则返回整型最大值;
如果可预见后续会使用比较大的空间，则可以先调用ensureCapacity做一次分配，以减少自动频繁扩容带来的开销；
求与另一个集合的差集、并集时采用了双指针的技巧。