Java 集合(Collections)总结

第一次系统的阅读理解Java Collections Framework的源码,已经粗略的学习完了,做个简单的总结。首先把资料放置在第一位,想系统学习的主要原因在工作之余想自学点东西,看了master24 的博文之后,感觉有必要把Java最长用的包学习一下,一来可以熟悉下Collections的API使用,用到再查和熟练使用总是不一样的。再者Collections Framework设计者书籍《Effective Java》荣获Jolt大奖,参考书及源码肯定有很多可学之处,而且相对于Java很多开源程序代码量并不大。

 

如果想找一个开源的代码来读,之前又没有系统阅读代码的经验,不想读Tomcat、Jobss、Struts、Hibernate、Spring中大块头的经典开源项目,阅读Collection蛮好,代码量小,获得过Jolt大奖,质量无容置疑。

一、集合对比
父类 数据结构 Java实现 优点 缺点
List 有序存放、元素可以重复
ArrayList 数组 Object[] 索引快 插入慢
LinkedList 双链表 Entry Inner Class 插入块 索引慢
Vector 与ArrayList类似 线程安全
Stack
Set 无重复元素,不排序。
HashSet HashMap实现
HashMap  存取 hashMap.put(value, new Object);
(如果是值类,通过覆盖hashCode与equals方法确认元素是否重复)
查找速度快
TreeSet

NavigableMap 存取 hashMap.put(value, new Object);

(可以通过存入的元素实现Comparable接口,比较元素与元素排序操作)
Map Entry implements Map.Entry
HashMap Hash Table + 单链表 Entry Inner Class + Entry[]
TreeMap 红黑二叉树
java.util.Hashtable 线程安全

关于Collection接口的实现(仅对1.2之后新增实现)

1. 非线程同步。HashTable等是线程同步的,但是JDK 1.2之前出现的类。

2. iterators 是 fail-fast在遍历时不能直接进行 CRUD操作

3. serializable 和 cloneable

4. 全都支持null元素。

5. 必须支持optional methods例如add和remove方法,否则UnsupportedOpertaionException。
6. Set重用Map(Set.add 等于Map.put(SetValue, new Object);)

 

* 容器的遍历

 

heap和stack有什么区别
栈是一种线形集合,其添加和删除元素的操作应在同一段完成。栈按照后进先出的方式进行处理。堆是栈的一个组成元素

二、Collections Framework学习步骤

 

 

1.  自己写一个ArrayList

 

自己写的ArrayList没有继承 AbstractList,没有实现List、RandomAccess、Cloneable、Serializable。只是凭借自己的使用ArryList的记忆写一个完全跟Collection框架无关的代码实现。不过仅仅写了add、get、set、size、iterator方法,期间学了很多东西,

 

例如:

1.1 内部结构:ArrayList是使用数组实现,数组需要一个默认的值,当元素超出数组的长度的时候,必须加以处理,增加容量新建一个数组,把之前的元素重新Copy到新数组中。

 

1.2 数组类型与泛型:使用Object作为数组的类型,Object是所有类的根类,任何类存入都不会出现类型异常等问题,add时存入Object[],在get方法中返回时再根据泛型类型进行强制类型转换。

例如:return (E) elementData[index]; ( ArrayList get方法的源码 )

 

1.3 获取容器的值:自己最初使用的是getter方法,可以获得数组及其中每一个元素,不需要考虑多个类间的复用、线程安全、序列化等问题。解决一个问题,怎么简单怎么来,打蚊子不用高射炮。

 

1.4 Iterator模式:复习迭代模式,与getter方法进行比较有哪些异同?

相同点:目的相同,都是通过方法,获取一个集合,可以顺序访问一个集合中的各个元素。

不同点:getter方法会暴漏内部细节,ArrayList的getter方法肯定必须return一个Object[]数组。

使用Iterator可以隐藏内部实现细节,即使内部数据结构不同。

如:LinkedList与HashSet使用时无需考虑是内部数据是红黑二叉树还是HashMap。

 

1.5 fail-fast:

在iterator方法中得到应用,使用迭代的时候不允许对集合进行add或set等修改操作,否则出现ConcurrentModificationException异常。

fail-fast 解释:???

Martin Fowler 2004《IEEE Software》文章《Fail Faster》

 

2.  使用Junit测试

2.1先学会使用,如果有不了解的方法,不知道怎样使用,可以参考资料中提及的Java 年鉴 或 《Java 编程思想4》

 

2.2感性认识一些类和方法使用有哪些效果,以测试源码BUG的方法,例如:能不能使用NULL值、怎样算越界等。

按照方法的特性进行分类,例如:???  可以系统的查看源码
2.3便于系统学习,如果有些暂时不感兴趣,以后可以填补,也有可能确实没有完全写test方法的必要。

三、接口、实现、算法

设计、Hash Table(算法、HashCode、equals)、内部数据结构

RandomAccess、Serializable(writeObject、readObject、transient)

Collections  排序、二分查找

主要是两个工具类java.util.Collections 与 java.util.Arrays。

四、参考资料

1. 博文:

Collections系列文章 (作者 : 江苏 无锡 缪小东 网名:master24)

 

2. Java 年鉴:

java.util.* 年鉴      Java年鉴首页

 

3. JDK UML 图 :

Collections Framework UML 图         JDK UML 图下载地址

 

4. 书籍:

《Java Collections》 目前没有发现有中文版的,看英文版的PDF吧

《Effective Java》 作者:Joshua Bloch 、 Java Collections Framework框架设计者

(Addison Wesley, 2001)荣膺2002年度Jolt大奖

标签