- 浏览: 21060 次
- 性别:
- 来自: 苏州
文章分类
最新评论
http://www.blogjava.net/jungleford/archive/2005/04/02/2759.html
对于Java集合框架(Java Collections Framework,JCF),Java玩家大概都不会陌生,在C++里面相似的概念是标准模板库(Standard Template Library,STL),主要是对一些数据结构和相关算法的封装。考虑到这是一个Java初学者将会经常接触的工具,所以有了以下的一些文字。主要是参 考了IBM developerWorks上的一篇教程,它可能解释得更加清晰,这里算是浓缩了一下吧,真正的来龙去脉可以看看JDK文档里的“The Collections Framework”,说明更为详细。
问题的源头
- 集合:对象的容器与数据结构
数据结构的数学基础是集合论, 为什么这么说呢?上面说过,现在我们要研究的不是单个的基本类型或对象,多个对象的整体不就是集合吗?从OO的角度上看,集合也是一种对象,但它是一种特 殊的对象:对象的容器(注意,我们这里没有继续讨论基本类型的集合,因为基本类型和存储分配方式与对象有着本质的差别)。集合论的一个根本问题就是:给定 一个元素,集合必须能够回答该元素是或者不是属于这个集合。还有一个问题也很重要,就是:如果元素是属于一个集合,那该元素在集合中的地位应该是唯一的, 或者说它是唯一确定的。当然还有其它问题,譬如查找、遍历、排序等等,这和具体的集合类型相关,后面将会讲到。
- 无序集、有序集、映射
等到我们上了大学,开始知道了另一种集合类型,叫做“有序集”(或 者叫“线性表”,区别于以后碰到的像“树”,“图”这样的非线性的数据结构),如果是计算机专业的,大概学过离散数学当中的“代数结构”,那你就更清楚的 知道,“有序集”其实是一种“二元关系”,确切的说是“偏序关系”,它是可以包含相同元素的,因为两个的相同元素的“序号”可以不同,这样根据“序号”仍 可以“唯一确定”一个元素,数组就是一种有序集,有序集的另一个特点就是任意两个元素可以确定他们的顺序。
无序集,有序集,难道还有第三种可能?呵呵,它还是出现在我们的高中代数课本里,叫做“映射”。映射也是集合?其实自从康托尔以来,集合论就认为“万物皆集合”(但也就是这个断言导致了集合论以后的尴尬境地,有兴趣可以看看罗素或哥德尔的一些结论,或google“集合论 悖论”)。映射其实是一种“元素对”的集合,就像f(a)=b, f(c)=d, ...等效于集合(无序集){(a, b), (c, d), ...}, 在“映射”中可以看作是(原象, 象)的集合,换一种说法就是(关键字key, 值value)的集合。所以我们可以在笛卡儿正交坐标平面上画出漂亮的函数图像,因为在集合论看来,函数(映射)就是二维平面上的一个个点,明白了?这样 一来上面的“有序集”也好理解了,偏序关系a>b>c>d>...(不知道“偏序关系”就把它们看作是数组x[1]=a, x[2]=b, x[3]=c, x[4]=d ...好了)等效于无序集{(1, a), (2, b), (3, c), (4, d), ...},于是乎,所有的集合都等效于无序集!所以高中只教了我们一种集合,呵呵……
JCF的全家福
HashSet | TreeSet | LinkedHashSet | ||
ArrayList | LinkedList | |||
HashMap | TreeMap | LinkedHashMap |
好啦好啦,这些我们都知道,又不是在上数学课,说了这么多废话,怎么还没扯到正题上来?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成员及其关系:
集合框架的祖宗: Collection |
历史集合 |
新集合 |
|||||||
无序集: Set |
有序集: List |
映射:Dictionary |
映射:Map |
||||||
历史集合 |
新集合 |
||||||||
可能有的概念您还不是太了解,譬如什么叫“历史集合”,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)的代价),但进行遍历和排序却很快。选择完全在于用户的侧重点,但由于类型转换的方便性,通常我们用哈希表构造一个集合以后,再把它转换成相应的树集 进行遍历,以获得较好的效果。
Set set1 = new HashSet(); set1.add(elem1);// 通过插入元素构造集合 set1.add(elem2); set1.add(elem3); Set set2 = new TreeSet(set); Iterator all = set2.iterator(); while (all.hasNext()) {// 遍历集合 all.next(); ... } |
- 2. 历史实现 vs. 新实现
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是“老前辈”而瞧不起它哦,它的一个著名的子类Properties我们可是经常会用到的。
- 3. 同步 vs. 不同步
-
4. 容易遗忘的工具:Collections和Arrays
想必大家不会忘记上面谈到的“折半查找”、“排序”等经典算法吧,Collections类提供了丰富的静态方法帮助我们轻松完成这些在数据结构课上烦人的工作:
binarySearch:折半查找。
sort:排序,这里是一种类似于快速排序的方法,效率仍然是O(n * log n),但却是一种稳定的排序方法。
reverse:将线性表进行逆序操作,这个可是从前数据结构的经典考题哦!
rotate:以某个元素为轴心将线性表“旋转”——哇,这个功能太酷了!
swap:交换一个线性表中两个元素的位置。
……
Collections还有一个重要功能就是“封装器”(Wrapper),它提供了一些方法可以把一个集合转换成一个特殊的集合:
unmodifiableXXX:转换成只读集合,这里XXX代表六种基本集合接口:Collection、List、Map、Set、SortedMap和SortedSet。如果你对只读集合进行插入删除操作,将会抛出UnsupportedOperationException异常。
synchronizedXXX:转换成同步集合。
singleton:创建一个仅有一个元素的集合,这里singleton生成的是单元素Set,singletonList和singletonMap分别生成单元素的List和Map。
空集:由Collections的静态属性EMPTY_SET、EMPTY_LIST和EMPTY_MAP表示。
此外,我们知道把集合转换成对象数组可以用Collection的toArray()方法,我们也可以方便地把一个对象数组转换成一个线性表(可不要告诉我你是一个一个地add哦):Arrays.asList()。
- 5. 泛型
小结
我 这里走马观花一样把JCF的一些主要概念罗嗦了一下,Java的老手们可能比较厌烦,新手们可能更觉得像回顾了一下高中的数学课和大学的数据结构,呵呵。 这只是一个小小的例子,可见基础知识对现实当中的应用还是蛮有指导意义的。大师们看数学,觉得那是很唯美很艺术的一样东西,西方一直都把数学区别于其它自 然科学,而认为它更靠近于哲学,像我等这样整天还在为找工作烦得要死的俗人还是没法入道啊,sigh……
参考资料
- IBM developerWorks教程: Java 集合框架
- J2SE Documentation: The Collections Framework
- The Java Tutorial
- JCF API
相关推荐
JAVA集合框架,java框架总结,java集合框架,java集合框架学习,java集合框架类
xmind格式的Java集合框架学习导图,包括Collection接口/Map接口以及具体实现类。 同样包含大厂面试题,也在导图中有所体现。 能学到什么: 更加成体系的知识框架,更加全面的、系统的知识。 思维导图: 思维导图具有...
掌握集合的概念、体系结构、分类及使用场景 2)了解Set接口及主要实现类(HashSet、TreeSet) 3)了解List接口及主要实现类...2、为什么使用集合框架,而尽可能少用数组作为存储结构? 3、如何使用TreeSet实现第一题?
引言 1. 前提 2. Java的学习 3. 目标 4. 联机文档 5. 章节 6. 练习 7. 多媒体CD-ROM 8. 源代码 9. 编码样式 10. Java版本 ...1.7.1 集合与继承器 ...1.7.3 集合库与方便使用...附录E 关于垃圾收集的一些话 附录F 推荐读物
该文档包含了Java面试中常见的面试题目,涵盖了Java基础知识、Java集合框架、Java并发编程、Java虚拟机等方面。 使用该Java面试题可以帮助面试者更加全面地了解Java面试的考点和难点,提高面试成功率。该面试题的...
关于Java框架Vert.x的几点思考.docx 关于堆和栈的那些事.docx 写好Java代码的30条经验总结.docx 华为java笔试面试题2014.doc 多态的理解.docx 大公司最喜欢问的Java集合类面试题.docx 大公司的Java面试题集.doc 就业...
关于Java框架Vert.x的几点思考.docx 关于堆和栈的那些事.docx 写好Java代码的30条经验总结.docx 华为java笔试面试题2014.doc 多态的理解.docx 大公司最喜欢问的Java集合类面试题.docx 大公司的Java面试题集.doc 就业...
2020世界信息安全大会演示PPT集合,共大家参考学习,包括: 基于OPC DA协议C2攻击链; 安全运营体系建设; 大型企业基础架构安全; 工控设备系统安全实践; 攻防技术趋势和企业威胁猎捕能力建设实践; 合规视角下...
Java集合框架(Collection Framework)是什么,它包含哪些类? Java中反射(Reflection)是什么?它有什么用处? Java中的多线程编程(Multithreading)是什么,如何实现? Java中的异常处理(Exception Handling)...
用集合组织相关数据 文件读写与 XML 用对象来思考:继承 用对象来思考:多态 用对象来思考:接口 序列化与反射 8. Video 教学 Video: 演示 新闻阅读器 功能 9. 附录 类库中主要命名空间 数据...
4、初步了解和掌握Java集合框架。 5、掌握Java包装类的基本用法。 6、初步掌握几个常用类和接口的含义和使用。 ★专题:文件IO和数据库编程★ 1、掌握File类的使用。 2、掌握字节流IO的操作。 3、掌握字符流IO的...
Java集合框架 并发编程 框架 Spring SpringBoot 数据库 安全 分布式 微服务 Spring Cloud Dubbo 架构设计 场景设计 缓存 网络 网络学习资源 性能调优 性能调优学习资源 Tomcat 面试题 互联网大厂面试题 技术博客:IT...
关于Java框架Vert.x的几点思考.docx 关于堆和栈的那些事.docx 写好Java代码的30条经验总结.docx 华为java笔试面试题2014.doc 多态的理解.docx 大公司最喜欢问的Java集合类面试题.docx 大公司的Java面试题集.doc 就业...
Anthem 是一个最小的 REST 框架。 目标是通过围绕 REST 操作进行轻量级抽象来减少创建 RESTful API 所涉及的样板文件。 JavaScript 没有协议,但这是思考 Anthem 的好方法。 Anthem 旨在使用基于类的继承进行扩展...
优势:Vue 是一个轻量级框架,只关注图层,是一个构建数据的视图集合,大小只有十几KB。vue简单易学,而且通过 MVVM 思想实现了数据的双向绑定,让开发者不用再操作 dom 对象,有更多时间去思考业务逻辑。而且 vue是...
第24章 Hibernate与Struts框架 24.1 实现业务数据 24.2 实现业务逻辑 24.3 netstore应用的订单业务 24.4 小结 第25章 Hibernate与EJB组件 25.1 创建EJB组件 25.1.1 编写Remote接口 25.1.2 编写Home...
第24章 Hibernate与Struts框架 24.1 实现业务数据 24.2 实现业务逻辑 24.3 netstore应用的订单业务 24.4 小结 第25章 Hibernate与EJB组件 25.1 创建EJB组件 25.1.1 编写Remote接口 25.1.2 编写Home...
第24章 Hibernate与Struts框架 24.1 实现业务数据 24.2 实现业务逻辑 24.3 netstore应用的订单业务 24.4 小结 第25章 Hibernate与EJB组件 25.1 创建EJB组件 25.1.1 编写Remote接口 25.1.2 编写Home...
第24章 Hibernate与Struts框架 24.1 实现业务数据 24.2 实现业务逻辑 24.3 netstore应用的订单业务 24.4 小结 第25章 Hibernate与EJB组件 25.1 创建EJB组件 25.1.1 编写Remote接口 25.1.2 编写Home...