`

集合与通用集合

    博客分类:
  • Java
阅读更多

URL: http://www.ibm.com/developerworks/cn/java/l-collection/

 

 

级别: 初级

龚永生 (gongys@lenovo.com),

2003 年 7 月 11 日

本文描述了Jakarta项目commons-collection,其当前版本是2.1版。本文对j2sdk集合框架的整理和例子示例可以大大加快程序员熟悉和使用集合,文中的例子虽然没有覆盖所有的接口但却显示了集合主要概念的使用方法。遗留问题和总结部分可以进一步加深读者对整个集合框架的理解,促进对commons-collection的使用和开发。

<!--START RESERVED FOR FUTURE USE INCLUDE FILES--><!-- include java script once we verify teams wants to use this and it will work on dbcs and cyrillic characters --><!--END RESERVED FOR FUTURE USE INCLUDE FILES-->

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 其行为依赖于垃圾回收线程,没有绝对理由则少用 &#160

4.1.2.辅助结构

在J2sdk集合框架中,除了具体实现集合的接口和类外,还有一些操作和辅助类,包括一个fa?ade类,两个等值方法和两个比较接口。

  • facade类──Collections类

    Collections类包含了对框架中集合的普遍性操作,充当fa?ade。这些操作都被实现为静态函数,分为几下几类:

    1. 最大最小函数,对于某个集合,寻找最大最小成员(或键成员),要求成员都必须实现comparable接口;
    2. 生成不可更改的singleton集合(singleton集合为包含一个成员的集合);
    3. 对list进行排序、重组、倒序操作;
    4. 对list进行填充、批量置换、和快速搜索操作;
    5. 对集合进行同步化,以便适应多线程环境;
    6. 对集合进行不可更改修饰,返回不可更改的集合视图。

     

  • 等值方法一 ──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方法的协议为:

    1. 当e1 < e2 时(e1.compareTo((Object)e2) <0;
    2. 当e1 > e2 时(e1.compareTo((Object)e2)〉0;
    3. 当e1.equals(e2) 时(e1.compareTo((Object)e2) ==0
    4. 当两个对象无法比较时,应该抛出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方法的协议为:

    1. 当e1 < e2 时compare((Object)e1, (Object)e2)<0;
    2. 当e1 > e2 时compare((Object)e1, (Object)e2)〉0;
    3. 当e1.equals(e2) 时compare((Object)e1, (Object)e2)==0
    4. 当两个对象无法比较时,应该抛出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"状态后,对对象的读取调用不被同步,而破坏性调用执行下列步骤:

  1. 复制现成的集合;
  2. 在复制品上执行修改操作;
  3. 用复制品覆盖现成的集合。

 

当程序运行在单线程环境下,我们应该直接使用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对象,这个类新增加的方法如下 :

  1. Object getKeyForValue(Object value) 是普通Map的 get方法的对立面,它从值找键 。
  2. Object removeValue(Object value) 寻找和删除指定的值对象,并返回这个值对象对应的键对象,同时这个键对象在DoubleOrderedMap对象不存在了。
  3. Set entrySetByValue() 返回一个值对象排序的Map.Entry集合。
  4. Set keySetByValue()返回一个键对象排序的Map.Entry集合。
  5. 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());
		MyBean myBean = new MyBean("before");
		bagtree.add(myBean);
		System.out.println("testReference(bagtree) = " + bagtree);
		Iterator iterator = bagtree.iterator();
			
		while (iterator.hasNext()) {
			MyBean element = (MyBean) iterator.next();
			System.out.println("testReference(bagtree) = " + element.getName());
			element.setName("after");
		}	
		
		iterator = bagtree.iterator();
			
		while (iterator.hasNext()) {	
			MyBean element = (MyBean) iterator.next();
			System.out.println("testReference(bagtree) = " + element.getName());
		}	
		
		System.out.println("testReference(bagtree) = " + bagtree);
	}		
	
	
	/**		
	* 主要显示不可改变的集合的含义		
	*		
	*/		
		
	private static void testUnmodified(){
		Bag baghash = new HashBag();
		baghash.add(new MyBean("first"));
		baghash.add(new MyBean("first"));
		int i = 0;
		Collection c = java.util.Collections.unmodifiableCollection(baghash);
		try{
			c.add(new MyBean("third"));
		}catch(UnsupportedOperationException e){	
			System.out.println("testUnmodified: yes it cannot be modified!");
		}	
		
		Iterator iterator = c.iterator();
			
		while (iterator.hasNext()) {	
			MyBean element = (MyBean) iterator.next();
			System.out.println("testUnmodified(before) = " + element.getName());
			element.setName("forth" + i++);
		}	
		
		iterator = c.iterator();
			
		while (iterator.hasNext()) {	
			MyBean element = (MyBean) iterator.next();
			System.out.println("testUnmodified(after) = " + element.getName());
		}			
		
	}	
	
	
	/**	 
	* 测试fastarraylist的特性	 
	*/	
		
	private static void testFastList(){
		arraylist(1000);
		fastlist_slow(1000);
		fastlist_fast(1000);
	}	
	
	private static void arraylist(int accounts){
		List list = new ArrayList();
		long start;
		long end;
		start = System.currentTimeMillis();
		
		for(int i =0;i<accounts;i++){	
			list.add(new MyBean(""+i));
		}	
		
		for(int i =0;i<accounts;i++){	
			list.get(i);
		}
		
		for(int i =0;i<2;i++){
			list.remove(list.size()-1);
		}
		
		end = System.currentTimeMillis();
		System.out.println("arraylist:" + (start-end));
	}	
	
	private static void fastlist_slow(int accounts){
		List list = new FastArrayList();
		long start;
		long end;
		start = System.currentTimeMillis();
		
		for(int i =0;i<accounts;i++){	
			list.add(new MyBean(""+i));
		}	
		
		for(int i =0;i<accounts;i++){	
			list.get(i);
		}	
		
		for(int i =0;i<2;i++){		
			list.remove(list.size()-1);
		}		
		
		end = System.currentTimeMillis();
		
		System.out.println("fastlist_slow:" + (start-end));
	}	
	
	
	private static void fastlist_fast(int accounts){
		List list = new FastArrayList();
		long start;
		long end;
		start = System.currentTimeMillis();
		
		for(int i =0;i<accounts;i++){
			list.add(new MyBean(""+i));
		}
		
		((FastArrayList)list).setFast(true);
		
		for(int i =0;i<accounts;i++){	
			list.get(i);
		}	
		
		for(int i =0;i<2;i++){	
			list.remove(list.size()-1);
		}		
		
		end = System.currentTimeMillis();
		System.out.println("fastlist_fast:" + (start-end));
	}	
	
	
	/**	
	* 主要显示IdentityHashMap的严格相等性	 
	*	
	*/	
		
	private static void testIdentityHashMap(){	
		Map map1 = new IdentityHashMap();
		String key = new String("first");
		String key2 = new String("first");
		map1.put(key, new MyBean("first"));
		System.out.println("IdentityHashMap:"+map1.containsKey(key));
		System.out.println("IdentityHashMap:"+map1.containsKey(key2));
		Map map2 = new HashMap();
		map2.put(key,  new MyBean("first"));
		System.out.println("HashMap"+map2.containsKey(key));
		System.out.println("HashMap"+map2.containsKey(key2));
	}
}

 

这个例子代码不仅让我们了解通用集合实现中bag集合的特性,而且还让我们了解了整个集合框架的重要结构。

  • 实验一──测试bag的特性

    输出结果如下:

    testCount(HashBag) = 
    [2:MyBean_Comparable@123d5a54,1:MyBean_Comparable@123d5a55,1:MyBean@13e8d89,1:MyBean@b8df17]
    

    表明这个Bag中有3个 MyBean_Comparable对象,其中两个相同;另外还有两个不同的MyBean对象。

    从试验素材中知道MyBean没有覆盖equals和hashcode方法,所以继承了Object的严格相等,所以加入bag集合中的两个MyBean对象虽然名字相同,但却是两个内存地址不同的对象,所以bag认为它们不相等。另一方面,虽然3个MyBean_Comparable对象也不严格相等,但是MyBean_Comparable类覆盖了equals和hashcode方法,使得只要两个对象的名字相等,bag就认为它们相等。

  • 实验二──测试comparator接口

    输出结果如下:

    testComparator(TreeBag) = first
    testComparator(TreeBag) = second
    testComparator(TreeBag) = second
    testComparator(TreeBag) = 
    [1:MyBean@10385c1,2:MyBean@42719c]
    

    虽然名为second的MyBean对象比first 的对象早插入,但输出却在其后,表明Tree数据结构实现的TreeBag是按照顺序保存成员对象的。另外我们在实验当中往TreeBag中加入了一个名为third的MyBean_Comparable对象,当这里却显示成名为second的MyBean对象,这是由于我们实现的Comparator的compare方法对不是MyBean类的对象统统返回相等的缘故。当名为third的MyBean_Comparable对象加入时,加入算法与第一个加入的对象比较得出它们两个相等,所以简单地在这个名为second的MyBean对象的计数上累加一,而且把MyBean_Comparable对象丢去了。

    从本试验还可得出:bag对认为是相等的对象只保留一个副本。

  • 试验三──测试成员的引用性

    输出结果如下:

    testReference(bagtree) = [1:MyBean@1e5e2c3]
    testReference(bagtree) = before
    testReference(bagtree) = after
    testReference(bagtree) = [1:MyBean@1e5e2c3]
    

    试验结果表明集合中保存的是对象的引用,因为修改成员对象之后体现在了集合中。

  • 实验四──不可改变的集合的含义

    输出结果如下:

    testUnmodified: yes it cannot be modified!
    testUnmodified(before) = first
    testUnmodified(before) = first
    testUnmodified(after) = forth0
    testUnmodified(after) = forth1
    

    结果表明Collections. unmodifiableCollection方法返回的集合确实不允许增减成员,但是不能避免成员被修改,这个与试验四体现的成员引用性有关联。

  • 实验五──测试fastarraylist的特性

    输出结果要依据所测试的成员数量决定。对于成员数量较大的集合,fast模式下的clone操作可能是一个性能瓶颈,使得性能有可能低于一直处于slow模式下的fastarraylist,但是fastarraylist的特性应该在多线程环境中才能较好体现。

  • 实验六──测试IdentityHashMap的严格相等性

    输出结果如下:

    IdentityHashMap:true
    IdentityHashMap:false
    HashMap:true
    HashMap:true
    

    表明IdentityHashMap对键成员的判断用的是严格相等含义,即两个键对象是同一内存对象时才相等,也就是说由同一个new操作产生。

 




回页首

 

5.内部剖析

commons-collection项目关注的主要是数据结构和算法,大家可以寻找相关的书籍来进一步了解源代码中的算法,本文不再冗述。

 




回页首

 

6.遗留问题

整体上来说commons-collection在多线程、集合类型、实现方法等方面对j2sdk集合框架的扩充还是比较完善的,如有特殊需求可以根据自己的需要扩充集合框架。比较明显的遗留问题就是commons-collection的实现代码上有部分函数没有遵循j2sdk集合框架协议,可能会导致代码行为上的不一致性。在设计上的问题可能就是不能遵循接口变成的原则,因为有些对某种接口的实现扩大了接口的范围,比如fastArrayList中的setFast方法在list接口中就没有,但是这个方法却是使用fastArrayList集合的关键方法。

 




回页首

 

7.总结

使用集合是我们经常遇到的编程问题,准确的理解j2sdk集合框架和commons-collection对此框架的扩展有助于提高我们的工作效率。使用这些集合类要注意它们在多线程环境下的表现和约束,关于多线程下的集合的例子可以到tomcat源码中寻找StandardSession对attribute集合的实现;另外一个重要的方面是按照自己的需求选择合适功能的集合类,因为功能的增加往往意味着性能的下降。如果j2sdk的集合类和commons-collection的集合类不能满足需要,读者也可以自己设计和实现,比如实现一个真正不可更改的集合。读者需要注意的另外一个问题是各个集合对null值的处理。

  • 大小: 29.6 KB
  • 大小: 9.5 KB
  • 大小: 7 KB
  • 大小: 21.9 KB
  • 大小: 12.3 KB
  • 大小: 29 KB
分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics