内容


集合与通用集合

Comments

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 的类层次图:

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 集合框架的扩展 , 真可以说是庞大阵容。

通用集合之 Map

首先是 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 集合

《通用集合之 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 值的处理。


相关主题


评论

添加或订阅评论,请先登录注册

static.content.url=http://www.ibm.com/developerworks/js/artrating/
SITE_ID=10
Zone=Java technology
ArticleID=52905
ArticleTitle=集合与通用集合
publish-date=07112003