JAVA集合分析概述

       前段时间在QQ空间写了篇关于JAVA集合分析的日志，现搬到这里与大家分享。 其中有链接可查看各种集合的具体介绍。

http://user.qzone.qq.com/396768440/blog/1359132442

 

 最基本的数据结构有数组、链表2种。
        1）数组的长度是固定的，容量是有限的(除非扩容)。可以用索引访问，因此访问速度比较快。
        2）链表中每个节点指向下一个节点，容量是无限的(不作限制且不考虑硬件)。访问链表中的任一节点需要遍历链，因此访问速度比较慢。
        
        JAVA集合内部使用这2种结构中的1种或2种来保存数据，基本接口有：Map和Collection。Collection下有List、Queue、Set这3个接口。

• Map用于保存多个键值对，键不能重复。其中部分实现类(线程安全、key有序、key枚举)的键不能为空。
• Collection用于保存一组对象，分为3种接口。
  • List列表，对象可重复、可空。
  • Queue队列，对象可重复、不能空，添加一些操作方法。
  • Set对象不能重复。

        类图如下，其中圆表示接口、方形表示类，斜体描述的方形表示抽象类，蓝色边框表示JDK1.5以后出现的。


Map 

图1.1：Map类图

实现类
HashMap： 最常用的Map，线程不安全，没有多线程同时访问的情况，使用HashMap效率最高。内部使用数组保存节点，数组中的元素可为空，也可为链表。
LinkedHashMap：保存了插入顺序，用Iterator遍历时，按插入时的顺序返回。是HashMap的子类，并用双向链表将节点按进入顺序连接。
TreeMap：key是有序的，纯种不安全，使用红黑树保存节点。
ConcurrentHashMap：线程安全，不是锁整个Map对象，而使用ReentrantLock锁相应的segment，效率比Hashtable高。
ConcurrentSkipListMap：key是有序的，适合多线程的高并发。用有序的链保存数据，为节点建立N层索引，定位节点类似二分查找法。
Hashtable：线程安全，put、get、remove方法用synchronized锁住整个对象，效率比较低。
EnumMap：key是枚举值。 
WeakHashMap：key在外部没有引用时，该key的键值可被GC回收。
IdentityHashMap：判断key值相等时，用key1==key2判断，而不是equals。所以key可以是值相等的不同对象。
Properties：主要用于读取properties或XML配置文件，线程安全。

名称	数据结构	线程安全	key有序	key可空	明细
HashMap	数组+链表(hash表)	否	否	是	查看
LinkedHashMap	数组+链表	否	否	是
TreeMap	链(红黑树)	否	是	否	查看
ConcurrentHashMap	数组+数组+链表(分段hash表)	是	ReentrantLock	否	否	查看
ConcurrentSkipListMap	链表+索引链(跳表)	是	CAS	是	否	查看
Hashtable	数组+链表	是	synchronized	否	否	查看
EnumMap	数组+数组	否	否	否
WeakHashMap	数组+链表	否	否	是
IdentityHashMap	数组+链表	否	否	是

表1.1 各种Map比较

List 、Queue
 

图1.2：List、Queue类图 

接口
List：列表接口
        1)add：添加元素。
        2)remove：删除指定元素。
        3)get：返回指定元素。
Queue：所有队列的接口
        1)add：添加元素到队列，如果没有空间则抛出异常。
        2)remove：从队列中删除元素。
        3)poll：取走头元素，如果队列为空，则返回null。
        4)peek：返回头元素，如果队列为空，则返回null。
        5)element：返回头元素，如果队列为空，则抛出异常。
BlockingQueue：可阻塞队列的接口
        1)add：添加元素到队列，如果没有空间则抛出异常。
        2)put：添加元素到队列，如果没有空间则阻塞等待直到有空间。
        3)take：取走头元素，如果队列为空，则阻塞等待直到有元素。
        4)poll ：取走头元素，如果队列为空，则在超时时长范围内阻塞等待，超时后仍未取到则返回null。

实现类
ArrayList：最常用的List，线程不安全，内部是数组结构。
CopyOnWriteArrayList：线程安全，修改(add、remove)数组将复制一个新的数组来修改再设置回去，适合读远多于写。
LinkedList：线程不安全，内部是链表结构。
Vector：线程安全，用synchronized锁住addElement、get整个方法，效率较低。
Stack：是Vector的子类，可先进先出，用来实现栈。
ConcurrentLinkedQueue：效率最高的线程安全队列。
PriorityQueue：有优先级的队列，线程不安全。
PriorityBlockingQueue：有优先级的队列，线程安全。
ArrayBlockingQueue：有界的阻塞的数组队列，数组被占满后不能自动扩容。数组已满再加元素，add抛出异常，put阻塞等待。
LinkedBlockingQueue：有界的阻塞的链表队列。
ArrayDeque：双向数组队列，线程不安全。
LinkedBlockingDeque：双向阻塞队列。
SynchronousQueue：无缓冲的等待队列，用于数据交换。
DelayQueue：延时队列，延时时间到期后才出队列。

名称	数据结构	线程安全	可阻塞	容量有限	元素可空	明细
ArrayList	数组	否	否	否	是	查看
LinkedList	链表(双向)	否	否	否	是
Vector	数组	是	synchronized	否	否	是	查看
Stack	数组	是	synchronized	否	否	是
ConcurrentLinkedQueue	链表	是	CAS	否	否	否	查看
PriorityQueue	数组	否	否	否	否	查看
PriorityBlockingQueue	数组	是	ReentrantLock	是	Condition	否	否
ArrayBlockingQueue	数组	是	ReentrantLock	是	Condition	是	否	查看
LinkedBlockingQueue	链表	是	ReentrantLock	是	Condition	是	否
ArrayDeque	数组(双向)	否	否	否	否	查看
LinkedBlockingDeque	链表(双向)	是	ReentrantLock	是	Condition	是	否
SynchronousQueue	-	是	CAS	是	LockSupport	是	否	查看
DelayQueue	数组	是	ReentrantLock	是	Condition	否	否	查看

表1.2 各种List、Queue比较

 
Set
 

图1.3：Set类图

实现类
HashSet：无序，使用HashMap实现。
TreeSet：有序，使用TreeMap实现。
ConcurrentSkipListSet：线程安全，使用ConcurrentSkipListMap实现。
CopyOnWriteArraySet：线程安全，适合读远多于写的情况，使用CopyOnWriteArrayList实现。