Java容器类研究3：AbstractCollection

摘要：随机访问数据是相对于顺序访问数据而言，例如链表的形式。方法将容器中的元素转化为数组的形式。在函数中，对容量每次扩展的大小，并且会检查是否会超过设定的最大数组长度。如果长度超过了限定值，则以原容量为底线，返回一个最大容量。

ArrayList继承自AbstractList，AbstractList为“random access”的数组提供了基本的实现。随机访问数据是相对于顺序访问数据而言，例如链表的形式。AbstractSequentialList为链表形式的顺序访问提供了基本实现。AbstractList提供了默认的随机访问数据的iterator。AbstractList继承自AbstractCollection，AbstractCollection为Collection提供了基本实现。

java.util.AbstractCollection

AbstractCollection实现了查询是否包含某一个元素的方法。最好使用Iterator遍历集合中的元素，因为可以屏蔽集合内部元素存储的具体实现，并且根据不同的数据存储特点，优化访问策略。这里还可以正确查找null元素，需要注意的是对null元素的查询需要特别的处理，有时候自己实现方法时，往往会忽略传入参数为null时的处理，导致方法无法处理特殊情况。

    public boolean contains(Object o) {
        Iterator it = iterator();
        if (o==null) {
            while (it.hasNext())
                if (it.next()==null)
                    return true;
        } else {
            while (it.hasNext())
                if (o.equals(it.next()))
                    return true;
        }
        return false;
    }

toArray方法将容器中的元素转化为数组的形式。这里元素的复制，采用的是直接复制引用。这里还考虑到了并发运算时，元素数量在复制时产生变化的情况，当数量减少时，就用Arrays.copy()截取结果。当数量增加时，会调用finishToArray函数扩容。

    public Object[] toArray() {
        // Estimate size of array; be prepared to see more or fewer elements
        Object[] r = new Object[size()];
        Iterator 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;
    }

在finishToArray函数中，对容量每次扩展1/2+1的大小，并且会检查是否会超过设定的最大数组长度MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8。如果长度超过了限定值，则以原容量+1为底线，返回一个最大容量。最后返回的数组也会修剪掉多余的位置。

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

这里有一个toArray的重载，需要传入一个数组作为参数，据我观察，目的是将集合中的元素存入指定的数组，重利用已有数组的存储。如果元素过多，而目标数组容纳不下，只能重新申请数组来进行存储。

    public  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 it = iterator();

        for (int i = 0; i < r.length; i++) {
            if (! it.hasNext()) { // fewer elements than expected
                if (a == r) {
                    //利用的原数组，且元素不足，则补null表示结束
                    r[i] = null; // null-terminate
                } else if (a.length < i) {
                    //元素较少，但数量超过原始数组，只能用新数组
                    return Arrays.copyOf(r, i);
                } else {
                    //元素减少，导致原始数组可以容纳下，则copy回原始数组，折腾呗
                    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;
    }

removeAll方法删除目标集合中的所有重叠元素。Iterator可以做到在遍历时，安全的删除元素，而通过index循环删除则可能导致index偏移。

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

AbstractCollection的toString实现，比较令我震惊的是e == this的作用。这里为什么要判断打印的内容是否为自己本身？因为sb.append(e == this ? "(this Collection)" : e);会调用e的toString函数来生成字符串，若不加判断，则会形成无限的toString递归调用。我猜想一下，估计当时toString的实现者没有注意到该问题的存在，直到该bug出现，脑洞不大还真难想起来这个问题。

    public String toString() {
        Iterator 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(" ");
        }
    }