1集合论引

? 集合   ? 集合框架  

2数组与容器

3返回数组

4类

5复制数组

6数组比较

7数组元素

8数组排序

9有序数组

10数组部分

11框架益处

? 减少设计辛劳  

? 提高速度质量   ? API缺点   ? 集合框架的复用  

12基础版本

? 简介   ? Vector   ? Stack   ? Hashtable  

13后续版本

? Collection   ? List   ? Set   ? Map  

14未来容器

15总结

 

集合论^[1]是现代数学中重要的基础理论。它的概念和方法已经渗透到代数、拓扑和分析等许多数学分支以及物理学和质点力学等一些自然科学部门，为这些学科提供了奠基的方法，改变了这些学科的面貌。计算机科学作为一门现代科学因其与数学的缘源，自然其中的许多概念也来自数学，集合是其中之一。如果说集合论的产生给数学注入了新的生机与活力，那么计算机科学中的集合概念给程序员的生活也注入了新的生机与活力。

很难给集合下一个精确的定义，通常情况下，把具有相同性质的一类东西，汇聚成一个整体，就可以称为集合。比如，用Java编程的所有程序员，全体中国人等。通常集合有两种表示法，一种是列举法，比如集合A={1,2,3,4}，另一种是性质描述法，比如集合B={X|0<X<100且X属于整数}。集合论的奠基人康托尔在创建集合理论给出了许多公理和性质，这都成为后来集合在其它领域应用的基础，本文并不是讲述集合论的，所以如果你对集合论感兴趣，可以参考相关书籍。

那么有了集合的概念，什么是集合框架呢？集合框架是为表示和操作集合而规定的一种统一的标准的体系结构。任何集合框架都包含三大块内容：对外的接口、接口的实现和对集合运算的算法。

接口：即表示集合的抽象数据类型。接口提供了让我们对集合中所表示的内容进行单独操作的可能。

实现：也就是集合框架中接口的具体实现。实际它们就是那些可复用的数据结构。

算法：在一个实现了某个集合框架中的接口的对象身上完成某种有用的计算的方法，例如查找、排序等。这些算法通常是多态的，因为相同的方法可以在同一个接口被多个类实现时有不同的表现。事实上，算法是可复用的函数。如果你学过C++，那C++中的标准模版库（STL）你应该不陌生，它是众所周知的集合框架的绝好例子。

数组与其它容器的区别体现在三个方面：效率，类型识别以及可以持有primitives。数组是Java提供的，能随机存储和访问reference序列的诸多方法中的，最高效的一种。数组是一个简单的线性序列，所以它可以快速的访问其中的元素。但是速度是有代价的；当你创建了一个数组之后，它的容量就固定了，而且在其生命周期里不能改变。也许你会提议先创建一个数组，等到快不够用的时候，再创建一个新的，然后将旧的数组里的reference全部导到新的里面。其实（我们以后会讲的）ArrayList就是这么做的。但是这种灵活性所带来的开销，使得ArrayList的效率比起数组有了明显下降。

Java对数组和容器都做边界检查；如果过了界，它就会给一个RuntimeException。这种异常表明这个错误是由程序员造成的，这样你就用不着再在程序里面检查了。

还有一些泛型容器类包括List，Set和Map。他们处理对象的时候就好像这些对象都没有自己的具体类型一样。也就是说，容器将它所含的元素都看成是（Java中所有类的根类）Object的。这样你只需要建一种容器，就能把所有类型的对象全都放进去。从这个角度来看，这种作法很不错（只是苦了primitive。如果是常量，你还可以用Java的primitive的Wrapper类；如果是变量，那就只能放在你自己的类里了）。与其他泛型容器相比，这里体现数组的第二个优势：创建数组的时候，你也同时指明了它所持有的对象的类型（这又引出了第三点－－数组可以持有primitives，而容器却不行）。也就是说，它会在编译的时候作类型检查，从而防止你插入错误类型的对象，或者是在提取对象的时候把对象的类型给搞错了。Java在编译和运行时都能阻止你将一个不恰当的消息传给对象。所有这并不是说使用容器就有什么危险，只是如果编译器能够帮你指定，那么程序运行会更快，最终用户也会较少收到程序运行异常的骚扰。

从效率和类型检查的角度来看，使用数组总是没错的。但是，如果你在解决一个更为一般的问题，那数组就会显得功能太弱了点。

不管你用的是那种类型的数组，数组的标识符实际上都是一个“创建在堆（heap）里的实实在在的对象的”reference。实际上是那个对象持有其他对象的reference。你即可以用数组的初始化语句，隐含地创建这个对象，也可以用new表达式，明确地创建这个对象，只读的length属性能告诉你数组能存储多少元素。它是数组对象的一部分（实际上也是你唯一能访问的属性或方法）。‘[]’语法是另一条访问数组对象的途径。

