Java容器介绍

 

概念分类

   Java 2将容器分为两个不同的概念: Collection 与Map

   Collection: 提供对一组各自独立的元素的集合，List 与 Set接口都继承自Collection接口。

   Map：提供了一组key-value(键值对)。

 

  两种类型的主要区别在于:

   Collection类型每个位置只持有一个元素(Object),比如List以加入到容器中的先后顺序来持有一个独立的的对象。Set中的对象不得重复，并且它会使用自己内部的一种排序机制。

Map类型所持有的是key-value(键值对)，Map不接受重复的key。

 

容器分类

   Java的所有容器类都实现了来自于List, Set, Map三种接口中的一个。我们可以通过Think in Java里面的类图来观察他们之间的关系： 

 

 

 

List

  List定义了一个线性表接口，Java2中的List实现方式分为两种：

ArrayList 是以array(数组)实现的线性表数据结构，其get(int index)方法的时间复杂度为O(1)。而其插入与删除操作的元素在中央时，其效率较低。因为每次都要对插入或删除位置(index)后面的array的进行数组拷贝。

LinkedList 是一个双向链表数据结构。其插入与删除操作效率要明显高于ArrayList。

而且其随机查找的时间复杂度为O(n) (其实每次随机查找的次数要依赖于size/2到要查找的目标index之间的个数)其查找的效率要低于ArrayList的O(1)。

 

Set

  Set是集合类，该集合不能有“重复”对象存在，Java2中Set实现方式分成两种：

HashSet 将持有对象映射到在哈希表中。  (JDK1.6的内部实现是 HashSet只是个适配器，其将适配对象HashMap适配成了Set接口)

TreeSet 将持有对象放入RBTree（红黑树）中。(TreeSet也将适配对象TreeMap适配成了Set接口)

 

 Map

  Map是一组key-value(键值对)集合，其中的key(键)不能重复。

HashMap  用key对象生成hashcode然后映射到Entry<K,V>[]数组中(JDK1.6中其hashtable默认大小为16，在持有对象数量查过默认大小之后就会重新生成一个更大HashTable，然后将原有持有的对象逐个散列到新哈希表中)。其get(Object key) 最佳时间复杂度为O(1)，最坏则为O(n)。但就查找的平均效率来说是要高于TreeMap。

TreeMap  用key对象为关键值存放在RBTree（红黑树）中。其get(Object key)方法的平均时间复杂度为O(logn)。

 

Iterator

  Iterator迭代器实现对: 哈希表HashMap，红黑树TreeMap，链表LinkedList，动态数组ArrayList等数据结构的迭代。

 

所有实现了Collection接口对象都可以获得一个Iterator对象用来遍历自己的所持有的对象。而现实了Map接口的对象都是以key-value(键值对)形式存放的，所以在遍历时需要将对象转换成Collection或者Set来实现，Map接口中定义了以下几个方法将自己内部的值转换成Collection或者Set：

1.       Collection<V> values() 生成一个只包含value(值)的Collection。

2.       Set<Map.Entry<K,V>> entrySet() 生成了一个包含key-value(键值对)的集合。

3.       Set<K> keySet() 生成一个只包含key的集合。

 

获得了Collection或Set之后使用Iterator<E> iterator()方法就可以获得迭代器了。Iterator的使用这里就不再多说了。

 

总结一下：

lArrayList与LinkedList效率比较

  ArrayList查找操作的效率最高为，但其在添加和删除操作时需要拷贝数组所以效率较低，尤其是删除操作。该数据结构适用于需要频繁快速查找的地方。

  LinkList 查找操作效率较低为，但其插入与删除操作效率较高，适用于需要频繁进行插入删除操作的情况。

以下测试数据来源于Think in Java

Type       GET   Iteration  Insert  Remove

ArrayList    281     1375        328     30484

LinkedLIst  5828   1047        109       16

 

HashSet和TreeSet就不介绍了，因为他们就是用HashMap和TreeMap实现的，可以直接参考下面的比较。

 

lHashMap与TreeMap效率比较

   HashMap 的查找、添加、删除的效率都要高于TreeMap。TreeMap存在是唯一理由就是它内部是一个树形结构存储结构，而Java中的其他的容器都是线性的(即arraylist,linkedlist)或者说是线性的扩展(hashmap)。

以下测试数据来源于Think in Java

          Type            Size    Put    Get     Iterator

         TreeMap      10    26.6     20.3    43.7

                             100   34.1     27.2    45.8

                             1000  27.8     29.3    8.8

        HashMap     10    21.9    18.8    60.9

100    21.9    18.6    63.3

1000   11.5    18.8    12.3