java.util.AbstractCollection源码解析

源码摘自jdk1.6，水平有限，难免有错，欢迎大家指出，仅当笔记留存。

---

AbstractCollection类直接实现Collection接口，他作为集合的顶级父类，为下面的集合类例如AbstractList、AbstractSet等实现了许多基本方法。

AbstractCollection实现了Collection中的一些方法，同时也保留了一些抽象方法供具体类来实现，因此AbstractCollection类是一个抽象类。

AbstractCollection的抽象方法：

public abstract Iterator<E> iterator();
public abstract int size();

AbstractCollection类实现的方法：

1、isEmpty方法

public boolean isEmpty() {
    return (size() == 0);
}

由于size()是抽象方法，因此不同的类会有不同的实现。

2、add方法

public boolean add(E paramE) {
    throw new UnsupportedOperationException();
}

AbstractCollection不允许添加单个元素，如果添加单个元素会报不支持操作异常。

3、allAll方法

public boolean addAll(Collection<? extends E> paramCollection) {
    int i = 0;
    //遍历要添加的集合，对于每个要添加的元素，调用add方法添加到当前集合中
    Iterator localIterator = paramCollection.iterator();
    while (localIterator.hasNext()) {
        if (add(localIterator.next()));
        i = 1;
    }
    return i;
}

4、contains方法

public boolean contains(Object paramObject) {
    //调用本类iterator方法生成迭代器
    Iterator localIterator = iterator();
    //如果入参为null，则使用迭代器判断当前集合是否含有null元素
    if (paramObject == null)
        while (true) {
            if (!(localIterator.hasNext()))
                break label53;
            if (localIterator.next() == null)
                return true;
        }
    //集合非空，使用equals比较迭代器和入参是否相同，这里paramObject需要重写equals方法。
    while (localIterator.hasNext()) {
        if (paramObject.equals(localIterator.next()))
            return true;
    }
    label53 : return false;
}

5、containsAll方法

public boolean containsAll(Collection<?> paramCollection) {
    //调用入参paramCollection集合的iterator得到入参集合的迭代器
    Iterator localIterator = paramCollection.iterator();
    //遍历入参集合所有元素，调用本集合contains方法（遍历本集合元素，使用equals比较），因此时间复杂度为n^2
    while (localIterator.hasNext())
        if (!(contains(localIterator.next())))
            return false;
    return true;
}

6、remove方法

public boolean remove(Object paramObject) {
    //调用本地迭代器方法
    Iterator localIterator = iterator();
    //如果要删除的参数为空，则判断当前集合中是否包含null
    if (paramObject == null) {
        do
            if (!(localIterator.hasNext()))//如果本集合没有元素，直接返回false
                break label65;
        while (localIterator.next() != null);
        localIterator.remove();//删除第一个为null的元素
        return true;
    }
    //入参即要删除的元素不为空
    do
        if (!(localIterator.hasNext()))//如果当前集合为空，返回false
            break label65;
    //如果当前集合元素与删除元素不等，则一直遍历，直到找到相等元素并删除，并返回true
    while (!(paramObject.equals(localIterator.next())));
    localIterator.remove();
    return true;

    label65 : return false;
}

7、removeAll方法

public boolean removeAll(Collection<?> paramCollection) {
    int i = 0;
    //与addAll方法逻辑相同，遍历要删除的集合，然后对于每个元素执行删除动作
    Iterator localIterator = iterator();
    while (localIterator.hasNext()) {
        //删除之前要执行一下contains方法，判断是否包含，如果不包含就不需要删除了
        if (paramCollection.contains(localIterator.next()));
        localIterator.remove();
        i = 1;
    }

    return i;
}

8、finishToArray方法
该方法将一个迭代器中的元素合并入一个已知数组并返回合并之后的数组，因此该方法接受两个参数，一个是源数组 T[] paramArrayOfT；另一个是待合并的迭代器Iterator<?> paramIterator；方法返回值T[]，即合并之后的数组。

private static <T> T[] finishToArray(T[] paramArrayOfT,Iterator<?> paramIterator) {
    //保存源paramArrayOfT数组中实际存储元素的个数，每次进入循环，数组实际大小将执行+1操作
    int i = paramArrayOfT.length;
    //遍历需要合并入数组的集合paramIterator
    while (paramIterator.hasNext()) {
        //使用j记录当前数组paramArrayOfT的容量
        int j = paramArrayOfT.length;
        /**
        * i和j相等，说明数组已经满了，需要数组进行扩容操作
        * 扩容的规则是：数组的当前容量 (j/2+1)*3，假设数组当前容量为10，经过运算，数组的容量将扩容为18，容量不到源容量的2倍
        * 扩容之后，判断
        */
        if (i == j) {
            int k = (j / 2 + 1) * 3;
            //这里判断k<=j的用意在于如果j过大，接近int的上边界，那么j在扩大超越int界限会变为负数，即扩容后的k比j要小
            //如果发生这种情况，判断j如果等于int上界，报错，因为数组不能再进行扩容了，否则将新数组的大小指定为int上界-1=2147483647
            if (k <= j) {
                if (j == 2147483647) {
                    throw new OutOfMemoryError(
                            "Required array size too large");
                }
                k = 2147483647;
            }
            //经过以上步骤，已经完成数组的扩容操作，接下来将paramArrayOfT指向扩容并拷贝元素后的新数组
            paramArrayOfT = Arrays.copyOf(paramArrayOfT, k);
        }
        //i和j不等，说明数组还没满，此时直接将迭代器下一个元素插入数组下一个位置即可
        paramArrayOfT[(i++)] = paramIterator.next();
    }
    /*判断数组i和paramArrayOfT.length是否相等，即判断经过扩容后的数组是否满容量：
        如果相等，说明当前数组paramArrayOfT没有空闲位置，直接返回即可
        如果不相等，说明数组paramArrayOfT经过扩容后，有空余位置未填入元素，此时需要返回实际大小的一个新数组。
    */
    return ((i == paramArrayOfT.length) ? paramArrayOfT : Arrays.copyOf(
            paramArrayOfT, i));
}

