從38節到51節，我們介紹的都是具體的容器類，上節我們提到，所有具體容器類其實都不是從頭構建的，它們都繼承了一些抽象容器類。這些抽象類提供了容器接口的部分實現，方便了Java具體容器類的實現，理解它們有助於進一步理解具體容器類。
此外，通過繼承抽象類，自定義的類也可以更為容易的實現容器接口。為什麼需要實現容器接口呢？至少有兩個原因：
那，具體都有哪些抽象類？它們都提供了哪些基礎功能？如何進行擴展？下面就來探討這些問題。
我們先來看都有哪些抽象類，以及它們與之前介紹的容器類的關系。
抽象容器類
抽象容器類與之前介紹的接口和具體容器類的關系如下圖所示：
虛線框表示接口，有Collection, List, Set, Queue, Deque和Map。
有六個抽象容器類：
下面，我們分別來介紹這些抽象類。
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正好相反：
擴展例子
具體如何擴展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編程及計算機技術的本質。用心原創，保留所有版權。
