12.0 第12章通用容器类和总结 12.1 抽象容器类

发表于 2021-12-05 更新于 2021-12-08 分类于 9 Java编程的逻辑， 3第三部分泛型与容器，第12章通用容器类和总结 Waline：本文字数： 13k 阅读时长 ≈ 12 分钟

第12章通用容器类和总结

之前的章节中，我们介绍的都是具体的容器类，本章介绍一些抽象容器类、一些通用的算法和功能，并对整个容器类体系进行梳理总结。

之前介绍的具体容器类其实都不是从头构建的，它们都继承了一些抽象容器类。这些抽象类提供了容器接口的部分实现，方便了Java具体容器类的实现。此外，通过继承抽象类，自定义的类也可以更为容易地实现容器接口。为什么需要实现容器接口呢？至少有两个原因。
1）容器类是一个大家庭，它们之间可以方便地协作，比如很多方法的参数和返回值都是容器接口对象，实现了容器接口，就可以方便地参与这种协作。
2）Java有一个类Collections，提供了很多针对容器接口的通用算法和功能，实现了容器接口，可以直接利用Collections中的算法和功能。

本章首先介绍抽象容器类，然后介绍Collections中的通用功能，最后对整个容器类体系进行梳理总结。

12.1 抽象容器类

抽象容器类与之前介绍的接口和具体容器类的关系如图12-1所示。

虚线框表示接口，有Collection、List、Set、Queue、Deque和Map。有6个抽象容器类。
1）AbstractCollection：实现了Collection接口，被抽象类AbstractList、AbstractSet、AbstractQueue继承，ArrayDeque也继承自AbstractCollection（图中未画出）。
2）AbstractList：父类是AbstractCollection，实现了List接口，被ArrayList、Abstract-SequentialList继承。

epub_923038_110

图12-1 容器类体系与抽象容器类

3）AbstractSequentialList：父类是AbstractList，被LinkedList继承。
4）AbstractMap：实现了Map接口，被TreeMap、HashMap、EnumMap继承。
5）AbstractSet：父类是AbstractCollection，实现了Set接口，被HashSet、TreeSet和EnumSet继承。
6）AbstractQueue：父类是AbstractCollection，实现了Queue接口，被PriorityQueue继承。

下面，我们分别来介绍这些抽象类，包括它们提供的基础功能、如何实现、如何进行扩展等，代码分析基于Java 7。

12.1.1 AbstractCollection

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

