java容器

l概念分类

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

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

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

 

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

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

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

 

l容器分类

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

 

 

 

 

 

 

lList

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

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

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

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

 

lSet

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

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

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

 

l 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)。

 

l Iterator

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

所有的Collection都可以获得一个Iterator对象用来遍历自己的所持有的对象。