AbstractCollection 源码选读

这次分析AbstractCollection的源码，选一些有意思的地方讨论。

文章目录

toArray()
数组增长策略
toArray(T[] a)
removeAll 和 retainAll 方法
clear 方法
toString()

toArray()

首先是toArray()方法，这个方法做的是将当前 collection 中的所有元素放到一个 Object 数组中返回，源码是：

public Object[] toArray() {
    // Estimate size of array; be prepared to see more or fewer elements
    Object[] r = new Object[size()];
    Iterator<E> it = iterator();
    for (int i = 0; i < r.length; i++) {
        if (! it.hasNext()) // fewer elements than expected
            return Arrays.copyOf(r, i);
        r[i] = it.next();
    }
    return it.hasNext() ? finishToArray(r, it) : r;
}

有意思的地方在于，iterator 中存储的元素个数是会变化的（concurrent 操作），所以一开始根据 size 大小申请了 Object 数组，会有两种情况：

实际元素个数比 size 小，这时直接把当前数组复制成一个大小刚好的数组返回就可以，如上代码第6，7行所示。
实际元素个数比size大，这时调用一个finishToArray(T[] r, Iterator<?> it)方法，将数组扩充后返回。

数组增长策略

那么finishToArray(T[] r, Iterator<?> it)这个方法的扩充策略是怎么样的呢，看看源码：

private static <T> T[] finishToArray(T[] r, Iterator<?> it) {
    int i = r.length;
    while (it.hasNext()) {
        int cap = r.length;
        if (i == cap) {
            int newCap = cap + (cap >> 1) + 1;
            // overflow-conscious code
            if (newCap - MAX_ARRAY_SIZE > 0)
                newCap = hugeCapacity(cap + 1);
            r = Arrays.copyOf(r, newCap);
        }
        r[i++] = (T)it.next();
    }
    // trim if overallocated
    return (i == r.length) ? r : Arrays.copyOf(r, i);
}

private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError
                ("Required array size too large");
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }

首先有一个定义int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;将数组最大长度定义为int最大值 - 8，对于 - 8，文档说的理由是给某些 VM 在数组里预留一些 header words 的空间。

每次当 Object 数组空间不够时就会增长int newCap = cap + (cap >> 1) + 1;，而当要申请的新空间超过MAX_ARRAY_SIZE，会先把newCap直接定为MAX_ARRAY_SIZE，再次不够时就 +1，直到超过 int 最大值，就会抛出异常。如下表所示：

	增长方式
cap + (cap >> 1) + 1 < MAX_ARRAY_SIZE	newCap = cap + (cap >> 1) + 1
cap + (cap >> 1) + 1 > MAX_ARRAY_SIZE && cap < MAX_ARRAY_SIZE	newCap = MAX_ARRAY_SIZE
MAX_ARRAY_SIZE <= cap <= Integer.MAX_VALUE	newCap = cap + 1
cap > Integer.MAX_VALUE	OutOfMemoryError

toArray(T[] a)

这个方法做的东西跟toArray()基本上是一致的，不同点在于这里有个参数 a 数组，当a数组的大小能够容纳 iterator 中的全部元素时，必须将元素放到 a 数组返回。源码如下：

public <T> T[] toArray(T[] a) {
    // Estimate size of array; be prepared to see more or fewer elements
    int size = size();
    T[] r = a.length >= size ? a :
              (T[])java.lang.reflect.Array
              .newInstance(a.getClass().getComponentType(), size);
    Iterator<E> it = iterator();

    for (int i = 0; i < r.length; i++) {
        if (! it.hasNext()) { // fewer elements than expected
            if (a == r) {
                r[i] = null; // null-terminate
            } else if (a.length < i) {
                return Arrays.copyOf(r, i);
            } else {
                System.arraycopy(r, 0, a, 0, i);
                if (a.length > i) {
                    a[i] = null;
                }
            }
            return a;
        }
        r[i] = (T)it.next();
    }
    // more elements than expected
    return it.hasNext() ? finishToArray(r, it) : r;
}

这个需求，我的思路是直接创建新的数组，按照toArray()方法的思路填充元素，然后跟 a 数组大小对比，合适的话就复制到 a 数组然后返回，否则直接返回新数组。

这样做的问题在于：对于 a 数组大小足够大的情况，每次都要新建数组和复制数组。

所以源码中做了优化，如果 a 数组足够大就直接用 a 数组填充元素，不需要再新建一个数组和节省复制时间。有以下几种情况（size 表示刚开始时 iterator 中元素的个数）：

当 iterator 中最后的元素个数比 size 大，则逻辑跟toArray()方法是一样的（相当于这段代码 for 循环中的 if 是不会进去的）

1.1 如果 a 数组足够大，那就以 a 数组返回

1.2 否则就新建数组返回
当 iterator 中元素个数比 size 小

2.1 a 数组的长度比 size 大，会将元素填充到 a 数组，然后在后面填一个 null，返回 a 数组（上面代码第 11 行）

2.2 a 数组的长度比元素总数小，将当前填充好的新建数组返回（上面代码第 13 行）

2.3 a 数组的长度比 size 小，但比元素总数大，将当前填充好的新建数组复制到 a 数组，如果 a 数组还有位置，在后面加一个 null，返回 a 数组（上面代码 16 行）

可以看到优化的代价就是增加了代码的复杂度，需要增加一些条件判断。

removeAll 和 retainAll 方法

public boolean removeAll(Collection<?> c) {
    Objects.requireNonNull(c);
    boolean modified = false;
    Iterator<?> it = iterator();
    while (it.hasNext()) {
        if (c.contains(it.next())) {
            it.remove();
            modified = true;
        }
    }
    return modified;
}

public boolean retainAll(Collection<?> c) {
        Objects.requireNonNull(c);
        boolean modified = false;
        Iterator<E> it = iterator();
        while (it.hasNext()) {
            if (!c.contains(it.next())) {
                it.remove();
                modified = true;
            }
        }
        return modified;
    }

这两个方法的难度不大，这里想说的是这两个方法的代码重复率是很高的，除了判断条件一行其他都是一样的，所以我们平时对于一些短小方法代码是不是一定要追求零重复，要不要考虑解耦呢，都是值得斟酌的。

clear 方法

public void clear() {
    Iterator<E> it = iterator();
    while (it.hasNext()) {
        it.next();
        it.remove();
    }
}

clear 方法也不难，但要注意时间复杂度是 O(n)，大部分情况下直接 new 一个新的可以减少这个 O(n) 的遍历：

List<String> exampleList = new LinkedList<>();
...
exampleList.clear(); // O(n)
exampleList = new LinkedList<>(); // O(1)

toString()

public String toString() {
    Iterator<E> it = iterator();
    if (! it.hasNext())
        return "[]";

    StringBuilder sb = new StringBuilder();
    sb.append('[');
    for (;;) {
        E e = it.next();
        sb.append(e == this ? "(this Collection)" : e);
        if (! it.hasNext())
            return sb.append(']').toString();
        sb.append(',').append(' ');
    }
}

最后 toString 方法也不难，需要注意的是 collection 本身（this）也作为其元素的情况，为了避免无限递归，代码中是做了判断的（上面代码第 10 行）

这次选读就到这里，有不对或者讲得不清楚的地方欢迎大家提出。