转载

AbstractCollection 源码选读

首先是 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 数组,会有两种情况:

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 中元素的个数):

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

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

    1.2 否则就新建数组返回

  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 行)

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

原文  https://juejin.im/post/5f00703b6fb9a07e926cd7cf
正文到此结束
Loading...