1. 项目愿景
实现和完善一个处理集合数据结构的基本类库。
回页首
2. 用户问题
程序员在开发程序时往往在表示集合的数据结构上花费好多时间，而且自己开发的集合结构不规范，功能不全面，有一套现成的处理集合的数据结构能大大提高开发速度和软件质量。
回页首
3. 简单分析
通用的集合数据结构有下列几种：
(1)set－保证成员唯一 , 支持数学中的集合操作，如交、并；
(2)list－支持成员顺序，提供按索引访问成员；
(3)Map－成员为键值对，提供按键对象查找值对象；
(4)bag－保留成员个数，能查询成员的数量；
(5)queue- 支持先进先出，能扩展为按优先级操作；
(6)stack- 支持后进先出。
回页首
4. 使用界面
回页首
4.1.J2dk 集合框架介绍
《 Jdk1.4 集合框架主体结构图》显示了 J2sdk 集合框架类结构。J2sdk 集合由 collection 接口牵头，Set、List 和 Map 承担主角，用数据结构 Tree,Array,Hash,Link 作为具体实现手段，组成了一个在功能和性能上相当不错的框架。整个框架由主体结构和辅助结构组成，主体结构形成了框架基础，辅助结构为使用框架提供了便利。
4.1.1. 主体结构
我们用下表来描述 j2sdk 的集合框架的主体结构：
| 接口 |
简述 |
实现 |
操作特性 |
成员要求 |
| Set |
成员不能重复 |
HashSet |
外部无序地遍历成员。 |
成员可为任意 Object 子类的对象，但如果覆盖了 equals 方法，同时注意修改 hashCode 方法。 |
| TreeSet |
外部有序地遍历成员； 附加实现了 SortedSet, 支持子集等要求顺序的操作 |
成员要求实现 caparable 接口，或者使用 Comparator 构造TreeSet。成员一般为同一类型。 |
| LinkedHashSet |
外部按成员的插入顺序遍历成员 |
成员与 HashSet 成员类似 |
| List |
提供基于索引的对成员的随机访问 |
ArrayList |
提供快速的基于索引的成员访问，对尾部成员的增加和删除支持较好 |
成员可为任意 Object 子类的对象 |
| LinkedList |
对列表中任何位置的成员的增加和删除支持较好，但对基于索引的成员访问支持性能较差 |
成员可为任意 Object 子类的对象 |
| Map |
保存键值对成员，基于键找值操作，compareTo 或 compare 方法对键排序 |
HashMap |
能满足用户对 Map 的通用需求 |
键成员可为任意 Object 子类的对象，但如果覆盖了 equals 方法，同时注意修改 hashCode 方法。 |
| TreeMap |
支持对键有序地遍历，使用时建议先用 HashMap 增加和删除成员，最后从 HashMap 生成 TreeMap； 附加实现了 SortedMap 接口，支持子 Map 等要求顺序的操作 |
键成员要求实现 caparable 接口，或者使用 Comparator 构造 TreeMap。键成员一般为同一类型。 |
| LinkedHashMap |
保留键的插入顺序，用 equals 方法检查键和值的相等性 |
成员可为任意 Object 子类的对象，但如果覆盖了 equals 方法，同时注意修改 hashCode 方法。 |
| IdentityHashMap |
使用 == 来检查键和值的相等性。 |
成员使用的是严格相等 |
| WeakHashMap |
其行为依赖于垃圾回收线程，没有绝对理由则少用 |
  |