你没法知道数组里面究竟放了多少元素，因为length只是告诉你数组能放多少元素，也就是说是数组对象的容量，而不是它真正已经持有的元素的数量。但是，创建数组对象的时候，它所持有的reference都会被自动地初始化为null，所以你可以通过检查数组的某个“槽位”是否为null，来判断它是否持有对象。以此类推，primitive的数组，会自动来数字初始化为零，字符初始化为(char)0，boolean初始化为false。

容器类只能持有Object对象的reference。而数组除了能持有Objects的reference之外，还可以直接持有primitive。当然可以使用诸如Integer，Double之类的wrapper类。把primitive的值放到容器中，但这样总有点怪怪的。此外，primitive数组的效率要比wrapper类容器的高出许多。

当然，如果你使用primitive的时候，还需要那种“能随需要自动扩展的”容器类的灵活性，那就不能用数组了。你只能用容器来存储primitive的wrapper类。

假设你写了一个方法，它返回的不是一个而是一组东西。那么在Java中就可以返回的“就是一个数组”。与C++不同，你永远也不必为Java的数组操心－－只要你还需要它，它就还在；一旦你用完了，垃圾回收器会帮你把它打扫干净。

java.util里面有一个Arrays类，它包括了一组可用于数组的static方法，这些方法都是一些实用工具。其中有四个基本方法：用来比较两个数组是否相等的equals()；用来填充的fill()；用来对数组进行排序的sort()；以及用于在一个已排序的数组中查找元素的binarySearch()。所有这些方法都对primitive和Object进行了重载。此外还有一个asList()方法，它接受一个数组，然后把它转成一个List容器。

虽然Arrays还是有用的，但它的功能并不完整。举例来说，如果它能让我们不用写for循环就能直接打印数组，那就好了。此外，正如你所看到的fill()只能用一个值填数组。所以，如果你想把随机生成的数字填进数组的话，fill()是无能为力的。

Java标准类库提供了一个System.arraycopy()的static方法。相比for循环，它能以更快的速度拷贝数组。System.arraycopy()对所有类型都作了重载。

对象数组和primitive数组都能拷贝。但是如果你拷贝的是对象数组，那么你只拷贝了它们的reference－－对象本身不会被拷贝。这被成为浅拷贝（shallow copy）。

为了能比较数组是否完全相等，Arrays提供了经重载的equals()方法。当然，也是针对各种primitive以及Object的。两个数组要想完全相等，他们必须有相同数量的元素，而且数组的每个元素必须与另一个数组的相对应的位置上的元素相等。元素的相等性，用equals()判断。（对于primitive，它会使用其wrapper类的equals()；比如int使用Integer.equals()。）。

Java里面有两种能让你实现比较功能的方法。一是实现java.lang.Comparable接口，并以此实现类“自有的”比较方法。这?这个方法能接受另一个对象作为参数，如果现有对象比参数小，它就会返回一个负数，如果相同则返回零，如果现有的对象比参数大，它就返回一个正数。

static randInt()方法会生成一个介于0到100之间的正数。

假设，有人给你一个没有实现Comparable接口的类，或者这个类实现了Comparable接口，但是你发现它的工作方式不是你所希望的，于是要重新定义一个新的比较方法。Java没有强求你一定要把比较代码塞进类里，它的解决方案是使用“策略模式（strategy design pattern）”。有了策略之后，你就能把会变的代码封装到它自己的类里（即所谓的策略对象strategy object）。你把策略对象交给不会变的代码，然后用它运用策略完成整个算法。这样，你就可以用不同的策略对象来表示不同的比较方法，然后把它们都交给同一个排序程序了。接下来就要“通过实现Comparator接口”来定义策略对象了。这个接口有两个方法compare()和equals()。但是除非是有特殊的性能要求，否则你用不着去实现equals()。因为只要是类，它就都隐含地继承自Object，而Object里面已经有了一个equals()了。所以你尽可以使用缺省的Object的equals()，这样就已经满足接口的要求了。

Collections类里专门有一个会返回与对象自有的比较法相反的Comparator的方法。它能很轻易地被用到CompType上面。

Collections.reverseOrder()返回了一个Comparator的reference。

compare()方法会根据第一个参数是小于，等于还是大于第二个参数，分别返回负整数，零或是正整数。

有了内置的排序方法之后，你就能对任何数组排序了，不论是primitive的还是对象数组的，只要它实现了Comparable接口或有一个与之相关的Comparator对象就行了。

Java标准类库所用的排序算法已经作了优化－－对primitive，它用的是“快速排序（Quicksort）”，对对象，它用的是“稳定合并排序（stable merge sort）”。所以除非是prolier表明排序算法是瓶颈，否则你不用为性能担心。

一旦数组排完序，你就能用Arrays.binarySearch()进行快速查询了。但是切忌对一个尚未排序的数组使用binarySearch()；因为这么做的结果是没意义的。

如果Arrays.binarySearch()找到了，它就返回一个大于或等于0的值。否则它就返回一个负值，而这个负值要表达的意思是，如果你手动维护这个数组的话，这个值应该插在哪个为止。这个值就是：

