Collection接口框架图

  |   1 评论   |   545 浏览

Java集合大致可分为Set、List和Map三种体系,其中Set代表无序、不可重复的集合;List代表有序、重复的集合;而Map则代表具有映射关系的集合。Java 5之后,增加了Queue体系集合,代表一种队列集合实现。

Java集合框架主要由Collection和Map两个根接口及其子接口、实现类组成。本文仅探讨Collection接口及其子接口、实现类。

1. Collection接口继承树


2. Collection接口是Set、List和Queue接口的父接口,基本操作包括:

*   add(Object o):增加元素
*   addAll(Collection c):...
*   clear():...
*   contains(Object o):是否包含指定元素
*   containsAll(Collection c):是否包含集合c中的所有元素
*   iterator():返回Iterator对象,用于遍历集合中的元素
*   remove(Object o):移除元素
*   removeAll(Collection c):相当于减集合c
*   retainAll(Collection c):相当于求与c的交集
*   size():返回元素个数
*   toArray():把集合转换为一个数组

3.Set子接口

Set集合不允许包含相同的元素,而判断两个对象是否相同则是根据equals方法。

3.1 HashSet类

HashSet类是Set接口的典型实现类。特点:

  1. 不能保证元素的排列顺序,加入的元素要特别注意hashCode()方法的实现。
  2. HashSet不是同步的,多线程访问同一步HashSet对象时,需要手工同步。
  3. 集合元素值可以是null。

3.2 LinkedHashSet类

LinkedHashSet类也是根据元素的hashCode值来决定元素的存储位置,但它同时使用链表维护元素的次序。与HashSet相比,特点:

  1. 对集合迭代时,按增加顺序返回元素。
  2. 性能略低于HashSet,因为需要维护元素的插入顺序。但迭代访问元素时会有好性能,因为它采用链表维护内部顺序。

3.3 SortedSet接口及TreeSet实现类

TreeSet类是SortedSet接口的实现类。因为需要排序,所以性能肯定差于HashSet。与HashSet相比,额外增加的方法有:

1.  first():返回第一个元素
2.  last():返回最后一个元素
3.  lower(Object o):返回指定元素之前的元素
4.  higher(Obect o):返回指定元素之后的元素
5.  subSet(fromElement, toElement):返回子集合

可以定义比较器(Comparator)来实现自定义的排序。默认自然升序排序。

3.4 EnumSet类

EnumSet类是专为枚举类设计的集合类,EnumSet中的所有元素都必须是指定枚举类型的枚举值。《Effective Java》第32条,用EnumSet代替位域,示范:

// EnumSet - a modern replacement for bit fields - Page 160
import java.util.*;

public class Text {
    public enum Style { BOLD, ITALIC, UNDERLINE, STRIKETHROUGH }

    // Any Set could be passed in, but EnumSet is clearly best
    public void applyStyles(Set styles) {
        // Body goes here
    }

    // Sample use
    public static void main(String[] args) {
        Text text = new Text();
        text.applyStyles(EnumSet.of(Style.BOLD, Style.ITALIC));
    }
}

4. List子接口

List子接口是有序集合,所以与Set相比,增加了与索引位置相关的操作:

*   add(int index, Object o):在指定位置插入元素
*   addAll(int index, Collection c):...
*   get(int index):取得指定位置元素
*   indexOf(Obejct o):返回对象o在集合中第一次出现的位置
*   lastIndexOf(Object o):...
*   remove(int index):删除并返回指定位置的元素
*   set(int index, Object o):替换指定位置元素
*   subList(int fromIndex, int endIndex):返回子集合

4.1 ArrayList和Vector实现类

  1. 这两个类都是基于数组实现的List类。
  2. ArrayList是线程不安全的,而Vector是线程安全的。但Vector的性能会比ArrayList低,且考虑到兼容性的原因,有很多重复方法。
  3. Vector提供一个子类Stack,可以挺方便的模拟“栈”这种数据结构(LIFO,后进先出)。

