介绍三个集合容器库
－－－对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 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已被废止。
假如你对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