-(插入点)-1

“插入点”就是，在所有“比要找的那个值”更大值中，最小的那个值的下标，或者，如果数组中所有的值都比要找的值小，它就是a.size()。

如果数组里面有重复元素，那它不能保证会返回哪一个。这个算法不支持重复元素，不过它也不报错。所以，如果你需要的是一个无重复元素的有序序列的话，那么可以考虑使用本章后面所介绍的TreeSet（支持【排序顺序“sorted order”】）和LinkedHashSet（支持【插入顺序“sorted order”】）。这两个类会帮你照看所有细节。只有在遇到性能瓶颈的时候，你才应该用手动维护的数组来代替这两个类。

如果排序的时候用到了Comparator（针对对象数组，primitive数组不允许使用Comparator），那么binarySearch()的时候，也必须使用同一个Comparator（用这个方法的重载版）。

总而言之，如果你要持有一组对象，首选，同时也是效率最高的选择，应该是数组。而且，如果这是一组primitive的话，你也只能用数组。还有一些更为一般的情况，也就是写程序的时候还不知道要用多少对象，或者要用一种更复杂方式来存储对象情况。为此，Java提供了“容器类（container class）”。其基本类型有List，Set和Map。

它们还有一些别的特性。比方说Set所持有的对象，个个都不同，Map则是一个“关联性数组（associative array）”，它能在两个对象之间建立联系。此外，与数组不同，它们还能自动调整大小，所以你可以往里面放任意数量的对象。

集合框架通过提供有用的数据结构和算法使你能集中注意力于你的程序的重要部分上，而不是为了让程序能正常运转而将注意力于低层设计上。通过这些在无关API之间的简易的互用性，使你免除了为改编对象或转换代码以便联合这些API而去写大量的代码。

集合框架通过提供对有用的数据结构和算法的高性能和高质量的实现使你的程序速度和质量得到提高。因为每个接口的实现是可互换的，所以你的程序可以很容易的通过改变一个实现而进行调整。另外，你将可以从写你自己的数据结构的苦差事中解脱出来，从而有更多时间关注于程序其它部分的质量和性能。

许多API天生的有对集合的存储和获取。在过去，这样的API都有一些子API帮助操纵它的集合内容，因此在那些特殊的子API之间就会缺乏一致性，你也不得不从零开始学习，并且在使用时也很容易犯错。而标准集合框架接口的出现使这个问题迎刃而解。

对于遵照标准集合框架接口的新的数据结构天生即是可复用的。同样对于操作一个实现了这些接口的对象的算法也是如此。

有了这些优点，并通过合理的使用，它就会成为程序员的一种强大的工具。不过，从历史上来看，集合大多其结构相当复杂，也就给它们一个造成极不合理的学习曲线的坏名声。但是，希望Java2的集合框架能缩短你的学习曲线，从而快速掌握它。

在许多高级语言中的数组其实也是集合的一种简单实现，比如C,C++,Pascal和Java。数组保存着相同类型的多个值，它的长度在数组被创建时就固定下来，建立之后就无法改变。如果你需要一种大小能动态改变的存储结构，数组就不适合了，这时集合框架就有了用武之地了。

其实在Java2之前，Java是没有完整的集合框架的。它只有一些简单的可以自扩展的容器类，比如Vector，Stack，Hashtable等。Vector中包含的元素可以通过一个整型的索引值取得，它的大小可以在添加或移除元素时自动增加或缩小。然而，Vector的设计却存在极多缺陷（下面会说到）。Stack是一种后进先出（LIFO）的堆栈序列，学过数据结构的都会知道，它的重要特点是先放入的东西最后才能被取出。Hashtable与Java2中的Map类似，可以看成一种关联或映射数组，可以将两个或多个毫无关系的对象相关联，与数组不同的是它的大小可以动态变化。

Vector的操作很简单，通过addElement()加入一个对象，用elementAt()取出它，还可以查询当前所保存的对象的个数size();另外还有一个Enumeration类提供了连续操作Vector中元素的方法，这可以通过Vector中的elements()方法来获取一个Enumeration类的对象，可以用一个While循环来遍历其中的元素。用hasMoreElements()检查其中是否还有更多的元素。用nextElement()获得下一个元素。Enumeration的用意在于使你能完全不用理会你要遍历的容器的基础结构，只关注你的遍历方法，这也就使得遍历方法的重用成为可能。由于这种思想的强大功能，所以在Java2中被保留下来，不过具体实现，方法名和内部算法都改变了，这就是Java2中的Iterator以及ListIterator类。然而Enumeration的功能却十分有限，比如只能朝一个方向进行，只能读取而不能更改等。

