摘要
自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 Framework
J2SE 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 Framework
Collection 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已被廢