自Java 2 Patform 诞生以来，Java Coections Framework 一直是Java核心类库的标准组成部分。如今，会发现起了些变化，我们有了其它的选择，譬如Jakarta Commons Coections 和 Recursion Software 公司最新的Java Generic ibrary (JG)。它们打破了Java Coections Framework 的垄断。（November 1, 2002）
在 Java 诞生之初，Java核心类库仅支持几种数据结构，包括数组（arrays）、向量（vectors） 和 hash tabes（键－值对）。而不支持另一些重要的数据结构，比如，平衡数（baanced trees）、原始对象袋（generic bags of objects）和优先队列（priority queues），但是这些你都可以自己来构建。因而，有一些开发者在类库中加入了他们自己的数据结构。
在这篇文章中，我们将回顾一些开发者早期的尝试，他们是如何发展Sun公司的Java Coections Framework的版本，以及该框架早期的进展和在参照了用户需求之后对一些数据结构的支持。
Java Coections Frameworks 的历史
首先，让我们回顾一下初期的数据结构集合，服务于纽约州立大学（在美国的Oswego）的Doug ea，他大概是创立了第一个被广泛应用的集合（coection）。该集合在1995年秋被发布。
那时候，一些早期的Java的开发者是由C＋＋转变而来。他们用Standard Tempate ibrary (ST) 进行开发，创立了Java 核心类库，而该类库极其缺乏对算法和数据结构的支持。 一家来自C＋＋和ST世界的公司（ObjectSpace）决定将ST接入Java。于是Java Generic ibrary (JG) 在1996年发布，但是Sun并不喜欢这个名字。ObjectSpace公司因此将其改名为Generic Coection ibrary for Java，但仍然使用JG这一缩写。
JG流行一时。通过营销，ObjectSpace公司使10个IDE（集成开发环境）工具提供商集成了该类库。ObjectSpace宣称它的基本用户已超过十万人。（而那时候Java开发者还远不及七位数。）事实上JG在Java早期成了一种标准。在几次修订之后，加了一个包并且与ObjectSpace的Voyager Object Request Broker (ORB) 集成，在1997年秋JG 3.1版发布。
随着J2SE 1.2的到来，以及它对数据结构支持的变化，Doug ea 放弃了他的 coections包，开始使用公用类的第二个类库开发。该新包提高了对数据的同步和多线程访问。在1998年7月发布的“uti.concurrent”类就提供了对锁闭（ocking）、池连（pooing）和同步（concurrent）的支持。
Java Coections Framework
J2SE 1.2 是在1998年12月发布的，它包括了一组称为Java Coections Framework 的类，用来操作数据集合。对比JG和 Coections Framework，它们有不同的目的JG是ST的替代品，而Java Coections Framework则不是。以前的C＋＋开发者倾向于使用JG，那是因为JG需要进行深入地学习，而这对于已经熟悉ST的人更为自然。JG大约有130个类和接口，而Coections Framework约是这个的百分之二十。
另外一个选择是Jakarta Commons Coections组件，于2001年7月发布,它用特制的数据类型和新方法扩展了J2SE 1.2 的APIS测试了集合论。在增添了一些类和接口的基础上，Coections Framework 和 J2SE 1.4版没有什么变化。对原型（如，模板），JSR14组织曾经辩论过，不过没有加入到J2SE 1.4。JSR 14 发布了一个原型，但仅在开发团体内部受到支持。
JSR 166 组织于去年1月出炉，由Doug ea 领导。该组织极力将先前提及uti.concurrent 类库中的诸多高水平概念并入到Java 核心类库中。
itte 从ObjectSpace公司的亲属那得知，在J2SE 1.4版发布前一天一个叫Recursion Software 的公司宣称取得了JG版权。后来，在2002年7月，Recursion Software 公司发布了JG 4.0版，并将JG集合和算法与标准的Coections Framework集成。
到了今天，我们可用的类库有：
Coections Framework，它是Java 核心类库的一部分，且定义了对所有数据结构实现的接口。
Jakarta Commons Coections组件，可以在Apache软件协议下自由取得。
JG 4.0
对Generic－types支持，作为原型对JSR 14 可用
两个非标准的类库（来自Doug ea），由JSR 166 正在发展成标准。
让我们来看看这些类库，考虑一下何时可能会使用它们。
The Coections Framework
Coection Framework 它提供了一套核心接口，共六个：Coection, Set, ist, SortedSet, Map, 和 SortedMap.
Coection 是sets和ists的基本接口。它描述了一组没有非凡特征的元素。对Coection没有直接的实现，仅有子接口的实现。
Set是一个由一些项组成的集合，这些项不容许出现重复。HashSet 和 TreeSet 是两个Set 的标准实现；TreeSet 是经过分类的，它实现了SortedSet。
ist接口是一个经排序的集合，提供了索引或顺序存取。ist的实现包括Arrayist和inkedist；Arrayist替代了原来的Vector类。
Map描述了‘键－值’格式的集合，类似于Hashtabe。可用的maps映射有HashMap和TreeMap；TreeMap是经过分类的，它实现了SortedMap。J2SE 1.4 引入两个新的实现：inkedHashSet和inkedHashMap，它们内部自动维护了在增添、搜索和删除操作后的元素顺序。J2SE 1.4 中另一个实现是IdentityHashMap，它用“＝＝”代替了“equas()”来进行等比较。对于在weak reference 感爱好的人来说，还有一个映射——WeakHashMap，它可以把WeakReference用作键（keys），因而，假如是通过键作为值（vaue）的唯一引用，将会丢弃该键－值对。
在设计之初，基本框架是非线程安全的。多线程的同步访问安全性需要用一个线程安全的外覆器（wrapper）来达到。这样的一种外覆器在集合框架中有一个只读的类似版本。
然而，这一框架比较小，不意味着对所有数据结构提供支持。相反，你仅仅可以通过它创建一些非凡的实现。
The Jakarta Commons Coections 组件
一些特定实现已被很好地定义与解释，可他们却不是核心集合框架（core Coections Framework）的一部分。其中的一些实现可能被包含在了同步公用类库里，随后我们将更为细致的讨论。
Jakarta Commons Coections 组件是这套特定实现的一个示例。被设计用来与J2SE 1.2 协作的Commons Coections 组件，它提供了两个ist实现和八个Map实现。新的基本结构也是可用的而且非常有趣。
让我们来看一看这一组特制实现。
最易理解的是FastArrayist, FastHashMap, 和 FastTreeMap。它们分别继续了标准的Arrayist、HashMap、和TreeMap，且都提供了在多线程下安全的同步读写访问。然而，安全性是需要成本的，这样便降低了写操作的速度。当读操作是非同步时，写操作在现存结构被替代时是在一份数据备份上进行地。
Bag就象是Set，但可以重复。另外它还有两个实现：HashBag和TreeBag；后者是经排序地。
另一个新的接口是PriorityQueue。它支持可比较项和使用比较器（Comparator），所以这些项可以BinaryHeap（基于优先级的）来维护，而且随后可从该堆中删除。
剩下的就是一组特定的Map实现。它们提供了非凡目标（specia－purpose）、键－值（key－vaue）来查找映射（maps）。
BeanMap运用反射提供了键值对（基于JavaBean属性）；该键是属性名，该值是这一属性名的值。
ExtendedProperties继续了java.uti.Properties；它为单一属性连接了多个值，而非覆写它。
RUMap是一个可维护最大容量的Map，而且使用了至少一个运算法则来定义在这一Map已满时要移去的节点。
MutiHashMap有点象WeakHashMap，但它用的是SoftReference而非WeakReference。
DoubeOrderedMap的重点在于串。它提供了一个Map来支持快速搜索（通过值和键）。但有这样一个要求：键和值必须都是唯一的。当然你用两个TreeMap对象也可以做到，但DoubeOrderedMap对每一个键值对仅保存一次。
其它更多的类和接口则更多的支持角色，但仍有一些非凡的方法可用。除了象isSubCoection和合并等一些公用方法外，该框架还包括了附加的Comparators和Iterators。Comparators大部分是用来连锁或替换另一个Comparator的行为。比如说，java.uti.Coections.reverseOrder()可以颠倒元素的原顺序，而ReverseComparator通过一个比较器（Comparator）来颠倒顺序。Iterators是在取出元素之前将每个Coection元素通过一个函数（或方法）的作用。这是JG和ST共享的方法。
JG 4.0
自1997年以来，JG就没有任何的更新，所以它的新版本使我很惊奇。我以为JG已没有了任何目的。显然，Recursion Software赋予了它其它的目的。该公司公布其基本用户已超过25万人，可是我并没有听说有谁在使用它。这一新版本与先前3.1版主要有三个不同之初：
所有的类与接口都集成到了Coections Framework中，且同该框架一样，默认非同步访问。
包的名称由com.objectspace.jg改成了com.recursionsw.jg。
Voyager-reated已被废止。
假如你对JG还不是很熟悉的话，请参阅JavaWord网站的文章。然而，新版没有太大的变化，类库仅能与J2SE 1.3.1和1.4协作。你可以将Coection Framework同JG混用。JG还提供了独立的抽象数据类型和法则。它支持50种预运算法则，而Coection Framework有18种。我明白为什么有人要学习两个不同的框架，但是一个好处就是使用JG的人可以将他们的应用程序部分的转移到Coections Framework中，而非所有。JG对于原是C＋＋的java开发者比起Coections Framework要更熟悉，但是由于JG现在是该框架的一部分，这并不要紧。
Generic types
最早计划要对核心集合框架的修改是去支持参数化的数据类型，又称为原型（generics），或者是模板（tempates）。现在所有的集合都不是型别安全的（type－safe）。你可以将任一个对象加到集合中，而且，在取出一个元素是，
