从提高存取效率的角度深入“集合框架”

 

 

在开始之前，我先提出问题引出整片的论述：

    问题：1、我们已经知道JDK提供的集合有很多种，我们应该通过哪些标准（比如执行效率等）来选取合适的集合使用？

             2、各种集合之间的关系到底是怎样的？

             3、各种集合的适用情况如何，即如何选取才能使你的程序的效率最高？

 下面，我就来试图解决这些问题！

 

一、基于图的集合框架整体认知

 

 

接口关系图详解：

 

 

更加详细的框架图见：http://hi.baidu.com/%C9%AE_%CC%C6/blog/item/9e2a8b0887008a8ad0581b3d.html

 

 

二、部分接口或类的分析

 

1、整个框架主要包括三大接口：

 

   java.util.Set 接口及其子类，set提供的是一个无序的集合。

   java.util.List 接口及其子类，List提供的是一个有序的集合

   java.util.Map 接口及其子类，Map提供了一个映射（对应）关系的结合数据结构。

   另外，在JDK5中新增了Queue（队列）接口及其子类，提供了基于队列的集合框架。并且，我们应该没有忘记自己最初是通过自定义数组和自定义队列来实现对象的集合存储的。

 

 

2、遍历问题：

 

   Collection类的遍历使用iterator()方法。所以，所有实现它的类都可以使用这个方法来达到遍历。

   List提供了一个listIterator()方法，返回一个ListIterator接口，和标准的Iterator接口相比，ListIterator多了一些add()之类的方法，允许添加、删除、设定元素，还能向前向后遍历。可以说ListIterator是Iterator的升级版。

   遍历HashMap：

 

            方法一：  用entrySet()

           Iterator it=map.entrySet().iterator();

           while(it.hasNext()){

                Map.Entry entry=(Map.Entry)it.next(); 

           }

 

            方法二：应用for-Each+keySet()循环：

            for(Object o:map.keySet){

                    Value value=map.get(o);

             }

 

             方法三：用entrySet()和or-Each循环

           for(Map.Entry<> m:map.entrySet()){

                 //m是映射项

            }

                    本方法同for(Map.Entry<> m:map){}（不过前提是所有的<>中类型都要指定）

 

            方法四：用keySet()

            Iterator it=map.keySet().iterator();

           while(it.hasNext()){

                String key=(keyType)it.next();

                Value value=map.get(key); 

           }

 

方法一比方法四效率高，因为对keySet其实是遍历了两次，一次是转为iterator，一次就是取出key对应的value，而entrySet只遍历了一次。

 

    

3、接口及其实现类（本条相关论述详见JDK文档）：本条的论述主要涉及同步问题，方法的时间开销，容量等问题。

 

   Collection接口：允许参数为Collection的构造器，实际上就是实现用户复制一个Collection。

   

     SortedSet<E>接口：继承自Set接口，使用自然顺序进行排序，或者在创建有序set是提供的Comparator进行排序。该set的迭代器将元素升序遍历set。

   

   HashSet<E>类：应用HashMap的一个集的实现。固然集定义成无序，但必须存在某种方法能相当高效地找到一个对象。应用一个HashMap对象实现集的存储和检索把持是在固定时间内实现的.   

 

 

    LinkedList类：提供了get，remove，insert的额外的方法，实现在LinkedList首部或尾部作用。这些操作时LinkedList可悲用作堆栈(Stack)、队列(queue)、或双向队列(deque)。

    注意LinkedList没有同步方法。如果多个线程同时访问一个List，则必须自己实现访问同步。一种解决方法是在创建List时构造一个同步的List：  
　　List  list  =  Collections.synchronizedList(new  LinkedList(...));   

 

 

    ArrayList类：size，isEmpty，get，set方法运行时间为常数。但是add方法开销为分摊的常数，添加n个元素需要O(n)的时间。其他的方法运行时间为线性。 

当需要插入大量元素时，在插入前可以调用ensureCapacity方法来增加ArrayList的容量以提高插入效率。  

 同样，该类unsynchronized。

 

     Vector类：实现了List接口。synchronized。当一个Interator被创建而且正在被使用，另一个线改变了Vector的状态，这是调用Iterator的方法将抛出ConcurrentModificationException 。

 

　   

         Stack类：继承自Vector，实现一个后进先出的堆栈。 

 

    

    Map接口：Map接口提供3种集合的视图，Map的内容可以被当作一组key集合，一组value集合，或者一组key-value映射。   

 

 

     HashMap类：unsynchronized。允许null，即null vlaue和null key。但是将HashMap视为Collection时（values()方法可返回Collection），其迭代子操作时间开销和HashMap的容量成比例。因此，如果迭代操作的性能相当重要的话，不要将HashMap的初始化容量设得过高，或者load  factor过低。   

 

    

          Hashtable类 ：由于作为key的对象将通过计算其散列函数来确定与之对应的value的位置，因此任何作为key的对象都必须实现hashCode和equals方法。hashCode和equals方法继承自根类Object，如果你用自定义的类当作key的话，要相当小心，按照散列函数的定义，如果两个对象相同，即obj1.equals(obj2)=true，则它们的hashCode必须相同，但如果两个对象不同，则它们的hashCode不一定不同，如果两个不同对象的hashCode相同，这种现象称为冲突，冲突会导致操作哈希表的时间开销增大，所以尽量定义好的hashCode()方法，能加快哈希表的操作。  