单元素容器Stack，它最常用的操作便是压入和弹出，最后压入的元素最先被弹出。你可以想象一个只上面开口的书箱，最后放进去的书一定是最先被拿到，而最先放进去的只有在全部书拿出后才能取出，这种特性被称为后进先出（LIFO）。在Java中Stack的的用法也很简单，有push()压入一个元素，用pop()弹出一个元素。然而它的设计却无法让人理解，Stack继承了Vector而不用Vector作为其中一个元素类型来实现其功能，这样造成的结果是Stack也拥有Vector的行为，也就是说你可以把Stack当作一个Vector来用，而这与Stack的用意毫无关系。这应该算为Java1（1.0/1.1)中容器类库设计者的一大失误吧，还好，这些在Java2中都有了相当大的改变观。

Hashtable也是Java1中一个有用的容器类库。它的基本目标是实现两个或多个对象之间进行关联。举一个现实生活中的例子，比如我们说美国白宫时，指的就是在美国华盛顿的总统办公大楼，为什么一说到美国白宫，指的就是总统办公大楼呢？这是我们人为的对“美国白宫”和总统办公大楼进行了关联，本来“美国白宫”就是四个普通的文字，却有了不同的含义。在Java中我们就可以用String定义一个内容为“美国白宫”的对象变量，在定义一个总统大楼的对象变量，把它们进行关联，这就是Hashtable的用意。通过使用pub(Object key,Object value)方法把两个对象进行关联，需要时用get(Object key)取得与key关联的值对象。还可以查询某个对象的索引值等等。值得说明的这里的get方法查找一个对象时与Vector中的get方法在内部实现时有很大不同，在一个Hashtable中查找一个键对象要比在一个Vector中快的多。这是因为Hashtable使用了一种哈希表的技术（在数据结构中有详细讲解），在Java每个对象缺省都有一个通过Object的hashCode()方法获得的哈希码，Hashtable就是利用这个哈希实现快速查找键对象的。

Java1容器类库设计的另一个重大失误是竟然没有对容器进行排序的工具。比如你想让Vector容器中的对象按字典顺序进行排序，你就要自己实现。

虽然Java1中的容器类库如此简陋，却也使Java程序员在当时编程时省力不少，那些容器类也被大量用到，正所谓无可奈何，没得选择。可能是Java在其成长过程一直被美丽的光环笼照着，所以它的缺点也被人们忽略了，幸好，在Java2中容器类库设计者对以前的拙劣设计进行了大刀阔斧的整改，从而使Java变得更加完美。

自Java1.2之后Java版本统称为Java2，Java2中的容器类库才可以说是一种真正意义上的集合框架的实现。基本完全重新设计，但是又对Java1中的一些容器类库在新的设计上进行了保留，这主要是为了向下兼容的目的，当用Java2开发程序时，应尽量避免使用它们，Java2的集合框架已经完全可以满足你的需求。有一点需要提醒的是，在Java1中容器类库是同步化的，而Java2中的容器类库都是非同步化，这可能是对执行效率进行考虑的结果。

Java2中的集合框架提供了一套设计优良的接口和类，使程序员操作成批的数据或对象元素极为方便。这些接口和类有很多对抽象数据类型操作的API，而这是我们常用的且在数据结构中熟知的。例如Maps，Sets，Lists，Arrays等。并且Java用面向对象的设计对这些数据结构和算法进行了封装，这就极大的减化了程序员编程时的负担。程序员也可以以这个集合框架为基础，定义更高级别的数据抽象，比如栈、队列和线程安全的集合等，从而满足自己的需要。

Java2的集合框架，抽其核心，主要有三类：List、Set和Map。List和Set继承了Collection，而Map则独成一体。初看上去可能会对Map独成一体感到不解，它为什么不也继承Collection呢？但是仔细想想，这种设计是合理的。一个Map提供了通过Key对Map中存储的Value进行访问，也就是说它操作的都是成对的对象元素，比如put()和get()方法，而这是一个Set或List所不就具备的。当然在需要时，你可以由keySet()方法或values()方法从一个Map中得到键的Set集或值的Collection集。

它提供了基本操作如添加、删除。它也支持查询操作如是否为空isEmpty()方法等。为了支持对Collection进行独立操作，Java的集合框架给出了一个Iterator，它使得你可以泛型操作一个Collection，而不需知道这个Collection的具体实现类型是什么。它的功能与Java1中的Enumeration类似，只是更易掌握和使用，功能也更强大。在建立集合框架时，Sun的开发团队考虑到需要提供一些灵活的接口，用来操作成批的元素，又为了设计的简便，就把那些对集合进行可选操作的方法与基本方法放到了一起。因为一个接口的实现者必须提供对接口中定义的所有方法的实现，这就需要一种途径让调用者知道它正在调用的可选方法当前不支持。最后开发团队选择使用一种信号，也即抛出一种不支持操作例外(UnsupportedOperationException)，如果你在使用一个Collection中遇到一个上述的例外，那就意味着你的操作失败，比如你对一个只读Collection添加一个元素时，你就会得到一个不支持操作例外。在你实现一个集合接口时，你可以很容易的在你不想让用户使用的方法中抛出UnsupportOperationException来告诉使用者这个方法当前没有实现，UnsupportOperationException是RuntimeException的一个扩展。