结论:不推荐使用Vector类,即使需要考虑同步,即也可以通过其它方法实现。同样我们也可以通过ArrayDeque类或LinkedList类实现“栈”的相关功能。所以Vector与子类Stack,建议放进历史吧。

4.2 LinkedList类

不像ArrayList是基于数组实现的线性表,LinkedList类是基于链表实现的。

另外还有固定长度的List:Arrays工具类的方法asList(Object… a)可以将数组转换为List集合,它是Arrays内部类ArrayList的实例,特点是不可以增加元素,也不可以删除元素。

5. Queue子接口

Queue用于模拟队列这种数据结构,实现“FIFO”等数据结构。通常,队列不允许随机访问队列中的元素。

Queue 接口并未定义阻塞队列的方法,而这在并发编程中是很常见的。BlockingQueue 接口定义了那些等待元素出现或等待队列中有可用空间的方法,这些方法扩展了此接口。

Queue 实现通常不允许插入 null 元素,尽管某些实现(如 LinkedList)并不禁止插入 null。即使在允许 null 的实现中,也不应该将 null 插入到 Queue 中,因为 null 也用作 poll 方法的一个特殊返回值,表明队列不包含元素。

基本操作:

*   boolean add(E e) : 将元素加入到队尾,不建议使用
*   boolean offer(E e): 将指定的元素插入此队列(如果立即可行且不会违反容量限制),当使用有容量限制的队列时,此方法通常要优于 add(E),后者可能无法插入元素,而只是抛出一个异常。推荐使用此方法取代add
*   E remove(): 获取头部元素并且删除元素,不建议使用
*   E poll(): 获取头部元素并且删除元素,队列为空返回null;推荐使用此方法取代remove
*   E element(): 获取但是不移除此队列的头
*   E peek(): 获取队列头部元素却不删除元素,队列为空返回null
   @Test
    public void testQueue() {
        Queue<String> queue = new LinkedList<String>();
        queue.offer("1.你在哪儿?");
        queue.offer("2.我在这里。");
        queue.offer("3.那你又在哪儿呢?");
        String str = null;
        while ((str = queue.poll()) != null) {
            System.out.println(str);
        }
    }

5.1 PriorityQueue类

PriorityQueue保存队列元素的顺序并不是按照加入队列的顺序,而是按队列元素的大小重新排序当调用peek()或者是poll()方法时,返回的是队列中最小的元素。当然你可以与TreeSet一样,可以自定义排序。自定义排序的一个示范:

    @Test
    public void testPriorityQueue() {
        PriorityQueue<Integer> pq = new PriorityQueue<Integer>(20, new Comparator<Integer>() {
            public int compare(Integer i, Integer j) {
                // 对数字进行奇偶分类,然后比较返回;偶数有较低的返回值(对2取余数然后相减),奇数直接相减。
                int result = i % 2 - j % 2;
                if (result == 0)
                    result = i - j;
                return result;
            }
        });

        // 倒序插入测试数据
        for (int i = 0; i < 20; i++) {
            pq.offer(20 - i);
        }

        // 打印结果,偶数因为有较低的值,所以排在前面
        for (int i = 0; i < 20; i++) {
            System.out.println(pq.poll());
        }
    }

输出:

2,4,6,8,10,12,14,16,18,20,1,3,5,7,9,11,13,15,17,19,

5.2 Deque子接口与ArrayDeque类

Deque代表一个双端队列,可以当作一个双端队列使用,也可以当作“栈”来使用,因为它包含出栈pop()与入栈push()方法。

ArrayDeque类为Deque的实现类,数组方式实现。方法有:

*   addFirst(Object o):元素增加至队列开头
*   addLast(Object o):元素增加至队列末尾
*   poolFirst():获取并删除队列第一个元素,队列为空返回null
*   poolLast():获取并删除队列最后一个元素,队列为空返回null
*   pop():“栈”方法,出栈,相当于removeFirst()
*   push(Object o):“栈”方法,入栈,相当于addFirst()
*   removeFirst():获取并删除队列第一个元素
*   removeLast():获取并删除队列最后一个元素

