全部 android asp.net C/C++ cshap IOS Java javascript nodejs perl php python ruby web容器 其他 前端 数据库 第三方平台 混合式APP 网络 系统 默认分类

计算机程序的思维逻辑 (52) - 抽象容器类

0 117

38节51节,我们介绍的都是具体的容器类,上节我们提到,所有具体容器类其实都不是从头构建的,它们都继承了一些抽象容器类。这些抽象类提供了容器接口的部分实现,方便了Java具体容器类的实现,理解它们有助于进一步理解具体容器类。

此外,通过继承抽象类,自定义的类也可以更为容易的实现容器接口。为什么需要实现容器接口呢?至少有两个原因:

  • 容器类是一个大家庭,它们之间可以方便的协作,比如很多方法的参数和返回值都是容器接口对象,实现了容器接口,就可以方便的参与进这种协作。
  • Java有一个类Collections,提供了很多针对容器接口的通用算法和功能,实现了容器接口,就可以直接利用Collections中的算法和功能。 

那,具体都有哪些抽象类?它们都提供了哪些基础功能?如何进行扩展?下面就来探讨这些问题。

我们先来看都有哪些抽象类,以及它们与之前介绍的容器类的关系。

抽象容器类

抽象容器类与之前介绍的接口和具体容器类的关系如下图所示:

虚线框表示接口,有Collection, List, Set, Queue, Deque和Map。

有六个抽象容器类:

  • AbstractCollection: 实现了Collection接口,被抽象类AbstractList, AbstractSet, AbstractQueue继承,ArrayDeque也继承自AbstractCollection (图中未画出)。
  • AbstractList:父类是AbstractCollection,实现了List接口,被ArrayList, AbstractSequentialList继承。
  • 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方法,否则,三个方法都必须实现。

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

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

通过迭代器方法循环进行比较。再比如retailAll方法,其代码为:

public boolean retainAll(Collection c) {
    boolean modified = false;
    Iterator it = iterator();
    while (it.hasNext()) {
        if (!c.contains(it.next())) {
            it.remove();
            modified = true;
        }
    }
    return modified;
}

也是通过迭代器方法进行循环,通过迭代器的remove方法删除不在参数容器c中的每一个元素。

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

扩展例子

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

DynamicArray当时没有实现根据索引添加和删除的方法,我们先来补充一下,补充代码为:

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,代码为:

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

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

AbstractList

功能说明

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

public boolean add(E e)
public boolean addAll(int index, Collection c)
public void clear()
public boolean equals(Object o)
public int hashCode()
public int indexOf(Object o)
public Iterator iterator()
public int lastIndexOf(Object o)
public ListIterator listIterator()
public ListIterator listIterator(final int index)
public List 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,代码为:

public class MyList extends AbstractList {
    private DynamicArray darr;
    
    public MyList(){
        darr = new DynamicArray<>();
    }
    
    public MyList(Collection 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。

AbstractSequentialList

功能说明

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

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

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

public abstract ListIterator 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,我们实现一个新的实现了ListIterator接口的类DynamicArrayListIterator,代码如下:

public class DynamicArrayListIterator  
    extends DynamicArrayIterator implements ListIterator{
    
    public DynamicArrayListIterator(int index, DynamicArray 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,我们看基于AbstractSequentialList的List实现,代码如下:

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

    @Override
    public int size() {
        return darr.size();
    }
}    

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

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 keySet()
public void putAll(Map m)
public V remove(Object key)
public int size()
public String toString()
public Collection values()

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

public V put(K key, V value)
public abstract Set> entrySet();

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

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

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

AbstractMap.SimpleEntry implements Entry
AbstractMap.SimpleImmutableEntry implements Entry

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

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

扩展例子

具体如何扩展AbstractMap呢?我们定义一个简单的Map实现类MyMap,内部还是用DynamicArray:

public class MyMap extends AbstractMap {
    private DynamicArray> darr;
    private Set> entrySet = null;

    public MyMap() {
        darr = new DynamicArray<>();
    }

    public MyMap(Map m) {
        this();
        putAll(m);
    }

    @Override
    public Set> entrySet() {
        Set> 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 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 newEntry = new AbstractMap.SimpleEntry<>(key, value);
        darr.add(newEntry);
        return null;
    }

    class EntrySet extends AbstractSet> {
        public Iterator> iterator() {
            return new DynamicArrayIterator>(darr);
        }

        public int size() {
            return darr.size();
        }
    }
}

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

AbstractSet

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

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

AbstractQueueAbstractQueue提供了Queue接口的基础实现,它继承自AbstractCollection,实现了如下方法:

public boolean add(E e)
public boolean addAll(Collection c)
public void clear()
public E element()
public E remove()

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

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

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

小结

本节介绍了Java容器类中的抽象类AbstractCollection, AbstractList, AbstractSequentialList, AbstractSet, AbstractQueue以及AbstractMap,介绍了它们与容器接口和具体类的关系,对每个抽象类,介绍了它提供的基础功能,是如何实现的,并举例说明了如何进行扩展。

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

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

----------------

未完待续,查看最新文章,敬请关注微信公众号“老马说编程”(扫描下方二维码),从入门到高级,深入浅出,老马和你一起探索Java编程及计算机技术的本质。用心原创,保留所有版权。

热忱回答0