主题：【原创】我们不谈数学（3）(草稿） -- jungleford

前面提到了偏序关系的问题，又勾起了俺古老的回忆

下面是俺五年前在blog上的涂鸦（那时候还是蜗在实验室里的青葱嫩小子），IT民工们可能会比较亲切，且作为一点补充的番外篇。

===================华丽的分割线===================

外链出处

关于集合框架的思考（2004-12-05）

jungleford如是说

对于Java集合框架（Java Collections Framework，JCF），Java玩家大概都不会陌生，在C++里面相似的概念是标准模板库（Standard Template Library，STL），主要是对一些数据结构和相关算法的封装。考虑到这是一个Java初学者将会经常接触的工具，所以有了以下的一些文字。主要是参考了IBM developerWorks上的一篇教程，它可能解释得更加清晰，这里算是浓缩了一下吧，真正的来龙去脉可以看看JDK文档里的“The Collections Framework”，说明更为详细。

问题的源头

* 集合：对象的容器与数据结构

回忆一下我们在程序设计里头可能会面对一些什么，无非是两类：基本类型和复合类型，后者常见的组织方式就是类。和基本类型不同，类对象通常是需要以动态方式分配的，譬如在内存的堆空间里new一个对象，这个我们一写OO的程序就必然会用到。同时我们面对的不仅仅是单个的基本类型或对象，对多个这样的数据我们通常采用的组织方式是什么？不错，是数组，这是伴随程序设计的一个古老概念。数组的优点显而易见，像根据下标检索元素这样的操作不费吹灰之力，但缺点也很明显：空间固定而不能动态增长（像Java这样的强类型语言对数组越界是及其敏感的），插入或删除元素比较费劲。因此数组不是解决一切集合问题的方便工具。我们可能需要一些新的工具，研究这些工具常常就是研究数据结构，特别的，数组本身就是一种线性有序的数据结构。

数据结构的数学基础是集合论，为什么这么说呢？上面说过，现在我们要研究的不是单个的基本类型或对象，多个对象的整体不就是集合吗？从OO的角度上看，集合也是一种对象，但它是一种特殊的对象：对象的容器（注意，我们这里没有继续讨论基本类型的集合，因为基本类型和存储分配方式与对象有着本质的差别）。集合论的一个根本问题就是：给定一个元素，集合必须能够回答该元素是或者不是属于这个集合。还有一个问题也很重要，就是：如果元素是属于一个集合，那该元素在集合中的地位应该是唯一的，或者说它是唯一确定的。当然还有其它问题，譬如查找、遍历、排序等等，这和具体的集合类型相关，后面将会讲到。

* 无序集、有序集、映射

谈到集合的类型，我们在高中所学的集合概念是其中的一种，叫做“无序集”，也就是说集合的各个元素都是平等的，没有先后的区别，于是在无序集当中就决不允许出现一模一样的元素，否则当取到这个元素的时候就不知道应该取哪一个，这就违反了上面的“唯一确定”原则。

等到我们上了大学，开始知道了另一种集合类型，叫做“有序集” （或者叫“线性表”，区别于以后碰到的像“树”，“图”这样的非线性的数据结构），如果是计算机专业的，大概学过离散数学当中的“代数结构”，那你就更清楚的知道，“有序集”其实是一种“二元关系”，确切的说是“偏序关系”，它是可以包含相同元素的，因为两个的相同元素的“序号”可以不同，这样根据“序号”仍可以“唯一确定”一个元素，数组就是一种有序集，有序集的另一个特点就是任意两个元素可以确定他们的顺序。

无序集，有序集，难道还有第三种可能？呵呵，它还是出现在我们的高中代数课本里，叫做“映射”。映射也是集合？其实自从康托尔以来，集合论就认为“万物皆集合”（但也就是这个断言导致了集合论以后的尴尬境地，有兴趣可以看看罗素或哥德尔的一些结论，或google“集合论 悖论”）。映射其实是一种“元素对”的集合，就像

等效于集合（无序集）

，在“映射”中可以看作是(原象, 象)的集合，换一种说法就是(关键字key, 值value)的集合。所以我们可以在笛卡儿正交坐标平面上画出漂亮的函数图像，因为在集合论看来，函数（映射）就是二维平面上的一个个点，明白了？这样一来上面的“有序集”也好理解了，偏序关系

（不知道“偏序关系”就把它们看作是数组

好了）等效于无序集

，于是乎，所有的集合都等效于无序集！所以高中只教了我们一种集合，呵呵……

JCF的全家福

好啦好啦，这些我们都知道，又不是在上数学课，说了这么多废话，怎么还没扯到正题上来？JCF的影子我还没看见呢！列位看官别急，这就给您道来。其实上面的概念对理解JCF非常重要。

JCF是个颇有点规模的家族，看看它的类层次关系图就知道了，下面这张图（图1）摘自著名的Thinking in Java：

图1 JCF层次结构

哇，这么多接口和类，真有点让人无从下手的感觉。其实我们真正需要记住的只是这么一个超超easy的结构（图2）：

图2

这张图看起来舒服多了吧？但它又能说明什么问题呢？它怎么就能够把握整个JCF呢？我们把Collection接口置于最顶上，意思是想说：Collection其实是整个JCF家族中的“祖宗”，几乎所有的JCF成员都源自该接口，或者和它有密切的关系，Collection提供关于集合的一些通用操作的接口，包括插入（add()方法）、删除（remove()方法）、判断一个元素是不是其成员（contains()方法）、遍历（iterator()方法）等等。注意了，前面的“废话”在这里将得到体现：Set接口体现的是“无序集”的概念，它是不允许有重复元素出现的；List接口代表“有序集”；而Map接口则是“映射”（在早期的Java版本中并不叫Map，我们在后面会看到），其实Map.Entry接口就是代表一个“元素对”我们可以通过Map的entrySet()方法得到这样一个由“元素对”组成的Set对象。我们注意到Set和List都是从“祖宗”Collection派生的，而Map不是，毕竟对一对元素的操作与对单个元素的操作还是有区别的，但是如果你仔细对照一下Collection和Map的源代码，以及它们的直接后代AbstractCollection和AbstractMap的源代码，你将会发现很多相似的地方，所以我们仍然可以把Map看成是和Collection有着血缘关系的接口，而和Set，List一起处于并列的位置。

有了“无序集”，“有序集”和“映射”，我们就可以定义各种各样的抽象数据结构了，譬如图1所示的向量，链表，堆栈，哈希表，平衡二叉树等。但我们需要记住的，仅仅是图2，置于其它的成员，在用到的时候查一下API手册不就行了？不过一般初学者还是比较容易用到一些类，像Vector、ArrayList、 HashMap，我在这里列了一张表，显示了常见的JCF成员及其关系：

可能有的概念您还不是太了解，譬如什么叫“历史集合”，Hashtable、HashMap、TreeMap三者之间有什么区别和联系，怎样实现对一个特定集合的快速遍历、元素查找或者排序，没关系，我们在下面将逐一进行研究。

细节考虑：目标与效率

有了JCF的层次还不够，重要的是对集合所容纳的对象的具体操作，以前我们学数据结构的时候可能老师总会让你计算一个算法的时间复杂度，可能你会对这个O(f(n))很不耐烦，但事实上算法效率是一个重要的因素。

1. 侧重点：遍历 vs. 查找

对集合的有两个主要的应用：我需要知道集合有哪些元素；根据条件找到一个特定的元素。在算法上通常称为“遍历”和“查找”。不要以为我们生活中不常用哦！譬如CCTV的“幸运52”里面，李咏让参赛者报出一款PDA的准确价位，他会怎么做？“2000”“高了”“1000”“低了”“1500”“低了”……直到答对为止。可能有很多人都会选择这个策略，无论他是不是计算机专业出身的，也不知道他是不是了解“数据结构”和“折半查找”，更不用说他是不是知道还有比在无初始代价下O(log n)的时间复杂度更快的算法了，但我们经常会自然而然地用这样的方法，这和一个人的行业无关，除非这个人的rp超强，呵呵……

又讲了一堆题外话了，遍历和修改似乎是一对矛盾，一个可以高效率插入删除元素的数据结构通常遍历的性能并不是最优。于是JCF在这里根据用户的目标实现了两种定制的数据结构：哈希表（包括HashSet和HashMap）和平衡二叉树（包括TreeSet和TreeMap）。由于可排序性是一种独特的要求，所以引入了SortedSet和SortedMap，它们分别是AbstractSet和AbstractMap的子接口，而TreeSet和TreeMap又分别是他们的一种实现。熟悉数据结构的人可能比较了解，哈希表在进行插入、删除、查找这样的操作是很快的，其时间复杂度是常数级O(1)；平衡二叉树虽然插入、删除操作比较麻烦（需要O(log n)的代价），但进行遍历和排序却很快。选择完全在于用户的侧重点，但由于类型转换的方便性，通常我们用哈希表构造一个集合以后，再把它转换成相应的树集进行遍历，以获得较好的效果。

2. 历史实现 vs. 新实现

历史实现（Legacy Implementations）是JCF的一个术语，准确的意义不是很清楚，但大致可以认为在Java 2（JDK 1.2）出现以前的老版本中JCF的一个雏形框架。在Java 2以后，JCF才开始完善健壮起来，新实现中出现了一些新的类用于替代老版本中的成员，但由于种种原因，老版本中很多类都代表了传统数据结构的精髓部分，以及一些安全原因，所以仍然被我们使用着。

Enumeration vs. Iterator

Enumeration是一个传统的集合遍历工具，在新的JCF中使用的是Iterator，Iterator同样具有遍历功能，还包含一个remove()方法来删除当前得到的元素。

Dictionary vs. Map

Dictionary 是一个现在已经被标记为deprecated的类，实现了老版本中的映射功能，现在已经完全被Map取代。它们的区别是：Dictionary中key和 value不能为null，但Map却允许空的关键字和值，这一点直接影响到它们的后代：Hashtable和HashMap。

Vector vs. ArrayList

Vector 和ArrayList是数组在JCF中的体现，还记得前面讲过的数组的缺点么？Vector和ArrayList就是一种可以动态增长的数组。 Vector是历史实现，它和ArrayList的主要区别在于，Vector是同步集合（或者说是线程安全的），但ArrayList并不是同步的，由于同步需要花一定的代价，所以ArrayList看起来要比Vector的存取访问效率更高。关于同步我们下面还将要谈到。

Hashtable vs. HashMap

Hashtable 是Dictionary的子类，属于历史实现，而HashMap是Map的子类，是新实现。它们的区别除了上面所说的key和value是否可以为空之外，也有同步的差别，Hashtable是同步的，但HashMap不是。HashMap的一个经典的例子就是JSP的内置对象session。不过不要因为Hashtable是“老前辈”而瞧不起它哦，它的一个著名的子类Propertie我们可是经常会用到的。

3. 同步 vs. 不同步

从上面的描述中我们似乎可以得出这么一个印象：历史实现好像都是同步的，但新实现中却没有。需要同步操作的理由是，可能存在多个线程对同一个集合进行操作的情况：譬如一个线程正在对某集合进行遍历，但与此同时，另一个线程又在对该集合进行插入或删除，那么第一个线程的遍历结果将是不可预测的，对于同步集合，它将会抛出一个ConcurrentModificationException异常，JCF把这种机制成为“fail-fast”。我们对比一下Vector和ArrayList的源代码就可以发现Vector的很多方法都是有synchronized关键字修饰的，但ArrayList没有。

4. 容易遗忘的工具：Collection和Array

在图1中右下角落里有两个类叫做Collections（注意，不是Collection！）和Arrays，这是JCF里面功能强大的工具，但初学者往往会忽视。按JCF文档的说法，这两个类提供了封装器实现（Wrapper Implementations）、数据结构算法和数组相关的应用。

想必大家不会忘记上面谈到的“折半查找”、“排序”等经典算法吧，Collections类提供了丰富的静态方法帮助我们轻松完成这些在数据结构课上烦人的工作：

Collections还有一个重要功能就是“封装器”（Wrapper），它提供了一些方法可以把一个集合转换成一个特殊的集合：

此外，我们知道把集合转换成对象数组可以用Collection的toArray()方法，我们也可以方便地把一个对象数组转换成一个线性表（可不要告诉我你是一个一个地add哦）：)]Arrays.asList()。