5.3 实现List接口与Deque接口的LinkedList类

LinkedList类是List接口的实现类,同时它也实现了Deque接口。因此它也可以当做一个双端队列来用,也可以当作“栈”来使用。并且,它是以链表的形式来实现的,这样的结果是它的随机访问集合中的元素时性能较差,但插入与删除操作性能非常出色。

6. 各种线性表选择策略

  1. 数组:是以一段连续内存保存数据的;随机访问是最快的,但不支持插入、删除、迭代等操作。
  2. ArrayList与ArrayDeque:以数组实现;随机访问速度还行,插入、删除、迭代操作速度一般;线程不安全。
  3. Vector:以数组实现;随机访问速度一般,插入、删除、迭代速度不太好;线程安全的。
  4. LinkedList:以链表实现;随机访问速度不太好,插入、删除、迭代速度非常快。

7. Collection框架中实现比较要实现什么接口

comparable/comparator

8. ArrayList和Vector的区别

这两个类都实现了List接口(List接口继承了Collection接口),他们都是有序集合,即存储在这两个集合中的元素的位置都是有顺序的,相当于一种动态的数组,我们以后可以按位置索引号取出某个元素,,并且其中的数据是允许重复的,这是HashSet之类的集合的最大不同处,HashSet之类的集合不可以按索引号去检索其中的元素,也不允许有重复的元素(本来题目问的与hashset没有任何关系,但为了说清楚ArrayList与Vector的功能,我们使用对比方式,更有利于说明问题)。

这主要包括两个方面:
(1)同步性:
Vector是线程安全的,也就是说是它的方法之间是线程同步的,而ArrayList是线程序不安全的,它的方法之间是线程不同步的。如果只有一个线程会访问到集合,那最好是使用ArrayList,因为它不考虑线程安全,效率会高些;如果有多个线程会访问到集合,那最好是使用Vector,因为不需要我们自己再去考虑和编写线程安全的代码。
备注:对于Vector&ArrayList、Hashtable&HashMap,要记住线程安全的问题,记住Vector与Hashtable是旧的,是java一诞生就提供了的,它们是线程安全的,ArrayList与HashMap是java2时才提供的,它们是线程不安全的。所以,我们讲课时先讲老的。

(2)数据增长:
ArrayList与Vector都有一个初始的容量大小,当存储进它们里面的元素的个数超过了容量时,就需要增加ArrayList与Vector的存储空间,每次要增加存储空间时,不是只增加一个存储单元,而是增加多个存储单元,每次增加的存储单元的个数在内存空间利用与程序效率之间要取得一定的平衡。Vector默认增长为原来两倍,而ArrayList的增长策略在文档中没有明确规定(从源代码看到的是增长为原来的1.5倍)。ArrayList与Vector都可以设置初始的空间大小,Vector还可以设置增长的空间大小,而ArrayList没有提供设置增长空间的方法。
总结:即Vector增长原来的一倍,ArrayList增加原来的0.5倍。

9. HashMap和Hashtable的区别

HashMap是Hashtable的轻量级实现(非线程安全的实现),他们都完成了Map接口,主要区别在于HashMap允许空(null)键值(key),由于非线程安全,在只有一个线程访问的情况下,效率要高于Hashtable。

HashMap允许将null作为一个entry的key或者value,而Hashtable不允许。

HashMap把Hashtable的contains方法去掉了,改成containsvalue和containsKey。因为contains方法容易让人引起误解。

Hashtable继承自Dictionary类,而HashMap是Java1.2引进的Map interface的一个实现。

最大的不同是,Hashtable的方法是Synchronize的,而HashMap不是,在多个线程访问Hashtable时,不需要自己为它的方法实现同步,而HashMap 就必须为之提供外同步。

Hashtable和HashMap采用的hash/rehash算法都大概一样,所以性能不会有很大的差异。

