程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> JAVA編程 >> JAVA綜合教程 >> 計算機程序的思維邏輯 (52),思維52

計算機程序的思維邏輯 (52),思維52

編輯:JAVA綜合教程

計算機程序的思維邏輯 (52),思維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編程及計算機技術的本質。用心原創,保留所有版權。

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved