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里面的类图来观察他们之间的关系：  

 

 

 

 

 

 

l List

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

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

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

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

 

l Set

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 对象用来遍历自己的所持有的对象。

 

 

 

--------------------------------------------------------------------------------------------------
我们的淘客网开通啦，欢迎大家去逛逛 ~\( ≧▽≦ )/~ 啦啦啦 ~~~
淘宝购物资讯网： http://taoke178.jimdo.com

淘乐园： http://taoleyuan.jimdo.com