public boolean addAll(Collection<? extends E> 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> T[] toArray(T[] a)
public String toString()

AbstractCollection又不知道数据是怎么存储的，它是如何实现这些方法的呢？它依赖于如下更为基础的方法：

1
2
3

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

add方法的默认实现是：

1
2
3

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

抛出“操作不支持”异常，如果子类集合是不可被修改的，这个默认实现就可以了，否则，必须重写add方法。addAll方法的实现就是循环调用add方法。

size方法是抽象方法，子类必须重写。isEmpty方法就是检查size方法的返回值是否为0。toArray方法依赖size方法的返回值分配数组大小。

iterator方法也是抽象方法，它返回一个实现了迭代器接口的对象，子类必须重写。我们知道，迭代器定义了三个方法：

1
2
3

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

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

AbstractCollection中的大部分方法都是基于迭代器的方法实现的，比如contains方法，其代码为：

public boolean contains(Object o) {
    Iterator<E> 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;
}

通过迭代器方法循环进行比较。

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

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

DynamicArray当时没有实现根据索引添加和删除的方法，我们先来补充一下，如代码清单12-1所示。

代码清单12-1 添加方法后的DynamicArray

public class DynamicArray<E> {
    //…
    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，如代码清单12-2所示。

代码清单12-2 一个简单的迭代器类DynamicArrayIterator

public class DynamicArrayIterator<E>   implements Iterator<E>{
    DynamicArray<E> darr;
    int cursor;
    int lastRet = -1;
    public DynamicArrayIterator(DynamicArray<E> 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，如代码清单12-3所示。

代码清单12-3 一个简单的容器类MyCollection

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

代码很简单，就是按建议提供了两个构造方法，并重写了size、add和iterator方法，这些方法内部使用了DynamicArray和DynamicArrayIterator。

12.1.2 AbstractList

AbstractList提供了List接口的基础实现，具体来说，它实现了如下方法：

public boolean add(E e)
public boolean addAll(int index, Collection<? extends E> c)
public void clear()
public boolean equals(Object o)
public int hashCode()
public int indexOf(Object o)
public Iterator<E> iterator()
public int lastIndexOf(Object o)
public ListIterator<E> listIterator()
public ListIterator<E> listIterator(final int index)
public List<E> subList(int fromIndex, int toIndex)

AbstractList是怎么实现这些方法的呢？它依赖于如下更为基础的方法：

public abstract int size();
abstract public E get(int index);
public E set(int index, E element)
public void add(int index, E element)
public E remove(int index)

size方法与AbstractCollection一样，也是抽象方法，子类必须重写。get方法根据索引index获取元素，它也是抽象方法，子类必须重写。

set、add、remove方法都是修改容器内容，它们不是抽象方法，但默认实现都是抛出异常UnsupportedOperationException。如果子类容器不可被修改，这个默认实现就可以了。如果可以根据索引修改内容，应该重写set方法。如果容器是长度可变的，应该重写add和remove方法。

与AbstractCollection不同，继承AbstractList不需要实现迭代器类和相关方法，AbstractList内部实现了两个迭代器类，一个实现了Iterator接口，另一个实现了ListIterator接口，它们是基于以上的这些基础方法实现的，逻辑比较简单，就不赘述了。

具体如何扩展AbstractList呢？我们来看个例子，也通过DynamicArray来实现一个简单的List，如代码清单12-4所示。

代码清单12-4 扩展AbstractList的List实现

public class MyList<E> extends AbstractList<E> {
    private DynamicArray<E> darr;
    public MyList(){
        darr = new DynamicArray<>();
    }
    public MyList(Collection<? extends E> c){
        this();
        addAll(c);
    }
    @Override
    public E get(int index) {
        return darr.get(index);
    }
    @Override
    public int size() {
        return darr.size();
    }
    @Override
    public E set(int index, E element) {
        return darr.set(index, element);
    }
    @Override
    public void add(int index, E element) {
        darr.add(index, element);
    }
    @Override
    public E remove(int index) {
        return darr.remove(index);
    }
}

代码很简单，就是按建议提供了两个构造方法，并重写了size、get、set、add和remove方法，这些方法内部使用了DynamicArray。

12.1.3 AbstractSequentialList

AbstractSequentialList是AbstractList的子类，也提供了List接口的基础实现，具体来说，它实现了如下方法：

public void add(int index, E element)
public boolean addAll(int index, Collection<? extends E> c)
public E get(int index)
public Iterator<E> iterator()
public E remove(int index)
public E set(int index, E element)

可以看出，它实现了根据索引位置进行操作的get、set、add、remove方法，它是怎么实现的呢？它是基于ListIterator接口的方法实现的，在AbstractSequentialList中，listIterator方法被重写为了一个抽象方法：

1	public abstract ListIterator<E> listIterator(int index)

子类必须重写该方法，并实现迭代器接口。

我们来看段具体的代码，看get、set、add、remove是如何基于ListIterator实现的。get方法代码为：

public E get(int index) {
    try {
        return listIterator(index).next();
    } catch (NoSuchElementException exc) {
        throw new IndexOutOfBoundsException("Index: "+index);
    }
}

代码很简单，其他方法也都类似，就不赘述了。

注意与AbstractList相区别，可以说，虽然AbstractSequentialList是AbstractList的子类，但实现逻辑和用法上，与AbstractList正好相反。

AbstractList需要具体子类重写根据索引操作的方法get、set、add、remove，它提供了迭代器，但迭代器是基于这些方法实现的。它假定子类可以高效地根据索引位置进行操作，适用于内部是随机访问类型的存储结构（如数组），比如ArrayList就继承自AbstractList。
AbstractSequentialList需要具体子类重写迭代器，它提供了根据索引操作的方法get、set、add、remove，但这些方法是基于迭代器实现的。它适用于内部是顺序访问类型的存储结构（如链表），比如LinkedList就继承自AbstractSequentialList。

具体如何扩展AbstractSequentialList呢？我们还是以DynamicArray举例来说明，在实际应用中，如果内部存储结构类似DynamicArray，应该继承AbstractList，这里主要是演示其用法。

扩展AbstractSequentialList需要实现ListIterator，前面介绍的DynamicArrayIterator只实现了Iterator接口，通过继承DynamicArrayIterator，我们实现一个新的实现了List-Iterator接口的类DynamicArrayListIterator，如代码清单12-5所示。

代码清单12-5 实现了ListIterator接口的类DynamicArrayListIterator

public class DynamicArrayListIterator<E>
    extends DynamicArrayIterator<E> implements ListIterator<E>{
    public DynamicArrayListIterator(int index, DynamicArray<E> darr){
        super(darr);
        this.cursor = index;
    }
    @Override
    public boolean hasPrevious() {
        return cursor > 0;
    }
    @Override
    public E previous() {
        if(! hasPrevious())
            throw new NoSuchElementException();
        cursor--;
        lastRet = cursor;
        return darr.get(lastRet);
    }
    @Override
    public int nextIndex() {
        return cursor;
    }
    @Override
    public int previousIndex() {
        return cursor - 1;
    }
    @Override
    public void set(E e) {
        if(lastRet==-1){
            throw new IllegalStateException();
        }
        darr.set(lastRet, e);
    }
    @Override
    public void add(E e) {
        darr.add(cursor, e);
        cursor++;
        lastRet = -1;
    }
}

逻辑比较简单，就不解释了。有了DynamicArrayListIterator，我们看基于Abstract-SequentialList的List实现，如代码清单22-6所示。

代码清单12-6 基于AbstractSequentialList的List实现

public class MySeqList<E> extends AbstractSequentialList<E> {
    private DynamicArray<E> darr;
    public MySeqList(){
        darr = new DynamicArray<>();
    }
    public MySeqList(Collection<? extends E> c){
        this();
        addAll(c);
    }
    @Override
    public ListIterator<E> listIterator(int index) {
        return new DynamicArrayListIterator<>(index, darr);
    }
    @Override
    public int size() {
        return darr.size();
    }
}

代码很简单，就是按建议提供了两个构造方法，并重写了size和listIterator方法，迭代器的实现是DynamicArrayListIterator。

12.1.4 AbstractMap

AbstractMap提供了Map接口的基础实现，具体来说，它实现了如下方法：

public void clear()
public boolean containsKey(Object key)
public boolean containsValue(Object value)
public boolean equals(Object o)
public V get(Object key)
public int hashCode()
public boolean isEmpty()
public Set<K> keySet()
public void putAll(Map<? extends K, ? extends V> m)
public V remove(Object key)
public int size()
public String toString()
public Collection<V> values()

AbstractMap是如何实现这些方法的呢？它依赖于如下更为基础的方法：

1 2	public V put(K key, V value) public abstract Set<Entry<K, V>> entrySet();

putAll就是循环调用put。put方法的默认实现是抛出异常UnsupportedOperation-Exception，如果Map是允许写入的，则需要重写该方法。

其他方法都基于entrySet方法。entrySet方法是一个抽象方法，子类必须重写，它返回所有键值对的Set视图，如果Map是允许删除的，这个Set的迭代器实现类，即entrySet(). iterator()的返回对象，必须实现迭代器的remove方法，这是因为AbstractMap的remove方法是通过entrySet().iterator().remove()实现的。

除了提供基础方法的实现，AbstractMap类内部还定义了两个公有的静态内部类，表示键值对：

1 2	AbstractMap.SimpleEntry implements Entry<K, V> AbstractMap.SimpleImmutableEntry implements Entry<K, V>

SimpleImmutableEntry用于表示只读的键值对，而SimpleEntry用于表示可写的。

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

具体如何扩展AbstractMap呢？我们定义一个简单的Map实现类MyMap，内部还是用DynamicArray，如代码清单12-7所示。

代码清单12-7 一个简单的Map实现类MyMap

public class MyMap<K, V> extends AbstractMap<K, V> {
    private DynamicArray<Map.Entry<K, V>> darr;
    private Set<Map.Entry<K, V>> entrySet = null;
    public MyMap() {
        darr = new DynamicArray<>();
    }
    public MyMap(Map<? extends K, ? extends V> m) {
        this();
        putAll(m);
    }
    @Override
    public Set<Entry<K, V>> entrySet() {
        Set<Map.Entry<K, V>> es = entrySet;
        return es ! = null ? es : (entrySet = new EntrySet());
      }
      @Override
      public V put(K key, V value) {
        for(int i = 0; i < darr.size(); i++) {
            Map.Entry<K, V> entry = darr.get(i);
            if((key == null && entry.getKey() == null)
                    || (key ! = null && key.equals(entry.getKey()))) {
                V oldValue = entry.getValue();
                entry.setValue(value);
                return oldValue;
            }
        }
        Map.Entry<K, V> newEntry = new AbstractMap.SimpleEntry<>(key, value);
        darr.add(newEntry);
        return null;
    }
    class EntrySet extends AbstractSet<Map.Entry<K, V>> {
        public Iterator<Map.Entry<K, V>> iterator() {
            return new DynamicArrayIterator<Map.Entry<K, V>>(darr);
        }
        public int size() {
            return darr.size();
        }
    }
}

我们定义了两个构造方法，实现了put和entrySet方法。put方法先通过循环查找是否已存在对应的键，如果存在则修改值，否则新建一个键值对（类型为AbstractMap.Simple-Entry）并添加。entrySet返回的类型是一个内部类EntrySet，它继承自AbstractSet，重写了size和iterator方法，iterator方法中，返回的是迭代器类型是DynamicArrayIterator，它支持remove方法。

12.1.5 AbstractSet

AbstractSet提供了Set接口的基础实现，它继承自AbstractCollection，增加了equals和hashCode方法的默认实现。Set接口要求容器内不能包含重复元素，AbstractSet并没有实现该约束，子类需要自己实现。

扩展AbstractSet与AbstractCollection是类似的，只是需要实现无重复元素的约束，比如，add方法内需要检查元素是否已经添加过了。具体实现比较简单，我们就不赘述了。

12.1.6 AbstractQueue

AbstractQueue提供了Queue接口的基础实现，它继承自AbstractCollection，实现了如下方法：

public boolean add(E e)
public boolean addAll(Collection<? extends E> c)
public void clear()
public E element()
public E remove()

这些方法是基于Queue接口的其他方法实现的，包括：

1
2
3

E peek();
E poll();
boolean offer(E e);

扩展AbstractQueue需要实现这些方法，具体逻辑也比较简单，我们就不赘述了。

12.1.7 小结

本小节介绍了Java容器类中的抽象类AbstractCollection、AbstractList、AbstractSequen-tialList、AbstractSet、AbstractQueue以及AbstractMap，介绍了它们与容器接口和具体类的关系，对每个抽象类，介绍了它提供的基础功能，如何实现，并举例说明了如何进行扩展，完整的代码在github上，地址为 https://github.com/swiftma/program-logic ，位于包shuo.lao-ma.collection.c52下。

前面我们提到，实现了容器接口，就可以方便地参与到容器类这个大家庭中进行相互协作，也可以方便地利用Collections这个类实现的通用算法和功能。

但Collections都实现了哪些算法和功能？都有什么用途？如何使用？内部又是如何实现的？有何参考价值？让我们下一小节来探讨。

第12章 通用容器类和总结