另外Java2的容器类库还有一种Fail fast的机制。比如你正在用一个Iterator遍历一个容器中的对象，这时另外一个线程或进程对那个容器进行了修改，那么再用next()方法时可能会有灾难性的后果，而这是你不愿看到的，这时就会引发一个ConcurrentModificationException例外。这就是fail－fast。Collection的功能

下面这张表给出了Collection的所有功能，也就是你能用Set和List做什么事（不包括从Object自动继承过来的方法）。（List还有一些额外的功能。）Map不是继承Collection的，所以我们会区别对待。

boolean add(Object)：确保容器能持有你传给它的那个参数。如果没有把它加进去，就返回false。（这是个“可选”的方法，本章稍后会再作解释。）

boolean addAll(Collection)：加入参数Collection所含的所有元素。只要加了元素，就返回true。

void clear()：清除容器所保存的所有元素。（“可选”）

boolean contains(Object)：如果容器持有参数Object，就返回true。

boolean containsAll(Collection)：如果容器持有参数Collection所含的全部元素，就返回true。 boolean isEmpty()：如果容器里面没有保存任何元素，就返回true。

Iterator iterator()：返回一个可以在容器的各元素之间移动的Iterator。

boolean removeAll(Collection)：删除容器里面所有参数Collection所包含的元素。只要删过东西，就返回true。（“可选”）

boolean retainAll(Collection)：只保存参数Collection所包括的元素（集合论中“交集”的概念）。如果发生过变化，则返回true。（“可选”）

int size()：返回容器所含元素的数量。

Object[] toArray()：返回一个包含容器中所有元素的数组。

Object[] toArray(Object[] a)：返回一个包含容器中所有元素的数组，且这个数组不是普通的Object数组，它的类型应该同参数数组a的类型相同（要做类型转换）。

注意，这里没有能进行随机访问的get()方法。这是因为Collection还包括Set。而Set有它自己的内部顺序（因此随机访问是毫无意义的）。所以如果你要检查Collection的元素，你就必须使用迭代器。

接下来讲List, Set和Map的各种实现了，每讲一种容器，我都会（用星号）告诉你默认情况下应该选用哪种实现。

List接口对Collection进行了简单的扩充

它的具体实现类常用的有ArrayList和LinkedList。你可以将任何东西放到一个List容器中，并在需要时从中取出。ArrayList从其命名中可以看出它是一种类似数组的形式进行存储，因此它的随机访问速度极快，而LinkedList的内部实现是链表，它适合于在链表中间需要频繁进行插入和删除操作。在具体应用时可以根据需要自由选择。前面说的Iterator只能对容器进行向前遍历，而ListIterator则继承了Iterator的思想，并提供了对List进行双向遍历的方法。List的功能

List的基本用法是相当简单的。虽然绝大多数时候，你只是用add()加对象，用get()取对象，用iterator()获取这个序列的Iterator，但List还有一些别的很有用的方法。

实际上有两种List：擅长对元素进行随机访问的，较常用的ArrayList，和更强大的LinkedList。LinkedList不是为快速的随机访问而设计的，但是它却有一组更加通用的方法。

List（接口）：List的最重要的特征就是有序；它会确保以一定的顺序保存元素。List在Collection的基础上添加了大量方法，使之能在序列中间插入和删除元素。（只对LinkedList推荐使用。）List可以制造ListIterator对象，你除了能用它在List的中间插入和删除元素之外，还能用它沿两个方法遍历List。

ArrayList*：一个用数组实现的List。能进行快速的随机访问，但是往列表中间插入和删除元素的时候比较慢。ListIterator只能用在反向遍历ArrayList的场合，不要用它来插入和删除元素，因为相比LinkedList，在ArrayList里面用ListIterator的系统开销比较高。

LinkedList：对顺序访问进行了优化。在List中间插入和删除元素的代价也不高。随机访问的速度相对较慢。（用ArrayList吧。）此外它还有addFirst()，addLast()，getFirst()，getLast()，removeFirst()和removeLast()等方法（这些方法，接口和基类均未定义），你能把它当成栈（stack），队列（queue）或双向队列（deque）来用。

记住，容器只是一个存储对象的盒子。如果这个小盒子能帮你解决所有的问题，那你就用不着去管它是怎么实现的（在绝大多数情况下，这是使用对象的基本概念）。如果开发环境里面还有一些别的，会造成固定的性能开销的因素存在，那么ArrayList和LinkedList之间的性能差别就会变得不那么重要了。你只需要它们中的一个，你甚至可以想象有这样一种“完美”的抽象容器；它能根据用途，自动地切换其底层的实现。

用LinkedList做一个栈