5. 泛型

目前我们了解的JCF的一个重要特征是：所有加入到集合当中的对象都将在表面上失去它们自己的特性，而看上去仅仅只是一个Object对象而已，除非你把它强制类型转换成它们原来的对象。这一点很自然，集合嘛，对象的容器，它容纳的是各种各样的对象，而不仅仅是某种特定类型的对象。J2SE 5.0出现以后，JCF开始引入泛型的特性，譬如我们经常碰到这样的应用，就是把集合转换成特定的数组，虽然Collection有toArray()的方法，但可惜的是，这个数组的所有元素都是Object类型的，我们通常的做法是用一个for循环把数组的每个元素都进行强制类型转换，虽然可行，但看上去很笨拙，如果有了泛型，我们就可以预先指定要得到的类型，然后一次toArray就可以得到我们期望的数组，里面的元素全部都是指定类型了。惭愧的是，我对5.0还不是太了解，具体可以参考J2SE 5.0的JCF文档。

小结

我这里走马观花一样把JCF的一些主要概念罗嗦了一下，Java的老手们可能比较厌烦，新手们可能更觉得像回顾了一下高中的数学课和大学的数据结构，呵呵。这只是一个小小的例子，可见基础知识对现实当中的应用还是蛮有指导意义的。大师们看数学，觉得那是很唯美很艺术的一样东西，西方一直都把数学区别于其它自然科学，而认为它更靠近于哲学，像我等这样整天还在为找工作烦得要死的俗人还是没法入道啊，sigh……

参考资料

* IBM developerWorks教程： Java 集合框架

* J2SE Documentation: The Collections Framework

* The Java Tutorial

* JCF API