就HashMap与HashTable主要从三方面来说。
一.历史原因:Hashtable是基于陈旧的Dictionary类的,HashMap是Java 1.2引进的Map接口的一个实现
二.同步性:Hashtable是线程安全的,也就是说是同步的,而HashMap是线程序不安全的,不是同步的
三.值:只有HashMap可以让你将空值作为一个表的条目的key或value

10. List 和 Map 的区别

一个是存储单列数据的集合,另一个是存储键和值这样的双列数据的集合,List中存储的数据是有顺序,并且允许重复;Map中存储的数据是没有顺序的,其键是不能重复的,它的值是可以有重复的。

11. List、Map、Set三个接口,存取元素时,各有什么特点

首先,List与Set具有相似性,它们都是单列元素的集合,所以,它们有一个功共同的父接口,叫Collection。Set里面不允许有重复的元素,所谓重复,即不能有两个相等(注意,不是仅仅是相同)的对象 ,即假设Set集合中有了一个A对象,现在我要向Set集合再存入一个B对象,但B对象与A对象equals相等,则B对象存储不进去,所以,Set集合的add方法有一个boolean的返回值,当集合中没有某个元素,此时add方法可成功加入该元素时,则返回true,当集合含有与某个元素equals相等的元素时,此时add方法无法加入该元素,返回结果为false。Set取元素时,没法说取第几个,只能以Iterator接口取得所有的元素,再逐一遍历各个元素。

List表示有先后顺序的集合,注意,不是那种按年龄、按大小、按价格之类的排序。当我们多次调用add(Obj e)方法时,每次加入的对象就像火车站买票有排队顺序一样,按先来后到的顺序排序。有时候,也可以插队,即调用add(int index,Obj e)方法,就可以指定当前对象在集合中的存放位置。一个对象可以被反复存储进List中,每调用一次add方法,这个对象就被插入进集合中一次,其实,并不是把这个对象本身存储进了集合中,而是在集合中用一个索引变量指向这个对象,当这个对象被add多次时,即相当于集合中有多个索引指向了这个对象,如图x所示。List除了可以以Iterator接口取得所有的元素,再逐一遍历各个元素之外,还可以调用get(index i)来明确说明取第几个。

Map与List和Set不同,它是双列的集合,其中有put方法,定义如下:put(obj key,obj value),每次存储时,要存储一对key/value,不能存储重复的key,这个重复的规则也是按equals比较相等。取则可以根据key获得相应的value,即get(Object key)返回值为key 所对应的value。另外,也可以获得所有的key的结合,还可以获得所有的value的结合,还可以获得key和value组合成的Map.Entry对象的集合。

List 以特定次序来持有元素,可有重复元素。Set 无法拥有重复元素,内部排序。Map 保存key-value值,value可多值。

同一个对象可以在Vector中加入多次。往集合里面加元素,相当于集合里用一根绳子连接到了目标对象。往HashSet中却加不了多次的。

12. 说出ArrayList,Vector, LinkedList的存储性能和特性

ArrayList和Vector都是使用数组方式存储数据,此数组元素数大于实际存储的数据以便增加和插入元素,它们都允许直接按序号索引元素,但是插入元素要涉及数组元素移动等内存操作,所以索引数据快而插入数据慢,Vector由于使用了synchronized方法(线程安全),通常性能上较ArrayList差,而LinkedList使用双向链表实现存储,按序号索引数据需要进行前向或后向遍历,但是插入数据时只需要记录本项的前后项即可,所以插入速度较快。

LinkedList也是线程不安全的,LinkedList提供了一些方法,使得LinkedList可以被当作堆栈和队列来使用。

13. Collection 和 Collections的区别

Collection是集合类的上级接口,继承与他的接口主要有Set 和List.

Collections是针对集合类的一个帮助类,他提供一系列静态方法实现对各种集合的搜索、排序、线程安全化等操作。

转载自:孙秋翔 http://www.cnblogs.com/quinnsun/

评论

  • lkq 回复»

    涂哥,挺厉害的呀:smile:

发表评论

validate