“栈（stack）”有时也被称为“后进先出”（LIFO）的容器。就是说，最后一个被“压”进栈中的东西，会第一个“弹”出来。同其他Java容器一样，压进去和弹出来的东西都是Object，所以除非你只用Object的功能，否则就必须对弹起来的东西进行类型转换。

LinkedList的方法能直接实现栈的功能，所以你完全可以不写Stack而直接使用LinkedList。

如果你只想要栈的功能，那么继承就不太合适了，因为继承出来的是一个拥有LinkedList的所有方法的类。

用LinkedList做一个队列

队列（queue）是一个“先进先出”（FIFO）容器。也就是，你把一端把东西放进去，从另一端把东西取出来。所以你放东西的顺序也就是取东西的顺序。LinkedList有支持队列的功能的方法，所以它也能被当作Queue来用。

还能很轻易地用LinkedList做一个deque（双向队列）。它很像队列，只是你可以从任意一端添加和删除元素。

Set接口也是Collection的一种扩展

与List不同的是，在Set中的对象元素不能重复，也就是说你不能把同样的东西两次放入同一个Set容器中。它的常用具体实现有HashSet和TreeSet类。HashSet能快速定位一个元素，但是你放到HashSet中的对象需要实现hashCode()方法，它使用了前面说过的哈希码的算法。而TreeSet则将放入其中的元素按序存放，这就要求你放入其中的对象是可排序的，这就用到了集合框架提供的另外两个实用类Comparable和Comparator。一个类是可排序的，它就应该实现Comparable接口。有时多个类具有相同的排序算法，那就不需要在每分别重复定义相同的排序算法，只要实现Comparator接口即可。集合框架中还有两个很实用的公用类：Collections和Arrays。Collections提供了对一个Collection容器进行诸如排序、复制、查找和填充等一些非常有用的方法，Arrays则是对一个数组进行类似的操作。Set的功能

Set的接口就是Collection的，所以不像那两个List，它没有额外的功能。实际上Set确确实实就是一个Collection－－只不过行为方式不同罢了。（这是继承和多态性的完美运用：表达不同地行为。）Set会拒绝持有多个具有相同值的对象的实例（对象的“值”又是由什么决定的呢？这个问题比较复杂，我们以后会讲）。

Set（接口）：加入Set的每个元素必须是唯一的；否则，Set是不会把它加进去的。要想加进Set，Object必须定义equals()，这样才能标明对象的唯一性。Set的接口和Collection的一摸一样。Set的接口不保证它会用哪种顺序来存储元素。

HashSet*：为优化查询速度而设计的Set。要放进HashSet里面的Object还得定义hashCode()。

TreeSet：是一个有序的Set，其底层是一颗树。这样你就能从Set里面提取一个有序序列了。

LinkedHashSet(JDK 1.4)：一个在内部使用链表的Set，既有HashSet的查询速度，又能保存元素被加进去的顺序（插入顺序）。用Iterator遍历Set的时候，它是按插入顺序进行访问的。

HashSet保存对象的顺序是和TreeSet和LinkedHashSet不一样的。这是因为它们是用不同的方法来存储和查找元素的。（TreeSet用了一种叫红黑树的数据结构【red-black tree data structure】来为元素排序，而HashSet则用了“专为快速查找而设计”的散列函数。LinkedHashSet在内部用散列来提高查询速度，但是它看上去像是用链表来保存元素的插入顺序的。）你写自己的类的时候，一定要记住，Set要有一个判断以什么顺序来存储元素的标准，也就是说你必须实现Comparable接口，并且定义compareTo()方法。

SortedSet

SortedSet（只有TreeSet这一个实现可用）中的元素一定是有序的。这使得SortedSet接口多了一些方法：

Comparator comparator()：返回Set所使用的Comparator对象，或者用null表示它使用Object自有的排序方法。

Object first()：返回最小的元素。

Object last()：返回最大的元素。

SortedSet subSet(fromElement, toElement)：返回Set的子集，其中的元素从fromElement开始到toElement为止（包括fromElement，不包括toElement）。

SortedSet headSet(toElement)：返回Set的子集，其中的元素都应小于toElement。

SortedSet headSet(toElement)：返回Set的子集，其中的元素都应大于fromElement。

注意，SortedSet意思是“根据对象的比较顺序”，而不是“插入顺序”进行排序.

Map是一种把键对象和值对象进行关联的容器

一个值对象又可以是一个Map，依次类推，这样就可形成一个多级映射。对于键对象来说，像Set一样，一个Map容器中的键对象不允许重复，这是为了保持查找结果的一致性;如果有两个键对象一样，那你想得到那个键对象所对应的值对象时就有问题了，可能你得到的并不是你想的那个值对象，结果会造成混乱，所以键的唯一性很重要，也是符合集合的性质的。当然在使用过程中，某个键所对应的值对象可能会发生变化，这时会按照最后一次修改的值对象与键对应。对于值对象则没有唯一性的要求。你可以将任意多个键都映射到一个值对象上，这不会发生任何问题（不过对你的使用却可能会造成不便，你不知道你得到的到底是那一个键所对应的值对象）。Map有两种比较常用的实现：HashMap和TreeMap。HashMap也用到了哈希码的算法，以便快速查找一个键，TreeMap则是对键按序存放，因此它便有一些扩展的方法，比如firstKey(),lastKey()等，你还可以从TreeMap中指定一个范围以取得其子Map。键和值的关联很简单，用put(Object key,Object value)方法即可将一个键与一个值对象相关联。用get(Object key)可得到与此key对象所对应的值对象。

