介紹三個集合容器庫
－－－對Java Collections Framework的補充
作者：John Zukowski
原文：http://www.javaworld.com/javaworld/jw-11-2002/jw-1101-collections-p1.html
譯者：yahh
MSN: yahh2008@hotmail.com
摘要
自Java 2 Platform 誕生以來，Java Collections Framework 一直是Java核心類庫的標準組成部分。如今，會發現起了些變化，我們有了其它的選擇，譬如Jakarta Commons Collections 和 Recursion Software 公司最新的Java Generic Library (JGL)。它們打破了Java Collections Framework 的壟斷。（November 1, 2002）
在 Java 誕生之初，Java核心類庫僅支持幾種數據結構，包括數組（arrays）、向量（vectors） 和 hash tables（鍵－值對）。而不支持另一些重要的數據結構，比如，平衡數（balanced trees）、原始對象袋（generic bags of objects）和優先隊列（priority queues），但是這些你都可以自己來構建。因而，有一些開發者在類庫中加入了他們自己的數據結構。
在這篇文章中，我們將回顧一些開發者早期的嘗試，他們是如何發展Sun公司的Java Collections Framework的版本，以及該框架早期的進展和在參照了用戶需求之后對一些數據結構的支持。
Java Collections Frameworks 的歷史首先，讓我們回顧一下初期的數據結構集合，服務于紐約州立大學（在美國的Oswego）的Doug Lea，他大概是創立了第一個被廣泛應用的集合（collection）。該集合在1995年秋被發布。
那時候，一些早期的Java的開發者是由C＋＋轉變而來。他們用Standard Template Library (STL) 進行開發，創立了Java 核心類庫，而該類庫極其缺乏對算法和數據結構的支持。 一家來自C＋＋和STL世界的公司（ObjectSpace）決定將STL接入Java。于是Java Generic Library (JGL) 在1996年發布，但是Sun并不喜歡這個名字。ObjectSpace公司因此將其改名為Generic Collection Library for Java，但仍舊使用JGL這一縮寫。
JGL流行一時。通過營銷，ObjectSpace公司使10個IDE（集成開發環境）工具提供商集成了該類庫。ObjectSpace宣稱它的基本用戶已超過十萬人。（而那時候Java開發者還遠不及七位數。）事實上JGL在Java早期成了一種標準。在幾次修訂之后，加了一個包并且與ObjectSpace的Voyager Object Request Broker (ORB) 集成，在1997年秋JGL 3.1版發布。
隨著J2SE 1.2的到來，以及它對數據結構支持的變化，Doug Lea 放棄了他的 collections包，開始使用公用類的第二個類庫開發。該新包提高了對數據的同步和多線程訪問。在1998年7月發布的“util.concurrent”類就提供了對鎖閉（locking）、池連（pooling）和同步（concurrent）的支持。
Java Collections FrameworkJ2SE 1.2 是在1998年12月發布的，它包括了一組稱為Java Collections Framework 的類，用來操作數據集合。對比JGL和 Collections Framework，它們有不同的目的JGL是STL的替代品，而Java Collections Framework則不是。以前的C＋＋開發者傾向于使用JGL，那是因為JGL需要進行深入地學習，而這對于已經熟悉STL的人更為自然。JGL大約有130個類和接口，而Collections Framework約是這個的百分之二十。
另外一個選擇是Jakarta Commons Collections組件，于2001年7月發布,它用特制的數據類型和新方法擴展了J2SE 1.2 的APIS測試了集合論。在增添了一些類和接口的基礎上，Collections Framework 和 J2SE 1.4版沒有什么變化。對原型（如，模板），JSR14組織曾經辯論過，不過沒有加入到J2SE 1.4。JSR 14 發布了一個原型，但僅在開發團體內部受到支持。
JSR 166 組織于去年1月出爐，由Doug Lea 領導。該組織極力將先前提及util.concurrent 類庫中的諸多高水平概念并入到Java 核心類庫中。
Little 從ObjectSpace公司的親屬那得知，在J2SE 1.4版發布前一天一個叫Recursion Software 的公司宣稱取得了JGL版權。后來，在2002年7月，Recursion Software 公司發布了JGL 4.0版，并將JGL集合和算法與標準的Collections Framework集成。
到了今天，我們可用的類庫有：
l Collections Framework，它是Java 核心類庫的一部分，且定義了對所有數據結構實現的接口。
l Jakarta Commons Collections組件，可以在Apache軟件協議下自由取得。
l JGL 4.0
l 對Generic－types支持，作為原型對JSR 14 可用
l 兩個非標準的類庫（來自Doug Lea），由JSR 166 正在發展成標準。
讓我們來看看這些類庫，考慮一下何時可能會使用它們。
The Collections FrameworkCollection Framework 它提供了一套核心接口，共六個：Collection, Set, List, SortedSet, Map, 和 SortedMap.
Collection 是sets和lists的基本接口。它描述了一組沒有特別特征的元素。對Collection沒有直接的實現，僅有子接口的實現。Set是一個由一些項組成的集合，這些項不容許出現重復。HashSet 和 TreeSet 是兩個Set 的標準實現；TreeSet 是經過分類的，它實現了SortedSet。
List接口是一個經排序的集合，提供了索引或順序存取。List的實現包括ArrayList和LinkedList；ArrayList替代了原來的Vector類。
Map描述了‘鍵－值’格式的集合，類似于Hashtable。可用的maps映射有HashMap和TreeMap；TreeMap是經過分類的，它實現了SortedMap。J2SE 1.4 引入兩個新的實現：LinkedHashSet和LinkedHashMap，它們內部自動維護了在增添、搜索和刪除操作后的元素順序。J2SE 1.4 中另一個實現是IdentityHashMap，它用“＝＝”代替了“equals()”來進行等比較。對于在weak reference 感興趣的人來說，還有一個映射——WeakHashMap，它可以把WeakReference用作鍵（keys），因而，如果是通過鍵作為值（value）的唯一引用，將會丟棄該鍵－值對。
在設計之初，基本框架是非線程安全的。多線程的同步訪問安全性需要用一個線程安全的外覆器（wrapper）來達到。這樣的一種外覆器在集合框架中有一個只讀的類似版本。
然而，這一框架比較小，不意味著對所有數據結構提供支持。相反，你僅僅可以通過它創建一些特殊的實現。
The Jakarta Commons Collections 組件一些特定實現已被很好地定義與解釋，可他們卻不是核心集合框架（core Collections Framework）的一部分。其中的一些實現可能被包含在了同步公用類庫里，隨后我們將更為細致的討論。
Jakarta Commons Collections 組件是這套特定實現的一個示例。被設計用來與J2SE 1.2 協作的Commons Collections 組件，它提供了兩個List實現和八個Map實現。新的基本結構也是可用的而且非常有趣。
讓我們來看一看這一組特制實現。
最易理解的是FastArrayList, FastHashMap, 和 FastTreeMap。它們分別繼承了標準的ArrayList、HashMap、和TreeMap，且都提供了在多線程下安全的同步讀寫訪問。然而，安全性是需要成本的，這樣便降低了寫操作的速度。當讀操作是非同步時，寫操作在現存結構被替代時是在一份數據備份上進行地。
Bag就象是Set，但可以重復。另外它還有兩個實現：HashBag和TreeBag；后者是經排序地。
另一個新的接口是PriorityQueue。它支持可比較項和使用比較器（Comparator），所以這些項可以BinaryHeap（基于優先級的）來維護，而且隨后可從該堆中刪除。
剩下的就是一組特定的Map實現。它們提供了特殊目標（special－purpose）、鍵－值（key－value）來查找映射（maps）。
l BeanMap運用反射提供了鍵值對（基于JavaBean屬性）；該鍵是屬性名，該值是這一屬性名的值。
l ExtendedProperties繼承了java.util.Properties；它為單一屬性連接了多個值，而非覆寫它。
l LRUMap是一個可維護最大容量的Map，而且使用了至少一個運算法則來定義在這一Map已滿時要移去的節點。
l MultiHashMap有點象WeakHashMap，但它用的是SoftReference而非WeakReference。
l DoubleOrderedMap的重點在于串。它提供了一個Map來支持快速搜索（通過值和鍵）。但有這樣一個要求：鍵和值必須都是唯一的。當然你用兩個TreeMap對象也可以做到，但DoubleOrderedMap對每一個鍵值對僅保存一次。
其它更多的類和接口則更多的支持角色，但仍有一些特別的方法可用。除了象isSubCollection和合并等一些公用方法外，該框架還包括了附加的Comparators和Iterators。Comparators大部分是用來連鎖或替換另一個Comparator的行為。比如說，java.util.Collections.reverseOrder()可以顛倒元素的原順序，而ReverseComparator通過一個比較器（Comparator）來顛倒順序。Iterators是在取出元素之前將每個Collection元素通過一個函數（或方法）的作用。這是JGL和STL共享的方法。
JGL 4.0自1997年以來，JGL就沒有任何的更新，所以它的新版本使我很驚訝。我以為JGL已沒有了任何目的。顯然，Recursion Software賦予了它其它的目的。該公司宣布其基本用戶已超過25萬人，可是我并沒有聽說有誰在使用它。這一新版本與先前3.1版主要有三個不同之初：
l 所有的類與接口都集成到了Collections Framework中，且同該框架一樣，默認非同步訪問。
l 包的名稱由com.objectspace.jgl改成了com.recursionsw.jgl。
l Voyager-related已被廢止。
假如你對JGL還不是很熟悉的話，請參閱JavaWorld網站的文章。然而，新版沒有太大的變化，類庫僅能與J2SE 1.3.1和1.4協作。你可以將Collection Framework同JGL混用。JGL還提供了獨立的抽象數據類型和法則。它支持50種預運算法則，而Collection Framework有18種。我明白為什么有人要學習兩個不同的框架，但是一個好處就是使用JGl的人可以將他們的應用程序部分的轉移到Collections Framework中，而非所有。JGL對于原是C＋＋的java開發者比起Collections Framework要更熟悉，但是由于JGL現在是該框架的一部分，這并不要緊。
Generic types最早計劃要對核心集合框架的修改是去支持參數化的數據類型，又稱為原型（generics），或者是模板（templates）。現在所有的集合都不是型別安全的（type－safe）。你可以將任一個對象加到集合中，而且，在取出一個元素是，你必須將它適當的轉型。如果從集合中取出你想要的型別只有在運行期才知道。JSR 14提議可以提供型別安全的集合訪問。
在最簡單的情況下，你只能通過型別和類名的聯系去確認正確的型別：
public static void main(String args[]) {
List<String> listOne = Arrays.asList(args);
List<String> listTwo = new ArrayList<String>(listOne);
}
在較復雜時，你可以把型別加入類的定義中，這時類中內部這一型別是很常見的：
class Node<T> {
T value;
Node(T value) {
this.value = value;
}
T getValue() {
return value;
}
void setValue(T value) {
this.value = value;
}
}對于generic－types支持的準確語法，以及是否被融入到J2SE的未來版本（可能是J2SE 1.5）還要作出決定。但是，如今你能生成與任意J2SE 1.3運行環境協作的類文件。你也不用要等到J2SE 1.5，去試試JSR 14的原型方法。
使用同步（Concurrency utilities）
先前我提到兩個類庫（來自Doug Lea）：collections和util.concurrent。后者是新類庫的第一個重擊，由JSR 166設計。從同步類庫的里外來看，JSR 16被包含在了JSR 176的計劃之內。
加入接受了JSR 166并加入到java的下一版本中，Java核心類庫體提供了非鎖閉隊列（nonblocking queue）、原子變量（atomic variables）、特定的鎖閉（some specialized locking）和定時機構（timing mechanisms）、同步集合（concurrent collections）（類似于Commons Collections的 FastArrayList和其相關的），還有一些有趣的機制（該機制裝入每個無捕捉異常的線程控制器，而非依賴ThreadGroup）。這不是一個全包含（all－inclusive）的列表，且隸屬于JSR 166。
注意如果要在你的程序中使用抽象數據類型，首先要做的是，你要了解核心集合框架。其它的都是以此為基礎，包括JSR所建議的東西。
一旦你了解了基本的集合類，你就能延伸到其它領域。當你現在可以擺弄generic－types的同時，你必須等待它的最終版本以及J2SE下一版本的同步類庫。如果發現Jakarta Commons Collections對你很有用，一定要用它。你可以避開創建一般的結構（例如multimap）。當一個一年級的計算科學系的學生能夠完成這樣的任務時，事實上這是有益的。Apache的許可對于大多數人來說不是什么問題。
JGL不是免費的，每一個開發者需要49.95美元。而且在你使用個別部分之前需要掌握這個類庫是如何運作的。近可能的融和JGL和Collections Framework，這可能并不是最好的選擇。一般來講，JGL就是提供了對Java核心類庫的另一選擇。我們寧愿使用Java主要類的優化代碼，而不在我們自己的集合上包裝第三方的類庫。是的，JGL支持更多的運算法則，而且有的可能還很有用。例如，你想多么頻繁的將整數集合取負？JGL可能對那些從C＋＋轉變來的Java開發者是有用的，但是，對于那些在用java編程的和對java感興趣的人，只了解標準集合框架的功用就行了。一般你是不需要JGL或是Commons Collections類。
關于作者John Zukowski同JZ Ventures領導著關于Java的咨詢，而且是jGuru組織FAQs的成員。他的新書有Learn Java with JBuilder 6 （Apress出版） and Mastering Java 2: J2SE 1.4（Sybex出版）。
Resources
· Original collections library from Doug Lea:
http://gee.cs.oswego.edu/dl/classes/collections/
· Doug Lea's util.concurrent library:
http://gee.cs.oswego.edu/dl/classes/EDU/oswego/cs/dl/util/concurrent/intro.html
· Past JavaWorld article (June 1997) about JGL:
http://www.javaworld.com/javaworld/jw-06-1997/jw-06-jgl.html
· Past JavaWorld article (January 1999) compares JGL and the Collections Framework:
http://www.javaworld.com/javaworld/jw-01-1999/jw-01-jglvscoll.html
· Past JavaWorld article (November 1998) introduces the Collections Framework:
http://www.javaworld.com/javaworld/jw-11-1998/jw-11-collections.html
· Collections Framework Design FAQ:
http://java.sun.com/j2se/1.4/docs/guide/collections/designfaq.html
· Jakarta Commons Collections component:
http://jakarta.apache.org/commons/collections.html
· JSR 14 generic-types support:
http://www.jcp.org/jsr/detail/14.jsp
· JSR 14 prototype (requires free registration):
http://developer.java.sun.com/developer/earlyAccess/adding_generics/
· JSR 166 concurrency utilities:
http://www.jcp.org/jsr/detail/166.jsp
· For those interested in learning more about JSR 166:
http://gee.cs.oswego.edu/dl/concurrency-interest/index.html
· JSR 176 (J2SE 1.5—Tiger):
http://www.jcp.org/jsr/detail/176.jsp
· Java Collections book by John Zukowski (Apress, 2001; ISBN: 1893115925):
http://www.apress.com/catalog/book/1893115925/
· Browse the J2SE section of JavaWorld's Topical Index:
http://www.javaworld.com/channel_content/jw-j2se-index.shtml?j2se
· Speak out in the JavaWorld Forum:
http://forums.devworld.com/webx?13@@.ee6b802
· Sign up for JavaWorld's free weekly Core Java email newsletter:
http://www.javaworld.com/subscribe
· You'll find a wealth of IT-related articles from our sister publications at IDG.net