JAVA集合框架思考.docVIP

JAVA集合框架思考 jungleford如是说 对于Java集合框架（Java Collections Framework，JCF），Java玩家大概都不会陌生，在C++里面相似的概念是标准模板库（Standard Template Library，STL），主要是对一些数据结构和相关算法的封装。前段时间在J2SE版看到一个关于Java集合框架的问题，当时re了一下，简单解释了一些的概念，考虑到这是一个Java初学者将会经常接触的工具，所以有了以下的一些文字。主要是参考了IBM developerWorks上的一篇教程，它可能解释得更加清晰，这里算是浓缩了一下吧，真正的来龙去脉可以看看JDK文档里的“The Collections Framework”，说明更为详细。 问题的源头 集合：对象的容器与数据结构 回忆一下我们在程序设计里头可能会面对一些什么，无非是两类：基本类型和复合类型，后者常见的组织方式就是类。和基本类型不同，类对象通常是需要以动态方式分配的，譬如在内存的堆空间里new一个对象，这个我们一写OO的程序就必然会用到。同时我们面对的不仅仅是单个的基本类型或对象，对多个这样的数据我们通常采用的组织方式是什么？不错，是数组，这是伴随程序设计的一个古老概念。数组的优点显而易见，像根据下标检索元素这样的操作不费吹灰之力，但缺点也很明显：空间固定而不能动态增长（像Java这样的强类型语言对数组越界是及其敏感的），插入或删除元素比较费劲。因此数组不是解决一切集合问题的方便工具。我们可能需要一些新的工具，研究这些工具常常就是研究数据结构，特别的，数组本身就是一种线性有序的数据结构。 数据结构的数学基础是集合论，为什么这么说呢？上面倒??衷谖颐且?芯康牟皇堑ジ龅幕?纠嘈突蚨韵螅?喔龆韵蟮恼?宀痪褪羌?下穑看?O的角度上看，集合也是一种对象，但它是一种特殊的对象：对象的容器（注意，我们这里没有继续讨论基本类型的集合，因为基本类型和存储分配方式与对象有着本质的差别）。集合论的一个根本问题就是：给定一个元素，集合必须能够回答该元素是或者不是属于这个集合。还有一个问题也很重要，就是：如果元素是属于一个集合，那该元素在集合中的地位应该是唯一的，或者说它是唯一确定的。当然还有其它问题，譬如查找、遍历、排序等等，这和具体的集合类型相关，后面将会讲到。 无序集、有序集、映射 谈到集合的类型，我们在高中所学的集合概念是其中的一种，叫做“无序集”，也就是说集合的各个元素都是平等的，没有先后的区别，于是在无序集当中就决不允许出现一模一样的元素，否则当取到这个元素的时候就不知道应该取哪一个，这就违反了上面的“唯一确定”原则。 等到我们上了大学，开始知道了另一种集合类型，叫做“有序集”（或者叫“线性表”，区别于以后碰到的像“树”，“图”这样的非线性的数据结构），如果是计算机专业的，大概学过离散数学当中的“代数结构”，那你就更清楚的知道，“有序集”其实是一种“二元关系”，确切的说是“偏序关系”，它是可以包含相同元素的，因为两个的相同元素的“序号”可以不同，这样根据“序号”仍可以“唯一确定”一个元素，数组就是一种有序集，有序集的另一个特点就是任意两个元素可以确定他们的顺序。 无序集，有序集，难道还有第三种可能？呵呵，它还是出现在我们的高中代数课本里，叫做“映射”。映射也是集合？其实自从康托尔以来，集合论就认为“万物皆集合”（但也就是这个断言导致了集合论以后的尴尬境地，有兴趣可以看看罗素或哥德尔的一些结论，或google“集合论 悖论”）。映射其实是一种“元素对”的集合，就像f(a)=b, f(c)=d, ...等效于集合（无序集）{(a, b), (c, d), ...}，在“映射”中可以看作是(原象, 象)的集合，换一种说法就是(关键字key, 值value)的集合。所以我们可以在笛卡儿正交坐标平面上画出漂亮的函数图像，因为在集合论看来，函数（映射）就是二维平面上的一个个点，明白了？这样一来上面的“有序集”也好理解了，偏序关系abcd...（不知道“偏序关系”就把它们看作是数组x[1]=a, x[2]=b, x[3]=c, x[4]=d ...好了）等效于无序集{(1, a), (2, b), (3, c), (4, d), ...}，于是乎，所有的集合都等效于无序集！所以高中只教了我们一种集合，呵呵…… JCF的全家福 好啦好啦，这些我们都知道，又不是在上数学课，说了这么多废话，怎么还没扯到正题上来？JCF的影子我还没看见呢！列位看官别急，这就给您道来。其实上面的概念对理解JCF非常重要。 JCF是个颇有点规模的家族，看看它的类层次关系图就知道了，下面这张图（图1）摘自著名的Thinking in Java：  图1 JCF层次结构 哇，这