4.1.2. 辅助结构
在 J2sdk 集合框架中，除了具体实现集合的接口和类外，还有一些操作和辅助类，包括一个 fa?ade 类，两个等值方法和两个比较接口。
-
facade 类── Collections 类
Collections 类包含了对框架中集合的普遍性操作 , 充当 fa?ade。这些操作都被实现为静态函数，分为几下几类：
- 最大最小函数，对于某个集合，寻找最大最小成员（或键成员），要求成员都必须实现 comparable 接口；
- 生成不可更改的 singleton 集合（singleton 集合为包含一个成员的集合）；
- 对 list 进行排序、重组、倒序操作；
- 对 list 进行填充、批量置换、和快速搜索操作；
- 对集合进行同步化，以便适应多线程环境；
- 对集合进行不可更改修饰，返回不可更改的集合视图。
-
等值方法一 ── equals(Object o) 方法
equals 方法实现了一个等价关系：
- 自反性 : 对于任何对象 x， x.equals(x) 必须返回 true；
- 对称性 : 对于任何对象 x 和 y, x.equals(y)==true 当切仅当 y.equals(x)==true；
- 传递性 : 对于任何对象 x,y,z，如果 x.equals(y)==true 和 y.equals(z)==true, 则 x.equals(z)==true；
- 一致性 : 对于任何对象 x 和 y，只要没有对 x,y 进行修改，多次的 x.equals(y) 调用应该返回相同的值；
- 对于任何 non-null 对象 x, x.equals(null)==false。
Object 类中这个方法被实现为严格相等，也就是如果比较的两个对象是同一对象，即 == 操作为 true，则返回 true。所以如果想在集合中搜索内容相等的成员对象或在 map 中获取内容相等的键映射的值，成员对象（或键对象）的类必须覆盖 equals(Object o) 方法。
-
等值方法二── hashCode() 方法
这个方法返回一个对象的 hash 代码，在 hashtable 数据结构实现的集合中，它决定了这个对象被放到哪个 bucket 中。而 equals 方法则是进一步到 bucket 寻找具体对象的依据。
为了 hashtable 数据结构能正常工作，hashCode 方法的通用协议是：equals 方法定为相等的两个对象的 hashCode（）返回的整数一定相同。只有这样才能在 hashtable 数据结构中找到这个对象。而 equals 方法定为不相等的两个对象的 hashCode（）返回的整数可以不相同，如果相同则为哈西冲突。所以尽量保证 equals 方法定为不相等的对象的 hashCode（）返回的整数不相同。
类 Object 实现的 hashCode 使用对象的内部地址转化为整数返回，使得 o1.equals(o2) 当且仅当 o1.hashCode（）== o2.hashCode()。
-
比较接口一──接口 Comparable
这个接口要求全序，也叫自然排序，实现了这个接口的类的 compareTo 称为自然比较方法。
Collections.sort 方法能对一个实现了这个接口的类的对象的列表自动排序。在没有指定 comparator 的情况下，这样的对象同时也能作为排序 map 的键或排序 set 的成员。
如果一个类的任意两个实例 e1 和 e2，(e1.compareTo((Object)e2) == 0) 和 e1.equals((Object)e2) 有同样的逻辑值，我们就说这个类的自然排序和 equals 方法一致。另外 e1.compareTo(null) 应该抛出 NullPointerException。
强烈要求保持这种一致性，否则没有显示指定 comparator 的排序 set（或 map）将会破坏 set ( 或 map) 的普遍接口协议，因为这些接口协议用 equals 方法决定成员身份。
compareTo 方法的协议为：
- 当 e1 < e2 时 (e1.compareTo((Object)e2) <0;
- 当 e1 > e2 时 (e1.compareTo((Object)e2) 〉 0；
- 当 e1.equals(e2) 时 (e1.compareTo((Object)e2) ==0
- 当两个对象无法比较时，应该抛出 ClassCastException 异常。
在 j2sdk1.4 中，下面的类实现了这个接口：
BigDecimal, BigInteger, Byte, ByteBuffer, Character, CharBuffer, Charset, CollationKey, Date, Double, DoubleBuffer, File, Float, FloatBuffer, IntBuffer, Integer, Long, LongBuffer, ObjectStreamField, Short, ShortBuffer, String, URI。
-
比较接口二──接口 Comparator
这个接口对一个集合的对象作全序排序，实现了这个接口的类的对象能在 Collections.sort 方法、TreeSet 和 TreeMap 等数据结构中控制排序结果。
对于一个集合中的成员来说，一个 Comparator 对象和 equals 一致，当且只当这个对象的方法 compare 对于任意两个成员 e1 和 e2， (compare((Object)e1, (Object)e2)==0) 和 e1.equals((Object)e2) 有同样的逻辑值。和 Comparable 接口一样，强烈要求保持这种一致性。
Compare 方法的协议为：
- 当 e1 < e2 时 compare((Object)e1, (Object)e2)<0;
- 当 e1 > e2 时 compare((Object)e1, (Object)e2) 〉 0；
- 当 e1.equals(e2) 时 compare((Object)e1, (Object)e2)==0
- 当两个对象无法比较时，应该抛出 ClassCastException 异常。
在 j2sdk1.4 中，下面的类实现了这个接口：
Collator
回页首
4.2. 通用集合介绍
通用集合开源项目 commons-collection 是对 j2sdk 集合框架的扩展和完善，实现了普遍的编程需求。
4.2.1.bag 集合
bag 是 commons-collection 对 j2sdk 集合框架的一个扩展。与 j2sdk 集合框架中 set 集合不同的是，bag 允许成员重复，所以就增加了一些额外的操作。bag 的成员应是同一数据类型，它为每个成员登记数量，使用对象的 hashCode 判断相等性。 假如有一个包含 {a, a, b, c} 的 bag 集合，调用 getCount（a） 将返回 2，调用 uniqueSet 将得到 {a, b, c}。
下图是 bag 的类层次图：
比起 jsdk 集合框架中 set 来，bag 目前缺少 LinkedHashBag 实现，其它类特性相似。
4.2.2.List 集合
《通用集合之 List 》图显示了 commons-collection 对 j2sdk 集合框架的另一个完善。FastArrayList 是对 java.util.ArrayList 的进一步定制，目的在于多线程环境，在那里，多数方法调用不破坏对象。当 FastArrayList 对象最初创建时处于"slow"状态，这个状态下的任何方法都被同步，在对象进入"fast"状态后，对对象的读取调用不被同步，而破坏性调用执行下列步骤：
- 复制现成的集合；
- 在复制品上执行修改操作；
- 用复制品覆盖现成的集合。
当程序运行在单线程环境下，我们应该直接使用 java.util.ArrayList。
CursorableLinkedList 对 List 接口的双链实现，实现了 List 接口的所有可选操作，包括 LinkedList 中的 stack/queue/dequeue 操作和支持 ListIterator, 允许对 List 的并发修改。
CursorableSubList 是个内部类。
4.2.3.Map 集合
《通用集合之 Map 》图显示了 commons-collection 对 jsdk 集合框架的扩展 , 真可以说是庞大阵容。
首先是 HashMap 和 TreeMap 的 fast 版，关于 fast 版的特性可以参见前面的 FastArrayList 的说明。
BeanMap 是个很有意思的 Map, 它利用 java Bean 的属性反射功能，把一个 Java Bean 变成一个 Map 来操作，例如一个具有 name 属性的 Bean 构造的 BeanMap，可以使用 beanMap.get("name") 得到 bean 的 name 属性值。
ReferenceMap 是一个基于 Hashtablede 的 Map 实现，允许垃圾回收线程回收键值映射。在创建 ReferenceMap 对象时可以指定键或值的引用种类（hard,soft 或者 weak）, 当用非 hard 引用创建集合后，当键或值不可到达时垃圾回收线程可能回收这些键或值对象。当键的引用种类为"weak"， 值的引用种类为"hard"时，ReferenceMap 的行为类似 j2sdk 集合框架中的 WeakHashMap. ReferenceMap 缺省构造其采用"hard"引用的键和"soft"引用的值。SoftRefHashMap 被缺省构造的 ReferenceMap 取代。
MultiHashMap 实现了 MultiMap 接口。 MultiMap 与普通 Map 意义上稍微有区别，它提供的键值映射中值为一个集合。比如执行 put( key, new Integer(1) ) 后执行 Object get( key ) 将得到一个整数的集合。 也就是说，这个类不会覆盖先前的同一键所对应的值对象，而是把新值对象加到键所对应的值对象集合中。
DoubleOrderedMap 是一个 Map 接口的红 - 黑树实现。这个类保证键对象和值对象的双排序。这个类对于需要通过键对象或值对象查找键 - 值对的程序非常有效，而普通的 Map 实现只能通过键对象查键 - 值对。虽然同样的目的能用一对 TreeMaps 实现（containsKey 方法由键值 TreeMaps 实现，containsValue 方法由另一个值键 TreeMaps 实现），它在两个 TreeMaps 的数据同步上很容易出现问题，而且冗余数据比较大。红 - 黑树实现的 DoubleOrderedMap 则很容易地同步数据，而且使得冗余最小。这个类对数据成员有些限制：如果一个值或键已经存在于 DoubleOrderedMap 对象中，再试图保存这个值或键会抛出 IllegalArgumentException 异常。这个类的方法返回的 Map.Entry 实例不允许调用 setValue() 方法。为了顺利操作 DoubleOrderedMap 对象，这个类新增加的方法如下 ：
- Object getKeyForValue(Object value) 是普通 Map 的 get 方法的对立面，它从值找键 。
- Object removeValue(Object value) 寻找和删除指定的值对象，并返回这个值对象对应的键对象，同时这个键对象在 DoubleOrderedMap 对象不存在了。
- Set entrySetByValue() 返回一个值对象排序的 Map.Entry 集合。
- Set keySetByValue() 返回一个键对象排序的 Map.Entry 集合。
- Collection valuesByValue() 返回一个值对象排序的值对象集合。
ProxyMap 是一个 对 map 实现的 wrapper, 它的 Map 方法都直接调用了被 wrap 的 Map. 这个类一般用作扩展现存 Map 实现的扩展框架，这些扩展通过继承的方法不太方便。
SequencedHashMap 是一个按照键值对插入顺序序列化的 Map 实现，它具有类似于 List 的操作接口，除了具有 getFirst,getLast 方法访问头尾成员之外 , 甚至还可以基于索引随机访问键和值对象。 这点是 j2sdk 集合框架中的 LinkedHashMap 没有的特性。
LRUMap 是 SequencedHashMap 的子类，具有最大尺寸。集合中的成员数达到最大尺寸时，采用最近最少使用算法排除成员。所有的对某个键对象（不管是 get 还是 put）的操作都会使其移到前端。
我们要介绍的最后一个 Map 是 StaticBucketMap。这个类实现了一个多线程环境下使用的 hashmap, 但是这个类的桶数在构造函数中指定，而且后来也不会变化。对于每个桶都有独立的并发访问监视器 (monitor), 所以多个线程可以同时访问不同的桶。这个类本身就是线程安全的，不需要 Collections.synchronizedMap(Map) 方法得到同步版。使用这个类时要注意的是多线程环境下批量操作结果的不确定性。
4.2.4.buffer 集合
《通用集合之 buffer 》图显示了 commons-collections 对 j2sdk 集合框架扩展的另一个概念实现－buffer 集合。
ArrayStack 是扩展了 ArrayList 而实现的栈 API，在单线程下操作比较合适。 一个 ArrayStack 对象中成员的删除顺序基于其插入顺序：最近插入的最先删除，而其 iterator 则是按插入序访问成员。
BoundedFifoBuffer 类的对象代表一个具有固定大小的缓冲，成员的删除顺序和他们的插入顺序一致，即"先进先出"。可以通过下列函数获得同步版的 BoundedFifoBuffer 类对象： Buffer fifo = BufferUtils.synchronizedBuffer(new BoundedFifoBuffer());
UnboundedFifoBuffer 是和 BoundedFifoBuffer 类相同功能，但是缓冲尺寸可以在运行时扩充。同样可以通过 BufferUtils 获得其对象的同步对象：Buffer fifo = BufferUtils.synchronizedBuffer(new UnboundedFifo());
BinaryHeap 是一个对 PriorityQueue 和 Buffer 的二叉堆实现。删除操作 删除的是堆顶的成员（最小成员或最大成员），而 iterator 的成员访问顺序不定。可以通过 BufferUtils 获得其对象的同步对象： Buffer heap = BufferUtils.synchronizedBuffer(new BinaryHeap());
SynchronizedPriorityQueue 是一个线程安全的 PriorityQueue 类的包装，方法都是对被包装类的方法的多线程安全装饰。
回页首
4.3. 应用编程接口
下图展示了各种集合的应用编程接口，另外的接口还有各种 iterator、utils 类和具体实现的类的扩充接口，请参见相关文档。
了解集合编程接口的最好方法是看文档，特别是仔细看看这些接口函数对集合的影响和返回值。
回页首
4.4. 例子
4.4.1. 素材
为了演示集合的使用，我们先准备两个成员对象类和一个 Comparator 实现。下表描述了两个成员对象类对集合框架中辅助结构的实现情况（注意 equals 方法和 hashCode 方法必须符合上面辅助结构一节描述的关系）：
| 类名 |
equals 方法和 hashCode 方法 |
| MyBean |
没覆盖 |
| MyBean_Comparable |
覆盖 |
| MyBeanComparator |
实现两个对象的排序算法，用于 Tree 结构实现的集合 |
MyBean 代码如下：
public class MyBean {
private String name;
public MyBean(String name){
this.name = name;
}
public MyBean(){
super();
}
public String getName() {
return name;
}
public void setName(String string) {
name = string;
}
}
|
MyBean_Comparable 代码如下：
public class MyBean_Comparable implements Comparable {
private String name;
public MyBean_Comparable() {
super();
}
public MyBean_Comparable(String name){
this.name = name;
}
public String getName() {
return name;
}
public void setName(String string) {
name = string;
}
public int hashCode() {
return name.hashCode();
}
public boolean equals(Object arg0) {
try {
MyBean_Comparable pt1 = (MyBean_Comparable) arg0;
return getName().equals(pt1.getName()) ;
} catch (ClassCastException e) {
return false;
}
}
public int compareTo(Object arg0) {
try {
MyBean_Comparable pt1 = (MyBean_Comparable) arg0;
return getName().compareTo(pt1.getName()) ;
}catch (ClassCastException e) {
return 0;
}
}
}
|
MyBeanComparator 类实现了 Comparator 接口：
public class MyBeanComparator implements Comparator {
public int compare(Object e1,Object e2){
try {
MyBean pt1 = (MyBean) e1;
MyBean pt2 = (MyBean) e2;
return pt1.getName().compareTo(pt2.getName()) ;
} catch (ClassCastException e) {
return 0;
}
}
}
|
4.4.2. 例子
例子代码主要体现了框架中集合的主要特性，内容如下：
import java.util.Collection;
import java.util.HashMap;
import java.util.IdentityHashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import org.apache.commons.collections.Bag;
import org.apache.commons.collections.FastArrayList;
import org.apache.commons.collections.HashBag;
import org.apache.commons.collections.TreeBag;
public class CollectionTest {
public static void main(String args[]) {
// 实验一
System.out.println("测试 bag 的特性");
testCount();
// 实验二
System.out.println("测试 comparator 接口");
testComparator();
// 实验三
System.out.println("测试成员的引用性");
testReference ();
// 实验四
System.out.println("不可改变的集合的含义");
testUnmodified();
// 实验五
System.out.println("测试 fastarraylist 的特性");
testFastList();
// 实验六
System.out.println("IdentityHashMap 的严格相等性");
testIdentityHashMap();
}
/**
* 主要显示：
* 1、Hash 结构实现的集合可以包含任意成员；
* 2、Bag 保留成员的数目；
*/
private static void testCount(){
Bag baghash = new HashBag();
baghash.add(new MyBean("MyBean"));
baghash.add(new MyBean("MyBean"));
baghash.add(new MyBean_Comparable("MyBean_Comparable1"));
baghash.add(new MyBean_Comparable("MyBean_Comparable1"));
baghash.add(new MyBean_Comparable("MyBean_Comparable2"));
System.out.println("testCount(HashBag) = " + baghash);
}
/**
* 主要显示 Comparator 得编写和 treebag 得顺序特性
*
*/
private static void testComparator(){
int i = 0;
Bag bagtree = new TreeBag(new MyBeanComparator());
bagtree.add( new MyBean("second"));
bagtree.add( new MyBean("first"));
bagtree.add( new MyBean("first"));
Iterator iterator = bagtree.iterator();
while (iterator.hasNext()) {
MyBean element = (MyBean) iterator.next();
System.out.println("testComparator(TreeBag) = " + element);
}
iterator = bagtree.iterator();
while (iterator.hasNext()) {
MyBean element = (MyBean) iterator.next();
element.setName("name" + i++);
System.out.println("testComparator(TreeBag) = " + element.getName());
}
iterator = bagtree.iterator();
while (iterator.hasNext()) {
MyBean element = (MyBean) iterator.next();
System.out.println("testComparator(TreeBag) = " + element);
System.out.println("testComparator(TreeBag) = " + element.getName());
}
System.out.println("testComparator(TreeBag) = " + bagtree);
}
/**
* 主要显示集合保留引用的特性
*
*/
private static void testReference (){
Bag bagtree = new TreeBag(new MyBeanComparator());
My
分享到：
Global site tag (gtag.js) - Google Analytics
|
相关推荐
java高级编程 集合介绍 bag 集合 List集合 Map集合 buffer集合 实例
java 操作文件通用方法集合,很实用的方法
java技巧，循环遍历集合，很方便的，是个通用的技巧。java中可以用来循环遍历任何一个集合的通用方法
Lambda表达式、扩展方法与通用集合运算符 理工大学仅需梁老师的课件
精选年终工作总结集合9篇_最新范文_通用模板.docx精选年终工作总结集合9篇_最新范文_通用模板.docx精选年终工作总结集合9篇_最新范文_通用模板.docx精选年终工作总结集合9篇_最新范文_通用模板.docx精选年终工作总结...
精选年终工作总结集合9篇_最新范文_通用模板.pdf精选年终工作总结集合9篇_最新范文_通用模板.pdf精选年终工作总结集合9篇_最新范文_通用模板.pdf精选年终工作总结集合9篇_最新范文_通用模板.pdf精选年终工作总结集合...
C# 各种通用类集合【技术文档】 MyHelper-master.zip MyHelper4Web API.chm ASP.NET中常用的33种代码 (C#版).txt
本实例可以把多个不同对象集合或者一个对象集合的数据导出到Excel表格中，能实现最大通用化。
幼儿园区角教案——食品大集合（通用）.doc
有关医生述职报告集合（通用16篇）.docx
CFD通用软件集合综述.rar
全国通用2016版高考数学大二轮总复习增分策略专题一集合与常用逻辑用语不等式第1讲集合与常用逻辑用语试题
JAVA时间集合类 一些通过的时间类.很常用哦
高三一轮测试文1集合与简易逻辑通用版精选.doc
C 语言通用 List 集合.zip
高三一轮测试理1集合与简易逻辑1通用版精选.doc
通用技术知识概念集合.doc
iOS开发 通用Utilities类 工具函数集合
通用实习总结集合9篇.doc