Map的功能

ArrayList能让你用数字在一个对象序列里面进行选择，所以从某种意义上讲，它是将数字和对象关联起来。但是，如果你想根据其他条件在一个对象序列里面进行选择的话，那又该怎么做呢？栈就是一个例子。它的标准是“选取最后一个被压入栈的对象”。我们常用的术语map，dictionary，或associative array就是一种非常强大的，能在序列里面进行挑选的工具。从概念上讲，它看上去像是一个ArrayList，但它不用数字，而是用另一个对象来查找对象！这是一种至关重要的编程技巧。

这一概念在Java中表现为Map。put(Object key, Object value)方法会往Map里面加一个值，并且把这个值同键（你查找时所用的对象）联系起来。给出键之后，get(Object key)就会返回与之相关的值。你也可以用containsKey()和containsValue()测试Map是否包含有某个键或值。

Java标准类库里有好几种Map：HashMap，TreeMap，LinkedHashMap，WeakHashMap，以及IdentityHashMap。它们都实现了Map的基本接口，但是在行为方式方面有着明显的诧异。这些差异体现在，效率，持有和表示对象pair的顺序，持有对象的时间长短，以及如何决定键的相等性。

性能是Map所要面对的一个大问题。如果你知道get()时怎么工作的，你就会发觉（比方说）在ArrayList里面找对象会是相当慢的。而这正是HashMap的强项。它不是慢慢地一个个地找这个键，而是用了一种被称为hash code的特殊值来进行查找的。散列（hash）时一种算法，它会从目标对象当中提取一些信息，然后生成一个表示这个对象的“相对独特”的int。hashCode()是Object根类的方法，因此所有Java对象都能生成hash code。HashMap则利用对象的hashCode()来进行快速的查找。这样性能就有了急剧的提高。

Map（接口）：维持键－－值的关系（既pairs），这样就能用键来找值了。

HashMap*：基于hash表的实现。（用它来代替Hashtable。）提供时间恒定的插入与查询。在构造函数种可以设置hash表的capacity和load factor。可以通过构造函数来调节其性能。

LinkedHashMap(JDK 1.4)：很像HashMap，但是用Iterator进行遍历的时候，它会按插入顺序或最先使用的顺序（least-recently-used(LRU)order）进行访问。除了用Iterator外，其他情况下，只是比HashMap稍慢一点。用Iterator的情况下，由于是使用链表来保存内部顺序，因此速度会更快。

TreeMap：基于红黑树数据结构的实现。当你查看键或pair时，会发现它们时按顺序（根据Comparable或Comparator，我们过一会讲）排列的。TreeMap的特点时，你所得到的是一个有序的Map。TreeMap是Map中唯一有subMap()方法的实现。这个方法能让你获取这个树中的一部分。

WeakHashMap：一个weak key的Map，是为某些特殊问题而设计的。它能让Map释放其所持有的对象。如果某个对象除了在Map当中充当键之外，在其他地方都没有其reference的话，那它将被当作垃圾回收。

IdentityHashMap(JDK 1.4)：一个用==，而不是equals()来比较键的hashmap。不是为我们平常使用而设计的，是用来解决特殊问题的。

散列是往Map里存数据的常用算法。

SortedMap

SortedMap（只有TreeMap这一个实现）的键肯定是有序的，因此这个接口里面就有一些附加功能的方法了。

Comparator comparator()：返回Map所使用的comparator，如果是用Object内置的方法的话，则返回null。

Object firstKey()：返回第一个键。

Object lastKey()：返回最后一个键。

SortedMap subMap(fromKey, toKey)：返回这个Map的一个子集，其键从fromKey开始到toKey为止，包括前者，不包括后者。

SortedMap headMap(toKey)：返回这个Map的一个子集，其键均小于toKey。

SortedMap tailMap(fromKey)：返回这个Map的一个子集，其键均大于等于fromKey。

pair是按key的顺序存储的，由于TreeMap有顺序的概念，因此“位置”是有意义的，所以你可以去获取它的第一个和最后一个元素，以及它的子集。

LinkedHashMap

为了提高速度，LinkedHashMap对所有东西都做了hash，而且遍历的时候（println()会遍历整个Map，所以你能看到这个过程）还会按插入顺序返回pair。此外，你还可以在LinkedHashMap的构造函数里面进行配置，让它使用基于访问的LRU（least-recently-used）算法，这样还没被访问过的元素（同时也是要删除的候选对象）就会出现在队列的最前头。这样，为节省资源而写一个定时清理的程序就变得很简单了。

