计算机程序的思维逻辑 (52)

来源:转载

从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<? 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又不知道数据是怎么存储的,它是如何实现这些方法的呢?它依赖于如下更为基础的方法:

public boolean add(E e)

public abstract int size();

public abstract Iterator<E> 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<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;

}

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

public boolean retainAll(Collection<?> c) {

boolean modified = false;

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

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

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。

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

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。

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方法被重写为了一个抽象方法:

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,我们实现一个新的实现了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,我们看基于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。

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是如何实现这些方法的呢?它依赖于如下更为基础的方法:

public V put(K key, V value)

public abstract Set<Entry<K,V>> 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<K,V>

AbstractMap.SimpleImmutableEntry implements Entry<K,V>

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

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

扩展例子

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

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.SimpleEntry)并添加。
entrySet返回的类型是一个内部类EntrySet,它继承自AbstractSet,重写了size和iterator方法,iterator方法中,返回的是迭代器类型是DynamicArrayIterator,它支持remove方法。

AbstractSet

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

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

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接口的其他方法实现的,包括:

E peek();

E poll();

boolean offer(E e);

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

小结

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

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

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

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

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

分享给朋友:
您可能感兴趣的文章:
随机阅读: