接口类图

Java Collection由两套并行的接口组成，一套是Collection接口，一套是Map接口。如下图

公共抽象类AbstractCollection

要求派生类实现iterator()方法，AbstractCollection根据得到的Iterator实现所有可以支持的方法，比如remove()、contains()、toArray()、toString()等。

当然，Map系列的类并不从AbstractCollection派生。

List实现

AbstractList

要求子类实现get(int)和size()方法，AbstractList利用这两个模板方法，实现出完整的只读List。

ArrayList

利用Object[]实现的List。

AbstractSequentialList

利用ListIterator接口，实现get(index)、set(index)、remove(index)、add(index, value)等随机访问的方法。

LinkedList

单向链表，下面是链表中每个节点的定义：

Vector

线程安全的List，采用synchronized(this)进行加锁。内部采用Object[]实现。

Stack

对Vector进行的简单封装。

CopyOnWriteArrayList

注意此类直接从Object派生。

线程安全。每个add、set等修改操作，都会导致对内部数组进行全新复制。Iterator()函数返回的迭代器对象，包含了当前array的一个快照。因此，对CopyOnWriteArrayList对象的修改，不会影响已经生成的迭代器对象，只是迭代器对象看到的快照有可能是过时的。

Queue实现

ArrayDeque

用环形数组实现的Deque，自动增长数组大小。

不能接受null元素。

非线程安全。

AbstractQueue

抽象类。利用模板函数实现了几个功能，比如addAll()

ConcurrentLinkedQueue

线程安全。但这只是表示并发操作不会破坏内部结构，但是toArray()、迭代器、addAll()等操作不是原子的。

不能接受null元素。

用单向链表实现。

使用了非JDK类sun.misc.Unsafe。

PriorityQueue

优先队列，利用优先堆实现。

非线程安全。

加入的元素必须支持全排序。

不能接受null元素。

DelayQueue

实现的时候用到了PriorityQueue。

非线程安全。

支持Blocking操作。

可以用于连接超时自动移除、缓存超时自动移除等场景。

注意事项：假定DelayQueue中的元素类型为T，

1.        T.getDelay()应该返回超时值

2.        T必须可以全排序

3.        T最好是根据超时值进行全排序，并且全排序一旦排好，比较结果不应该随着Delay值变化而变化。

SynchronousQueue

线程安全。

不接收null元素。

特点是put和take函数必须同时执行，才能全部返回；任何一个单独执行只会导致等待。

PriorityBlockingQueue

带有Blocking功能的优先队列。

LinkedBlockingQueue

带有Blocking功能的Queue

用单向链表实现。

创建的时候可以指定容量，没有指定容量就是Integer.MaxValue；容量在创建后不能修改。

已满状态执行put会导致等待。

为空状态下执行take会导致等待。

ArrayBlockingQueue

带有Blocking功能的Queue

用Array实现。

创建的时候必须指定容量，并且创建后不能修改。

已满状态执行put会导致等待。

为空状态下执行take会导致等待。

Set实现

AbstractSet

抽象基类，通过Iterator实现几个通用方法。

HashSet

内部包含了一个HashMap对象。

向HashSet中添加一个元素X，相当于向HashMap对象添加一个<X,DummyObject>二元组。

非线程安全。

接收null元素。

LinkedHashSet

内部包含了一个LinkedHashMap对象。

非线程安全。

接收null元素。

采用Iterator迭代的时候，根据元素添加的顺序排序。

TreeSet

内部包含了一个TreeMap对象。

向TreeSet中添加一个元素X，相当于向TreeMap对象添加一个<X,DummyObject>二元组。

非线程安全。

不接受null元素。

ConcurrentSkipListSet

内部包含了一个ConcurentSkipListMap。

线程安全。

不接收null元素。

CopyOnWriteArraySet

内部包含了一个CopyOnWriteArrayList做实际的数据存储，因此这实际上是一个Array。

Map实现

AbstractMap

抽象类，利用entrySet()模板方法实现了一些通用方法。

HashMap

哈希表

Key和Value都可以为null。

非线程安全。

LinkedHashMap

从HashMap派生，整个哈希结构都是利用了HashMap来实现

每个插入的Value，都通过一个双向链表连接起来。

可以指定链表的顺序是按照插入时间排序、还是按照访问时间排序。如果是按照访问时间排序，每次访问都要调整链表。

TreeMap

基于红黑树实现的Map。

非线程安全。

ConcurrentHashTable

基于哈希表实现。

构造函数中可以指定并发程度，也就是预期有多少更新线程。

ConcurrentSkiptListMap

支持并发的跳跃表

IdentityHashMap

哈希表

内部采用==判断key的相等性。

EnumMap

接收Key为Enum类型的Map。

内部用数组来存储Value，即Value =http://www.mamicode.com/= this.Vals[Key.ordinal]，效率高。

WeakHashMap

每个Key用WeakReference管理。当Key对象符合弱引用的回收条件时，就被回收。

Size()方法返回的是还没有被回收的Key对象的数量。

如果Key已经被回收，get方法放回null。

利用哈希表实现。

实现上，每个<Key，Value>对应一个Entry，每个Entry都是WeakReference的派生类对象。该Entry对象也就是Key的WeakReference。

集合类的区分因素

1.        支持哪些操作接口

2.        内部实现的数据结构，及其相应的时空复杂度

3.        是否对插入元素的数量有限制

4.        是否支持插入null元素

5.        是否线程安全

6.        是否支持阻塞