　　如果相同的对象有不同的hashCode，对哈希表的操作会出现意想不到的结果（期待的get方法返回null），要避免这种问题，只需要牢记一条：要同时复写equals方法和hashCode方法，而不要只写其中一个。 

 

 

 

 本条小结：HashSet采用散列函数对元素进行排序，这是专门为快速查询而设计的；TreeSet采用红黑树的数据结构进行排序元素；LinkedHashSet内部使用散列以加快查询速度，同时使用链表维护元素的次序，使得看起来元素是以插入的顺序保存的。需要注意的是，生成自己的类时，Set需要维护元素的存储顺序，因此要实现Comparable接口并定义compareTo()方法。 如果涉及到堆栈，队列等操作，应该考虑用List，对于需要快速插入，删除元素，应该使用LinkedList，如果需要快速随机访问元素，应该使用ArrayList。 

 

 

参考：http://dev.firnow.com/course/3_program/java/javajs/2007917/71621.html 

             

          

   

三、扩展

 

1、散列表（也叫哈希表）：从哈希表的优势入手

    数据结构中，有个时间算法复杂度O(n)的概念来衡量某种算法在时间效率上的优劣。哈希表的理想算法复杂度为O(1)，也就是说利用哈希表查找某个值，系统所使用的时间在理想情况下为定值，这就是它的优势。那么哈希表是如何做到这一点的呢？
    实际生活中有这样一个mapping需要存储：name-value。存储和读取整个流程为：

    A、开辟一块空间(HashValues[m])用于存储value;

B、通过哈希函数(ChangeToHashValue (name))计算出name的哈希码hashcode(name)=x.

C、将value存储到hachValues[x]中。到这里存储就完毕了。

D、读取时，给定name，通过哈希函数(ChangeToHashValue (name))计算出哈码hashcode(name)=x

E、读取HashValue [x]

 

不过，实际上m总是大于实际需要的n的，所以这其实是用空间换时间的数据结构。

 

不过，哈希表的方法也会遇到问题：

当两个不同的name值经过哈希函数的计算结构得到的哈希值相同，那么就会出现冲突。冲突使得哈希表的存取速度变慢。解决方法有两种：一种就是定义一个好的哈希函数；另一种就是在不改变哈希函数的情况下用后续的手段解决冲突，如出现重复hashcode加1等等。

 

 

2、HashSet 而言，它是基于 HashMap 实现的，HashSet 底层采用 HashMap 来保存所有元素 

 

   当我们试图把某个类的对象当成 HashMap 的 key，或试图将这个类的对象放入 HashSet 中保存时，重写该类的 equals(Object obj) 方法和 hashCode() 方法很重要，而且这两个方法的返回值必须保持一致：当该类的两个的 hashCode() 返回值相同时，它们通过 equals() 方法比较也应该返回 true。通常来说，所有参与计算 hashCode() 返回值的关键属性，都应该用于作为 equals() 比较的标准。 

1     // 根据 first 判断两个 Name 是否相等 

2     public boolean equals(Object o)   

3     {   

4         if (this == o)   

5         {   

6             return true;   

7         }   

8         if (o.getClass() == Name.class)   

9         {   

10             Name n = (Name)o;   

11             return n.first.equals(first);   

12         }   

13         return false;   

14     }   

15        

16     // 根据 first 计算 Name 对象的 hashCode() 返回值  

17     public int hashCode()   

18     {   

19         return first.hashCode();   

20     }  

 

四、最后的总结：

 

1、集合框架中各个类的使用需要考虑空间占用率（容量，通过loadFactor 属性来设置）、同步问题、是否可以存入null值、各种类的区别与选择、遍历选择等问题。这些问题，在我上面的论述中多多少少有涉及，其中各个类的区别、是否存入null值、同步问题、以及部分类空间占用等问题我只是做了一个引入式的分析，并没有分析到能应用的层面。这点是还可以进一步研究的地方。