CollectionsAPI定制實現（一）
br>許多程序員永遠不需要實現他們自己的 對象集 類。用本課程上面所描述的實現，你可以做得非常好。然而，有一天，你可能發現你要編寫一個你自己的核心 對象集 接口的實現。用由Java平臺提供的 abstract implementations（抽象實現），這一點很容易辦到。但是，在我們要討論如何編寫一個實現之前，讓我們先討論一下為什么你要做這樣一件事。
編寫你自己的實現的原因
以下列舉了幾種你可能要實現的對象集，但這并不是全部。
持久的(Persistent): 所有的內置 對象集 實現駐留在主存儲器，而在VM退出時則消失。 假設你需要一個 對象集，它能在下一次VM啟動時仍然存在。實現這樣一個 對象集 的途徑是在外部數據庫之上建立一個虛飾板（veneer）。這樣一個 對象集 可能會并發地接受多個VMs的訪問，因為它駐留在VM之外。
與特定應用相關的（Application-specific）: 這是一個非常廣闊的范疇。一個例子是包含實時遙感勘測數據的一個不可更改的 Map 。鍵可能代表位置，而值可能被從這些位置上的傳感器上讀取以響應 get 操作。
高并發的（Highly Concurrent）: 內置 對象集 未被設計為支持高并發性。同步包裝器（和早期實現）鎖定整個（ entire） 對象集 （在每次它被訪問時）。假設你正在建立一個服務器，并且需要一個可被許多線程并發訪問的 Map 實現。簡單的辦法就是建立一個可分別鎖定每一個存儲段的哈希表，并允許多線程對該表的并發訪問(假設它們正在分布于不同存儲段中的鍵)。
高性能、特殊目的（High-performance, Special-purpose）: 有許多數據結構利用有限的用法，以提供可能比用通用實現更好的性能。例如，考慮一個 Set， 它的元素被限定在一個小的、固定的領域。這樣的一個 Set 可被表示為一個 bit-vector, 它可提供令人眼花繚亂的快速性能以及低內存占用。 另一個例子涉及到包含長期相同元素值的 List。這樣的列表（它經常出現在文本處理中）可能是游長編碼的（run-length encoded）: 運行可被表示為一個單一的對象，該對象包含重復的元素和連續重復的次數。這個例子很有趣，因為它交替使用了兩個方面的性能：它要求比一個 ArrayList 小得多的空間，但更多的時間。
高性能、通用的（High-performance, General-purpose）: 設計 對象集 架構 的工程師試圖為每一 涌詼繼峁┳詈玫耐ㄓ檬迪? 但是有許多許多數據結構可能被使用，并且每天都在發明新的。也許你能帶來什么更快的東西!
增強功能(Enhanced functionality）: 假設你需要一個 Map (或 Set) 實現，它即可提供不變時間存取又可提供插入順序迭代。這種性能的結合可用哈希表獲得，它的所有元素被進一步以插入順序連接到一個雙向鏈表中（doubly-linked）。另外，作為一種替代選擇，假設你需要一種有效的 bag 實現(也稱作 multiset)-- 一個可提供不變時間訪問同時允許復制元素的 Collection。 那么，在HashMap上實現這樣的一個Collection是非常簡單明了的。
便利性（Convenience）: 你可能需要由Java平臺提供的那些實現之外的附加便利實現。例如，你可能經常需要一個代表單獨鍵-值映射的不變 Map 對象、或代表一個連續的整數局域的 List 對象或者其他什么東西。
適配器（Adapter）: 假設你正在使用某些有著自己特別的collectioon API 的早期API。你可以編寫一個適配器（adapter） 實現，它使那些 對象集 可以在 Java Collections Framework 上進行操作。一個適配器實現是一個薄的虛飾板，它可以包裝一個類型的對象，并使其表現得象另一個類型的對象。這是通過將后一類型的操作轉化到前一類型的結果。
如何編寫一個定制實現
借助Java平臺上的抽象實現（abstract implementations） 來編寫定制實現出奇地簡單。抽象實現是 核心 對象集 接口 的骨干實現，它明顯地是為便于定制實現的編寫而設計的。我們以一個例子開始，以下是一個 Arrays.asList的實現：
public static List asList(Object[] a) {
return new ArrayList(a);
}
private static class ArrayList extends AbstractList
implements java.io.Serializable
{
private Object[] a;
ArrayList(Object[] array) {
a = array;
}
public Object get(int index) {
return a[index];
}
public Object set(int index, Object 元素) {
Object oldValue = a[index];
a[index] = 元素;
return oldValue;
}
public int size() {
return a.length;
}
}
相信不相信？這幾乎就是包含在JDK中的實現。它是那樣的簡單! 你只提供構造函數、 get、 set 和 size 方法, 其余的都由 AbstractList 來做。而你免費獲得了 ListIterator, 批量操作、搜索操作、哈希代碼計算、比較和串表示法等。
假設你要使這個實現再快一點。API有關抽象實現的文本精確地描述了每一種方法是如何被實現的。于是，你將知道要覆蓋哪個方法，以得到你所需要的性能。上面提到的這些實現是很好的，但還能做些改進。特別是，toArray 方法在 List 上迭代，每次拷貝一個元素。假如在內部是這樣表示的，那么直接克隆這個數組則要快得多--那樣才是明智的:
public Object[] toArray() {
return (Object[]) a.clone();
}
隨著這個覆蓋（override）和類似的 toArray(Object[])的增加，這個實現完全是 JDK中的形象了。為了全面展現JDK，你還要堅持一下去使用其它抽象實現，它們要求你編寫你自己的迭代器，但是，它仍然不是那么難。 抽象實現的小結如下:
AbstractCollection: 一個既不是Set也不是 List的 Collection。如：一個元包（bag）。 最低限度下，你必須提供 iterator 和 size 方法。
AbstractSet : 一個 Set. 用法與 AbstractCollection 相同。
AbstractList : 一個由隨機存取數據存儲(如一個數組)所支持的 List 。 最低限度下，你必須提供定位存取方法 (get(int) 和可選擇的 set(int), remove(int), 以及add(int)) 和 size 方法。抽象類負責維護listIterator (和 iterator).
AbstractSequentialList : 一個由順序-存取數據存儲（如一個鏈接的列表）所支持的 List。最低限度下，你必須提供 listIterator 和 size 方法。抽象類負責維護該定位存取方法 (這與 AbstractList是相對的) 。
AbstractMap : 一個 Map。 最低限度下，你必須提供 entrySet 視圖。這是用 AbstractSet 類典型地實現的。如果該 Map 是可更改的，你還必須提供 put 方法。
編寫一個定制實現的過程，小結如下:
1.從上面的列表中選擇適當的抽象實現類。
2.為所有這些類的抽象方法提供實現。如果你的定制對象集 將是可更改的，你必須覆蓋一個或幾個具體方法。有關抽象實現類的API文本將告訴你覆蓋哪個方法。
3.測試 并（ 如果需要）調試實現。你現在已經有了一個工作的定制 對象集 實現!
4.如果你關心性能, 閱讀抽象實現類的API文本。如果某一種方法太慢，覆蓋它。如果你覆蓋了哪個方法，確認衡量一下覆蓋前后的性能! 你在性能上的付出將與你在功能上的收獲成正比！（通常，這一步被忽略）
編寫你自己的實現的原因
以下列舉了幾種你可能要實現的對象集，但這并不是全部。
持久的(Persistent): 所有的內置 對象集 實現駐留在主存儲器，而在VM退出時則消失。 假設你需要一個 對象集，它能在下一次VM啟動時仍然存在。實現這樣一個 對象集 的途徑是在外部數據庫之上建立一個虛飾板（veneer）。這樣一個 對象集 可能會并發地接受多個VMs的訪問，因為它駐留在VM之外。
與特定應用相關的（Application-specific）: 這是一個非常廣闊的范疇。一個例子是包含實時遙感勘測數據的一個不可更改的 Map 。鍵可能代表位置，而值可能被從這些位置上的傳感器上讀取以響應 get 操作。
高并發的（Highly Concurrent）: 內置 對象集 未被設計為支持高并發性。同步包裝器（和早期實現）鎖定整個（ entire） 對象集 （在每次它被訪問時）。假設你正在建立一個服務器，并且需要一個可被許多線程并發訪問的 Map 實現。簡單的辦法就是建立一個可分別鎖定每一個存儲段的哈希表，并允許多線程對該表的并發訪問(假設它們正在分布于不同存儲段中的鍵)。
高性能、特殊目的（High-performance, Special-purpose）: 有許多數據結構利用有限的用法，以提供可能比用通用實現更好的性能。例如，考慮一個 Set， 它的元素被限定在一個小的、固定的領域。這樣的一個 Set 可被表示為一個 bit-vector, 它可提供令人眼花繚亂的快速性能以及低內存占用。 另一個例子涉及到包含長期相同元素值的 List。這樣的列表（它經常出現在文本處理中）可能是游長編碼的（run-length encoded）: 運行可被表示為一個單一的對象，該對象包含重復的元素和連續重復的次數。這個例子很有趣，因為它交替使用了兩個方面的性能：它要求比一個 ArrayList 小得多的空間，但更多的時間。
高性能、通用的（High-performance, General-purpose）: 設計 對象集 架構 的工程師試圖為每一 涌詼繼峁┳詈玫耐ㄓ檬迪? 但是有許多許多數據結構可能被使用，并且每天都在發明新的。也許你能帶來什么更快的東西!
增強功能(Enhanced functionality）: 假設你需要一個 Map (或 Set) 實現，它即可提供不變時間存取又可提供插入順序迭代。這種性能的結合可用哈希表獲得，它的所有元素被進一步以插入順序連接到一個雙向鏈表中（doubly-linked）。另外，作為一種替代選擇，假設你需要一種有效的 bag 實現(也稱作 multiset)-- 一個可提供不變時間訪問同時允許復制元素的 Collection。 那么，在HashMap上實現這樣的一個Collection是非常簡單明了的。
便利性（Convenience）: 你可能需要由Java平臺提供的那些實現之外的附加便利實現。例如，你可能經常需要一個代表單獨鍵-值映射的不變 Map 對象、或代表一個連續的整數局域的 List 對象或者其他什么東西。
適配器（Adapter）: 假設你正在使用某些有著自己特別的collectioon API 的早期API。你可以編寫一個適配器（adapter） 實現，它使那些 對象集 可以在 Java Collections Framework 上進行操作。一個適配器實現是一個薄的虛飾板，它可以包裝一個類型的對象，并使其表現得象另一個類型的對象。這是通過將后一類型的操作轉化到前一類型的結果。
如何編寫一個定制實現
借助Java平臺上的抽象實現（abstract implementations） 來編寫定制實現出奇地簡單。抽象實現是 核心 對象集 接口 的骨干實現，它明顯地是為便于定制實現的編寫而設計的。我們以一個例子開始，以下是一個 Arrays.asList的實現：
public static List asList(Object[] a) {
return new ArrayList(a);
}
private static class ArrayList extends AbstractList
implements java.io.Serializable
{
private Object[] a;
ArrayList(Object[] array) {
a = array;
}
public Object get(int index) {
return a[index];
}
public Object set(int index, Object 元素) {
Object oldValue = a[index];
a[index] = 元素;
return oldValue;
}
public int size() {
return a.length;
}
}
相信不相信？這幾乎就是包含在JDK中的實現。它是那樣的簡單! 你只提供構造函數、 get、 set 和 size 方法, 其余的都由 AbstractList 來做。而你免費獲得了 ListIterator, 批量操作、搜索操作、哈希代碼計算、比較和串表示法等。
假設你要使這個實現再快一點。API有關抽象實現的文本精確地描述了每一種方法是如何被實現的。于是，你將知道要覆蓋哪個方法，以得到你所需要的性能。上面提到的這些實現是很好的，但還能做些改進。特別是，toArray 方法在 List 上迭代，每次拷貝一個元素。假如在內部是這樣表示的，那么直接克隆這個數組則要快得多--那樣才是明智的:
public Object[] toArray() {
return (Object[]) a.clone();
}
隨著這個覆蓋（override）和類似的 toArray(Object[])的增加，這個實現完全是 JDK中的形象了。為了全面展現JDK，你還要堅持一下去使用其它抽象實現，它們要求你編寫你自己的迭代器，但是，它仍然不是那么難。 抽象實現的小結如下:
AbstractCollection: 一個既不是Set也不是 List的 Collection。如：一個元包（bag）。 最低限度下，你必須提供 iterator 和 size 方法。
AbstractSet : 一個 Set. 用法與 AbstractCollection 相同。
AbstractList : 一個由隨機存取數據存儲(如一個數組)所支持的 List 。 最低限度下，你必須提供定位存取方法 (get(int) 和可選擇的 set(int), remove(int), 以及add(int)) 和 size 方法。抽象類負責維護listIterator (和 iterator).
AbstractSequentialList : 一個由順序-存取數據存儲（如一個鏈接的列表）所支持的 List。最低限度下，你必須提供 listIterator 和 size 方法。抽象類負責維護該定位存取方法 (這與 AbstractList是相對的) 。
AbstractMap : 一個 Map。 最低限度下，你必須提供 entrySet 視圖。這是用 AbstractSet 類典型地實現的。如果該 Map 是可更改的，你還必須提供 put 方法。
編寫一個定制實現的過程，小結如下:
1.從上面的列表中選擇適當的抽象實現類。
2.為所有這些類的抽象方法提供實現。如果你的定制對象集 將是可更改的，你必須覆蓋一個或幾個具體方法。有關抽象實現類的API文本將告訴你覆蓋哪個方法。
3.測試 并（ 如果需要）調試實現。你現在已經有了一個工作的定制 對象集 實現!
4.如果你關心性能, 閱讀抽象實現類的API文本。如果某一種方法太慢，覆蓋它。如果你覆蓋了哪個方法，確認衡量一下覆蓋前后的性能! 你在性能上的付出將與你在功能上的收獲成正比！（通常，這一步被忽略）