Java 抽象容器类源码剖析

总体介绍

抽象容器类接口和具体容器类的关系如图所示，顶层包括Collection、List、Set、Queue、Deque和Map6个抽象容器类。

AbstractCollection：实现了Collection接口，被抽象类AbstractList、AbstractSet、AbstractQueue继承，ArrayDeque也继承自AbstractCollection。

AbstractList：父类是AbstractCollection，实现了List接口，被ArrayList、Abstract-SequentialList继承。

AbstractSequentialList：父类是AbstractList，被LinkedList继承。

AbstractMap：实现了Map接口，被TreeMap、HashMap、EnumMap继承。

AbstractSet：父类是AbstractCollection，实现了Set接口，被HashSet、 TreeSet和EnumSet继承。

AbstractQueue：父类是AbstractCollection，实现了Queue接口，被PriorityQueue继承。

本文分别介绍这些抽象类，包括它们提供的基础功能、如何实现、如何进行扩展等。

以AbstractCollection为例

AbstractCollection提供了Collection接口的基础实现，它实现了如下方法：

public boolean addAll(Collection c)
public boolean contains(Object o)
public boolean containsAll(Collection c)
public boolean isEmpty()
public boolean remove(Object o)
public boolean removeAll(Collection c)
public boolean retainAll(Collection c)
public void clear()
public Object[] toArray()
public  T[] toArray(T[] a)
public String toString()

由于AbstractCollection不知道数据是怎么存储的，它依赖于如下更为基础的方法：

public boolean add(E e)
public abstract int size();
public abstract Iterator iterator();

add方法的默认实现是：

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

代码抛出“操作不支持”异常，如果子类集合是不可被修改的，这个默认实现就可以了，否则，必须重写add方法。addAll方法的实现就是循环调用add方法。
size方法是抽象方法，子类必须重写。isEmpty方法就是检查size方法的返回值是否为0。toArray方法依赖size方法的返回值分配数组大小。
iterator方法也是抽象方法，它返回一个实现了迭代器接口的对象，子类必须重写。迭代器
定义了三个方法：

boolean hasNext();
E next();
void remove();

如果子类集合是不可被修改的，选代器不用实现remove方法，否则，三个方法都必须实现。

除了接口中的方法，Collection接口文档建议，每个Collection接口的实现类都应该提供至少两个标准的构造方法，一个是默认构造方法，另一个接受一个Collection类型的参数。

具体如何通过继承AbstractCollection来实现自定义容器呢？下面通过一个简单的例子来说明。我们使用自己实现的动态数组容器类DynamicArray来实现一个简单的Collection。

public class DynamicArray {
       //...
       public E remove(int index) {
           E oldValue = get(index);
           int numMoved = size - index - 1;
           if(numMoved > 0)
               System.arraycopy(elementData, index + 1, elementData, index,
                       numMoved);
           elementData[--size] = null;
           return oldValue;
       }
       public void add(int index, E element) {
           ensureCapacity(size + 1);
           System.arraycopy(elementData, index, elementData, index + 1,
                            size - index);
           elementData[index] = element;
           size++;
       }
}

基于DynamicArray，再实现一个简单的迭代器类DynamicArrayIterator

public class DynamicArrayIterator  implements Iterator{
       DynamicArray darr;
       int cursor;
       int lastRet = -1;
       public DynamicArrayIterator(DynamicArray darr){
           this.darr = darr;
        }
    @Override
    public boolean hasNext() {
     return cursor != darr.size();
    }
    @Override
    public E next() {
        int i = cursor;
        if(i >= darr.size())
            throw new NoSuchElementException();
        cursor = i + 1;
    lastRet = i;
        return darr.get(i);
    }
    @Override
    public void remove() {
    if(lastRet < 0)
        throw new IllegalStateException();
    darr.remove(lastRet);
    cursor = lastRet;
    lastRet = -1;
}

基于DynamicArray和DynamicArrayIterator，通过继承AbstractCollection，我们来实现一个简单的容器类MyCollection。MyCollection提供了两个构造方法，并重写了size、add和iterator方法，这些方法内部使用了DynamicArray和DynamicArrayIterator。

public class MyCollection extends AbstractCollection {
       DynamicArray darr;
       public MyCollection(){
           darr = new DynamicArray<>();
       }
       public MyCollection(Collection c){
           this();
addAll(c); }
       @Override
       public Iterator iterator() {
           return new DynamicArrayIterator<>(darr);
       }
       @Override
       public int size() {
           return darr.size();
       }
       @Override
       public boolean add(E e) {
           darr.add(e);
           return true;
       }
}