前面几部分对Java中容器类库的状况进行了讨论，然而就在写下此文时，Sun已经开始通过某种途径分发J2SE1.5的Alpha测试版了。在JavaOne大会上，诸多大师描绘了Java的美好未来与在下一个版本中即将加入的一些新特性，其中为容器类库加入的一个重要特性就是泛型。

其实泛型并不是什么新东西，在其它一些面向对象的语言中早已存在，如C++。泛型的基本目标很简单：能够保证你使用一种类型安全的容器。那么到底怎样一种类型安全呢？我们先看下面这一段没有使用泛型特性的代码：

1. importjava.util.*;

2. public class Generics{

3. /**

4. * 输出一个String类型的列表，假设所给参数list中所有元素都为String。

5. */

6. public static void printList(Listlist){

7. for(int i=0;i<list.size();i++){

8. System.out.println(((String)list.get(i)).toString());

9. }

10. }

11. public static void main(String[] args){

12. Listlist=new ArrayList();

13. for(int i=0;i<9;i++){

14.list.add("Number:"+Integer.toString(i));

15. }

16. //list.add(new Generics()); //(1)

17. printList(list);

18. }

19. }

上面的代码很简单，定义了一个静态方法来打印一个元素为String类型的List，然而正如你看到的一样，如果你试着将(1)行中前面的注释去掉，你就会得到一个ClassCastException例外，因为printList会将list中的每个元素都转型为String，而在遇到最后一个元素时发现它是一个Generics类型从而无法完成转型，例外就被抛出。这种情况在Java编程中很容易出现，原因是Java的容器类库通常保存的是Object类型，而这是所有类的直接或间接超类，这就允许你将任何类型的元素添加到一个List中而不会给你任何提示，有经验的程序员可能会自己编写一个容器类来限制添加到其中的元素，这是一个编程技巧。但是我们就再也不用那样做了，泛型机制会为我们做好这件事。那就看一下用泛型机制对上面代码进行的改进：

1. importjava.util.*;

2. public class Generics{

3. /**

4. * 输出一个String类型的列表，限制了所给参数list中所有元素都为String

5. */

6. public static void printList(ArrayList<String> list){

7. for(int i=0;i<list.size();i++){

8. System.out.println(list.get(i).toString());

9. //get()返回的不再是Object类型，而是String类型

10. }

11. }

12. public static void main(String[] args){

13. ArrayListlist=new ArrayList<String>(); //注意此行中声明语法的变化

14. for(int i=0;i<9;i++){

15.list.add("Number:"+Integer.toString(i)); //只能向其中添加String类型

16. }

17.list.add(new Generics()); //无法通过，编译时错误

18. printList(list);

19. }

20. }

正如在代码中所看到的，容器的声明有了变化，即在一个容器类后面用<>来说明你想要放入这个容器中的元素类型，那么接下来你只能向这个容器加那种类型，否则编译就无法通过。在printList中也省去了转型的麻烦。当然有了泛型，并不是说以前的声明方法不能用了，你完全可以还用以前的方法，这没有任何问题。其实根据JSR中对for语句功能的增强，遍历一个容器也会更加简单。

当然泛型的使用方法不只如此，这里并没有对它进行完整描述，只想告诉你，泛型确实为我们编程提供了便利，但是仍然需要用心去学习和掌握。

1.数组把对象和数字形式的下标联系起来。它持有的是类型确定的对象，这样提取对象的时候就不用再作类型传递了。它可以是多维的，也可以持有primitive。但是创建之后它的容量不能改了。

2.Collection持有单个元素，而Map持有相关联的pair。

3.和数组一样，List也把数字下标同对象联系起来，你可以把数组和List想成有序的容器。List会随元素的增加自动调整容量。但是List只能持有Objectreference，所以不能存放primitive，而且把Object提取出来之后，还要做类型传递。

4.如果要做很多随机访问，那么请用ArrayList，但是如果要再List的中间做很多插入和删除的话，就应该用LinkedList了。

5.LinkedList能提供队列，双向队列和栈的功能。

6.Map提供的不是对象与数组的关联，而是对象和对象的关联。

HashMap看重的是访问速度，而TreeMap看重键的顺序，因而它不如HashMap那么快。而LinkedHashMap则保持对象插入的顺序，但是也可以用LRU算法为它重新排序。

7.Set只接受不重复的对象。HashSet提供了最快的查询速度。而TreeSet则保持元素有序。LinkedHashSet保持元素的插入顺序。

8.没必要再在新代码里使用旧类库留下来的Vector，Hashtable和Stack了。

容器类库是你每天都会用到的工具，它能使程序更简洁，更强大并且更高效。

随着Java的进一步完善，它的功能和易用性也得到提高，我有理由相信Java在计算机语言中所占的位置也会更加牢固，让喜爱Java的人更加喜爱它。祝愿Java一路走好！