思考：该方法是一个私有方法，目的是处理toArray方法的再多线程情况下的操作，具体请看9和10。

9、toArray方法

public Object[] toArray() {
    //新建一个size容量的Object数组
    Object[] arrayOfObject = new Object[size()];
    //调用本地迭代器并遍历，将结合中每一个元素放入数组
    Iterator localIterator = iterator();
    for (int i = 0; i < arrayOfObject.length; ++i) {
        //如果迭代器到达结尾，返回实际元素容量的数组拷贝
        if (!(localIterator.hasNext()))
            return Arrays.copyOf(arrayOfObject, i);
        arrayOfObject[i] = localIterator.next();
    }
    //如果执行上述代码迭代器还有元素，调用finishToArray将迭代器中元素合并入数组并返回
    //否则直接返回arrayOfObject数组
    return ((localIterator.hasNext()) ? finishToArray(arrayOfObject,
            localIterator) : arrayOfObject);
}

为什么执行到最后还需要判断迭代器是都还存在元素呢，上面不是基于size()函数创建了数组了么，我们知道一旦迭代器创建，再添加元素是不允许的，会报java.util.ConcurrentModificationException。但是假设线程A执行完第一行，此时线程A已经创建了size元素大小的数组，在调用iterator方法之前，线程B向当前集合新添加了元素，线程A继续执行创建迭代器，此时数组是添加元素之前的集合大小，迭代器确是添加元素之后的迭代器，那么集合的实际大小已经扩大了，线程A创建的数组长度显然比实际元素少，此时就需要调用方法8-finishToArray再次执行拷贝，AbstractCollection不是线程安全的，但是多线程操作时，toArray不会产生问题。

10、toArray重载方法：该方法接受一个已知数组paramArrayOfT，将集合中所有元素填入这个数组并返回，如果paramArrayOfT中有元素，集合中的元素会从前向后覆盖，如果数组中还存在之前数组，那返回的数组就是两部分数组，从0到size-1存放的是集合中的数据，size到paramArrayOfT.length-1存储的是paramArrayOfT故有数据，容易造成数据混乱，因此不建议入参paramArrayOfT中存入数据，一般传入空数组。

public <T> T[] toArray(T[] paramArrayOfT) {
    //集合中的元素个数
    int i = size();
    /**
    * 如果入参paramArrayOfT大小比集合元素个数小，新建一个数组实例，大小为集合大小
    * 元素类型与paramArrayOfT相同。
    */
    Object[] arrayOfObject = (paramArrayOfT.length >= i)
            ? paramArrayOfT
            : (Object[]) (Object[]) Array.newInstance(paramArrayOfT
                    .getClass().getComponentType(), i);
    //调用迭代器方法准备遍历添加
    Iterator localIterator = iterator();

    for (int j = 0; j < arrayOfObject.length; ++j) {
        //如果迭代器没有多余元素，返回实际元素数量的数组拷贝
        if (!(localIterator.hasNext())) {
            if (paramArrayOfT != arrayOfObject)
                return Arrays.copyOf(arrayOfObject, j);
            arrayOfObject[j] = null;
            return arrayOfObject;
        }
        //否则直接将迭代器下一个元素装进数组
        arrayOfObject[j] = localIterator.next();
    }
    //这里还是多线程的问题，会造成size装满了，但是迭代器中还有元素，需要调用finishToArray进行处理
    return ((localIterator.hasNext()) ? finishToArray(arrayOfObject,
            localIterator) : arrayOfObject);
}

11、retainAll方法：该方法用于保留入参paramCollection中不存在的元素。

public boolean retainAll(Collection<?> paramCollection) {
    int i = 0;
    //调用集合迭代器，并遍历
    Iterator localIterator = iterator();
    while (localIterator.hasNext()) {
        //如果paramCollection中包含当前元素，就删除，最后剩下的就是要保留的所有元素
        if (!(paramCollection.contains(localIterator.next())));
        localIterator.remove();
        i = 1;
    }

    return i;
}

12、clear方法：用于清空当前集合

public void clear() {
    //调用迭代器并遍历，挨个删除
    Iterator localIterator = iterator();
    while (localIterator.hasNext()) {
        localIterator.next();
        localIterator.remove();
    }
}

13、toString方法

public String toString() {
    //调用iterator方法，准备遍历。
    Iterator localIterator = iterator();
    //如果迭代器没有元素，说明集合为空，返回"[]"
    if (!(localIterator.hasNext())) {
        return "[]";
    }
    StringBuilder localStringBuilder = new StringBuilder();
    localStringBuilder.append('[');
    //将集合中所有元素拼接，返回[1,2,3]诸如这种形式的字符串
    while (true) {
        Object localObject = localIterator.next();
        localStringBuilder.append((localObject == this)
                ? "(this Collection)"
                : localObject);
        if (!(localIterator.hasNext()))
            return ']';
        localStringBuilder.append(", ");
    }
}

此处注意需要集合中元素类实现toString方法，否则返回的字符串中将是各元素地址拼成的字符串，我们可以执行如下方法：

List<Integer> list = new ArrayList<Integer>();
    list.add(1);
    list.add(2);
    list.add(3);
    System.out.println(list);
运行结果：
[1, 2, 3]

我们可以直接打印list、set，系统可以正确打印元素都是因为AbstractCollection类的toString方法的功劳。