首页 > 代码库 > Java中各种集合问题

Java中各种集合问题

一,java种集合关系图

Collection                接口的接口                   对象的集合

--List          子接口 有序 可重复

  --LinkedList                接口实现类  链表  插入删除  没有同步  线程不安全

  --ArrayList                  接口实现类  数组  随机访问  没有同步  线程不安全

  --Vector                      接口实现类  数组               同步        线程安全

    --Stack

--Set                              子接口  仅接收一次,并做内部排序  不可重复

  --HashSet

    --LinkedHashSet

  --TreeSet

 

Map                       接口                            键值对的集合

--Hashtable            接口实现类  同步        线程安全     不可以储存null值

--HashMap                        接口实现类  没有同步   线程不安全  可以储存null值

  --LinkedHashMap

  --WeakHashMap

--TreeMap

--IdentifyHashMap

Map采用哈希散列,查找元素时比ArrayList快

二、详细介绍

1、List接口

  1.1 次序是List最重要的特点,能够用索引来访问元素,允许有相同元素;

  1.2 除了Collection接口必备的iterator()方法,List提供了一个listIterator()方法,允许添加删除,设定元素,向前向后遍历;

  LinkedList:对顺序访问进行了优化,随机访问相对较慢

  1.3 LinkedList允许null值,提供了addFirst(),getFirst()等方法在LinkedList的首部或尾部,使linkedList可被用作堆栈,队列或双向队列;

  1.4 LinkedList没有同步方法,如果多线程访问时,必须自己实现访问同步

    如  List list=Collection.synchronizedList(new LinkedList(...));

  ArrayList:向List中间插入与移除元素的速度很慢,随机访问相对较快

  1.5 ArrayList有数组实现,允许所有元素,包括null

  1.6  ListIterator 只应该用来由后向前遍历 ArrayList, 而不是用来插入和移除元素。因为那比 LinkedList 开销要大很多;

  Vector:

  1.7 由Vector创建的iterator被创建而且正在被使用,另一线程改变了vector的状态,这时调用 Iterator 的方法时将抛出 ConcurrentModificationException ,因此必须捕获该异常

  Stack:

  1.8 实现一个后进先出的堆栈,Stack 提供 5 个额外的方法使得 Vector 得以被当作堆栈使用。基本的 push 和 pop 方法,还有 peek 方法得到栈顶的元素, empty 方法测试堆栈是否为空, search 方法检测一个元素在堆栈中的位置。 Stack 刚创建后是空栈;

2 Set接口

  2.1 set不保证维护元素的次序,最多有一个null值;

  2.2 Set的构造函数有一个约束条件 ,传入的Collection参数不能包含重复的元素;

  HashSet:

  LinkedHashSet:

  TreeSet:

3.Map接口

  3.1 可以用containsKey()和containsValue()测试Map中是否包含某个”键”或“值”,有内置的排序;

  3.2 HsahMap使用对象的hashCode()进行快速查询,“散列码”是“相对唯一”用以代表对象的 int 值,它是通过将该对象的某些信息进行转换而生成的,所有 Java 对象都能产生散列码,因为 hashCode() 是定义在基类 Object 中的方法;

  HashTable:

  3.3 实现了一个key-value映射的哈希表,任何非空对象都可以作为key或者value;

  3.4 添加数据put,去除数据get;

  3.5 Hashtable 通过初始化容量 (initial capacity) 和负载因子 (load factor) 两个参数调整性能,通常缺省的 load factor 0.75 较好地实现了时间和空间的均衡。增大 load factor 可以节省空间但相应的查找时间将增大,这会影响像 get 和 put 这样的操作;

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

  HashMap:

  3.7 hashmap非同步,允许null值。将 HashMap 视为 Collection 时( values() 方法可返回 Collection ),插入和查询“键值对”的开销是固定的,但其迭代子操作时间开销和 HashMap 的容量成比例。因此,如果迭代操作的性能相当重要的话,不要将 HashMap 的初始化容量 (initial capacity) 设得过高,或者负载因子 (load factor) 过低;

  LinkedHashMap

  3.8 类似于 HashMap ,但是迭代遍历它时,取得“键值对”的顺序是其插入次序,或者是最近最少使用 (LRU) 的次序。只比 HashMap 慢一点。而在迭代访问时发而更快,因为它使用链表维护内部次序;

  WeakHashMap:

  3.9 弱键( weak key ) Map 是一种改进的 HashMap ,它是为解决特殊问题设计的,对 key 实行 “ 弱引用 ” ,如果一个 key 不再被外部所引用(没有 map 之外的引用),那么该 key 可以被垃圾收集器 (GC) 回收;

  TreeMap:

  基于红黑树数据结构的实现。查看“键”或“键值对”时,它们会被排序 ( 次序由 Comparabel 或 Comparator 决定 ) 。 TreeMap 的特点在于,你得到的结果是经过排序的。 TreeMap 是唯一的带有 subMap() 方法的 Map ,它可以返回一个子树;

  IdentifyHashMap:

  使用 == 代替 equals() 对“键”作比较的 hash map 。专为解决特殊问题而设计。

三  比较

1.数组(Array) 数组类(Arrays)

  1.1 java存储及随机访问一连串对象时,array最有效率,但缺点是容量固定且无法动态改变,无法判断实际存在多少元素,length为容量;

  1.2 数组类专门操作数组,数组类拥有一组static函数:equals() ,fill() ,sort(),binarySearch() 在排好序的array中查找元素 ,System.arraycopy() array复制;

  1.3 若编写程序时不知道究竟需要多少对象,需要在空间不足时自动扩增容量,则需要使用容器类库, array 不适用;

2.容器(Collection)和map

  2.1 collection每个位置只有一个元素;map持有key-value对,像个小型数据库 ( Collections.max(Collection coll); 取 coll 中最大的元素);

四、总结

1 List,Set,Map将持有对象一律视为object型别;

2 Collection 、 List 、 Set 、 Map 都是接口,不能实例化。继承自它们的 ArrayList, Vector, HashTable, HashMap 是具象 class ,这些才可被实例化;

3 使用keySet()抽取key序列,将 map 中的所有 keys 生成一个 Set(不可重复);

   使用 values() 抽取 value 序列,将 map 中的所有 values 生成一个 Collection ;

4 在各种 Lists ,对于需要快速插入,删除元素,应该使用 LinkedList (可用 LinkedList 构造堆栈 stack 、队列 queue ),如果需要快速随机访问元素,应该使用 ArrayList 。最好的做法是以 ArrayList 作为缺省选择。 Vector 总是比 ArrayList 慢,所以要尽量避免使用;

5 在各种 Sets 中, HashSet 通常优于 HashTree (插入、查找)。只有当需要产生一个经过排序的序列,才用 TreeSet 。 HashTree 存在的唯一理由:能够维护其内元素的排序状态;在各种 Maps 中 HashMap 用于快速查找

6 当元素个数固定,用 Array ,因为 Array 效率是最高的

 

 

原文:http://blog.csdn.net/jackie03/article/details/7312481

 

Java中各种集合问题