java集合框架（二） Collection架构与源码分析

Collection是一个接口，它主要的两个分支是List和Set。

List和Set都是接口，它继承于Collection。
List是有序队列，可以用重复的元素；
Set元素无序，并且不可重复；
List和Set都有他们各自的实现类

为了方便，我们抽象出AbstractCollection类来让其他类继承，该类实现类Collection中的绝大部分方法。AbstractList和AbstractSet都继承与AbstractCollection，具体的List实现类继承与AbstractList，而Set的实现类则继承与AbstractSet。

另外，Collection中有个iterator()方法，它的作用是返回一个Iterator接口。通常，我们通过Iterator迭代器来遍历集合。ListIterator是List接口所特有的，在List接口中，通过ListIterator()返回一个ListIterator对象。
我们首先来阅读下这些 接口和抽象类以及他们的实现类中都有哪些方法：

1、Collection
Collection的定义如下：
public interface Collection extends Iterable{}
从他的定义中可以看出，Collection是一个接口，他是高度抽象出来的集合，包含了集合的基本操作：添加、删除、清空、遍历、是否为空，获取大小等。
booleanadd(E o)
确保此 collection 包含指定的元素（可选操作）。booleanaddAll(Collection

下面看一下AbstractCollection实现的部分方法的源码：

public abstract class AbstractCollection implements Collection {
protected AbstractCollection() {
}

public abstract Iterator<E> iterator();//iterator()方法没有实现  

public abstract int size(); //size()方法也没有实现  

public boolean isEmpty() { //检测集合是否为空  
    return size() == 0;  
}  
/*检查集合中是否包含特定对象*/  
public boolean contains(Object o) {   
    Iterator<E> it = iterator();  
    if (o==null) {  
        while (it.hasNext()) //从这里可以看出，任何非空集合都包含null  
            if (it.next()==null)  
                return true;  
    } else {  
        while (it.hasNext())  
            if (o.equals(it.next()))  
                return true;  
    }  
    return false;  
}  
/*将集合转变成数组*/  
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  
            //Arrays.copy(**,**)的第二个参数是待copy的长度，如果这个长度大于r，则保留r的长度  
            return Arrays.copyOf(r, i);  
        r[i] = it.next();  
    }  
    return it.hasNext() ? finishToArray(r, it) : r;  
}  

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

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

// 删除对象o  
public boolean remove(Object o) {  
    Iterator<E> it = iterator();  
    if (o==null) {  
        while (it.hasNext()) {  
            if (it.next()==null) {  
                it.remove();  
                return true;  
            }  
        }  
    } else {  
        while (it.hasNext()) {  
            if (o.equals(it.next())) {  
                it.remove();  
                return true;  
            }  
        }  
    }  
    return false;  
}  

    // 判断是否包含集合c中所有元素 
    public boolean containsAll(Collection