1. 接口

首先，放上层次图（少了Queue）。

Collection 继承了 Iterator 接口（事实上，该接口是所有集合的总接口），定义了集合的遍历操作。

前面我们已经介绍过集合类的基础知识，这里就简单回顾以下：

• Collection：Collection 是一个接口，没有直接实现类。它用来传递集合并在需要最大通用性时对其进行操作。
• List：有序集合（或称为序列），可以包含重复元素。List 可以通过索引访问元素。
• Set：不能包含重复元素的集合。
• Queue：用于在处理之前保存多个元素的集合。队列通常（但不一定）以先入先出方式对元素进行排序。优先级队列可以根据 comparator 或者元素的自然顺序排序。
  • Deque：双向队列。可 先进先出 也可 后进先出，可以在两端插入、检索和删除元素。
• Map：将键映射到值得对象。不能包含重复的键，每个键最多可以映射一个值。

另外还有 Set 和 Map 的"排序版本"：

• SortedSet：一个升序维护元素得集合。用于自然排序的 set
• SortedMap：按键的升序顺序维护其映射的 map。用于自然排序的键值对。

对上述整理分类的话，可以分为两个不同的接口树：

• 第一个树以Collection接口开始，它提供了所有集合使用的基本功能，例如add和remove方法。 它的子接口 Set， List和Queue提供更专业的集合。
  • Set接口不允许重复元素。 这对于存储诸如一副纸牌或学生记录之类的集合非常有用。 Set接口有一个子接口SortedSet ，它提供了集合中元素的排序。
  • List接口提供有序集合，适用于需要精确控制每个元素插入位置的情况。 可以按照其确切位置从List检索元素。
  • Queue支持其他插入，提取和检查操作。 Queue中的元素通常以FIFO为基础进行排序。
  • Deque接口可在两端启用插入，删除和检查操作。 Deque元素可用于LIFO和FIFO。
• 第二个树以Map接口开始，它映射键和值类似于Hashtable 。
  • Map的子接口SortedMap按升序或按Comparator指定的顺序维护其键值对。

List 和 Set 对比

1. Set ：检索元素效率低，删除和插入效率高（不会引起元素位置改变）
2. List：和数组类型，可以动态增长；查找元素效率，插入和删除元素效率低（会引起元素位置改变）

线程安全集合类 与 非线程安全集合类

1. 线程安全：Vector、HashTable、（StringBuffer）
2. 非线程安全：LinkedList、ArrayList、HashSet、HashMap、（StringBuilder）

2. 实现类

本节用来介绍具体上述接口对应的实现类，有如下几种实现：

• 通用实现 是最常用的实现，专为日常使用而设计。
• 专用实现 旨在用于特殊情况，并显示非标准性能特征，使用限制或行为。
• 并发实现 旨在支持高并发性，通常以牺牲单线程性能为代价。 这些实现是java.util.concurrent包的一部分。
• 包装器实现 与其他类型的实现（通常是通用实现）结合使用，以提供增加或限制的功能。
• 便利实现(Convenience Implementations ) 是通常通过静态工厂方法提供的小型实现，为特殊集合（例如，单例集）的通用实现提供方便，有效的替代方案。
• 抽象实现 是支持构建自定义实现类的核心。

下面给出通用实现的小结：

2.1 Set 实现类

Set 实现分为 通用实现 和 专用实现。

2.1.1 通用实现

Set 的通用实现包括：HashSet、TreeSet 和 LinkedHashSet。

特性：

1. HashSet：为快速查找而设计的 Set。存入 HashSet 的元素必须定义 hashCode()；比 TreeSet 快的多。
2. TreeSet：保持次序的 Set，底层为树结构。使用它可以从 Set 提取有序的序列，元素必须实现 Comparable 接口。
3. LinkedHashSet：具有 HashSet 的查询速度，且内部使用链表维护元素的顺序（插入次序）。在使用迭代器遍历 Set 时，结果会按元素插入的次序显示。元素也必须定义 hashCode() 方法

2.1.2 专用实现

Set 有两个专用实现：EnumSet 和 CopyOnWriteArraySet。

特性：

1. EnumSet：枚举类型的高性能 Set 实现。
   1. 成员必须具有相同的枚举类型。
   2. 内部以位向量的形式存储，紧凑高效，因此EnumSet占用内存很小，且运行效率很好
   3. 不允许假如 null 元素
2. CopyOnWriteArraySet：
   1. 通过动态数组实现（写时复制）；
   2. 线程安全；
   3. 可变操作如add()等开销很大（因为要复制整个数组）；
   4. 迭代器支持 hasNext(),next()等不可变操作，不支持可变 remove()等 操作
   5. 迭代器遍历速度很快。构造迭代器时，依赖于不变的数组快照。
   6. 非常适合维护防止重复的事件处理程序列表。

2.2 List 实现类

List 实现分为通用实现和专用实现。

2.2.1 通用实现

List 有两个通用实现：ArrayList 和 LinkedList。

特性：

1. ArrayList：底层通过可调整大小的数组实现。

   1. 提供常数时间的随机访问，速度极快。

   2. 但是添加/删除元素时，性能很差。（线性时间）

      需要移动数组元素

2. LinkedList：底层通过链表实现。

   1. 添加/删除元素时，性能很好。（常数时间）

   2. 随机访问性能很差。（线性时间）

      需要遍历查找该元素。

2.2.2 专用实现

List 有一个专用实现：CopyonWriteArrayList。

特性：

1. 本质和 CopyOnWriteArraySet 一样，都是写时复制数组
2. 线程同步
3. 不支持可变操作如 remove()、add()等。
4. 非常适合维护事件处理程序列表，其中更改很少发生，并且遍历频繁且可能非常耗时。

2.3 Map 实现类

Map 实现分为通用实现，专用实现和并发实现。

2.3.1 通用实现

有三个通用实现：HashMap、TreeMap、LinkedHashMap

特性：

1. HashMap：Map 基于散列表的实现。插入和查询“键值对”的开销是固定的，可以通过构造器设置容量和负载因子，以调整容器的性能
2. Tree Map：基于红黑树的实现，查看“键”或“键值对”时，它们会被排序（由 Comparable 或 Comparator 决定次序），结果是经过排序的。
3. LinkedHashMap：类似于 HashMap，但是迭代遍历时，取得“键值对”的顺序是其插入次序，或者是LRU次序。只比 HashMap 慢一点：却在迭代访问时更快，因为用链表维护内部次序。

需要特殊强调一个方法：LinkedHashMap 提供的 removeEldestEntry() 方法。可以重写该方法，改变将添加新映射时强制删除过时映射的策略。通过该方法，可以轻松的实现 LRU 缓存。

2.3.2 专用实现

有三种特殊用途的专用实现：EnumMap、WeakHashMap、IdentityHashMap

特性：

1. EnumMap：是一个于枚举类一起使用的 Map 实现，其中所有 key 都必须是单个枚举类的枚举值。
   1. 内部以数组形式保存
   2. 根据 key 的自然顺序（即枚举值在枚举类中的定义顺序）来维护键值对的次序。
   3. 不允许使用 null 作为 key，但允许使用 null 作为 value。
2. WeakHashMap：和 HashMap 一样，也是一个散列表，存储内容也是 键值对，而且键和值都可以是 null。
   1. 键是"弱键"，存储的是键的弱引用，当键不再使用时，会自动移除。
   2. 换个说法，当键不在 WeakHashMap 之外引用时，允许垃圾回收器进行回收。
   3. 适用于实现类似注册表的结构。当任何线程不再可以访问其密钥时，条目的实用程序就会消失。
3. IdentityHashMap 底层是哈希表的的基于身份的 Map 实现
   1. 允许 key 相等。
   2. 故意反常 equals 方法的结果。仅当 (k1==null ? k2==null : v1.equals(v2)) 时，两个键 k1 和 k2 才相等。

2.3.3 并发实现

ConcurrentHashMap是一个底层为哈希表的高度并发，高性能的实现。 执行检索时，此实现永远不会阻塞，并允许客户端选择更新的并发级别。 它旨在作为Hashtable替代品：除了实现ConcurrentMap ，它还支持Hashtable特有的所有遗留方法。

2.4 Queue 实现类

Map 实现分为通用实现，专用实现和并发实现。

2.4.1 通用实现

LinkedList 实现了 Queue 接口。

这里主要说另一种实现：PriorityQueue，它是基于堆数据结构的优先级队列。此队列根据构造是指定的顺序堆元素进行排序，这可以是元素的自然顺序或显式指定 Comparator 的排序。

注意，迭代器中的 iterator 不保证以任何特定顺序遍历 PriorityQueue中的元素，如果需要有序输出，使用Arrays.sort(pq.toArray()) 或者 for 循环遍历。

2.4.2 并发实现

java.util.concurrent包中包含一组同步的Queue接口和类。 BlockingQueue 使用等待队列在检索元素时变为非空的操作以及在存储元素时队列中可用的空间来扩展Queue 。 此接口由以下类实现：

• LinkedBlockingQueue - 由链表支持的可选有界FIFO阻塞队列
• ArrayBlockingQueue - 由数组支持的有界FIFO阻塞队列
• PriorityBlockingQueue- 由堆支持的无限制阻塞优先级队列
• DelayQueue - 由堆支持的基于时间的调度队列
• SynchronousQueue - 一种使用BlockingQueue接口的简单集合点机制

在JDK 7中， TransferQueue是一个专门的BlockingQueue ，其中向队列添加元素的代码可以选择等待（阻塞）另一个线程中的代码来检索元素。 TransferQueue有一个实现：

• LinkedTransferQueue - 基于链接节点的无界TransferQueue

2.5 Deque 实现类

Deque 实现分为通用实现和并发实现。

2.5.1 通用实现

LinkedList 和 ArrayDeque。

1. ArrayDeque：基于可调整大小的数组实现
   1. 不允许 null 元素
   2. 效率高，可以从两端添加和删除操作
2. LinkedList：基于 List 实现
   1. 允许使用 null 元素
   2. 不是迭代的理想结构。
   3. 比 ArrayDeque 实现消耗更多内存

对于ArrayDeque 的遍历，两种方式：

1. foreach
2. 迭代器

2.5.2 并发实现

LinkedBlockingDeque]类是Deque接口的并发实现。 如果deque为空，那么诸如takeFirst和takeLast方法takeLast等到元素变为可用，然后检索并删除相同的元素。

2.6 包装器实现

包装器实现将所有实际工作委托给指定的集合，但在此集合提供的功能之上添加额外的功能。 这些实现是匿名的; 该库提供静态工厂方法，而不是提供公共类。

2.6.1 同步

保证了线程安全性，每一个核心街口都有一个静态工厂方法。

public static <T> Collection<T> synchronizedCollection(Collection<T> c);
public static <T> Set<T> synchronizedSet(Set<T> s);
public static <T> List<T> synchronizedList(List<T> list);
public static <K,V> Map<K,V> synchronizedMap(Map<K,V> m);
public static <T> SortedSet<T> synchronizedSortedSet(SortedSet<T> s);
public static <K,V> SortedMap<K,V> synchronizedSortedMap(SortedMap<K,V> m);

这些方法每一个都返回一个由指定集合备份的同步（线程安全） Collection 。 为了保证串行访问，必须通过返回的集合完成对后备集合的所有访问。 保证这一点的简单方法不是保留对后备集合的引用。 使用以下技巧创建同步集合。

List<Type> list = Collections.synchronizedList(new ArrayList<Type>());

以该方式创建的集合都是线程安全的。

2.6.2 不可修改

与添加功能的同步包装器不同，不可修改的包装器可以消除功能。 具体来说，会通过拦截所有修改集合的操作来消除修改集合的能力并抛出 UnsupportedOperationException 。 不可修改的包装有两个主要用途，如下所示：

• 在构建集合后使集合不可变。 在这种情况下，最好不要维护对集合的引用。 这保证了不变性。
• 允许某些客户端以只读方式访问数据结构。 保留对支持集合的引用，但是分发对包装器的引用。 通过这种方式，客户端可以查看但不能修改，同时保持完全访问权限。

与同步包装器一样，六个核心Collection接口中的每一个都有一个静态工厂方法。

public static <T> Collection<T> unmodifiableCollection(Collection<? extends T> c);
public static <T> Set<T> unmodifiableSet(Set<? extends T> s);
public static <T> List<T> unmodifiableList(List<? extends T> list);
public static <K,V> Map<K, V> unmodifiableMap(Map<? extends K, ? extends V> m);
public static <T> SortedSet<T> unmodifiableSortedSet(SortedSet<? extends T> s);
public static <K,V> SortedMap<K, V> unmodifiableSortedMap(SortedMap<K, ? extends V> m);

2.7 "便利"实现

这里指的就是 Arrays 和 Collections 这两个类了。

二者内部封装了一系列静态方法，来对集合进行操作，具体 API 就不讲了。

官方文档 https://docs.oracle.com/javase/9/docs/api/overview-summary.html

2.8 实现类小结

开发中，我们实际上是操作实现类来存储数据对象，这些实现类实现了集合的核心接口。

对于核心接口的通用实现：

• 对于Set接口， HashSet是最常用的实现。
• 对于List接口， ArrayList是最常用的实现。
• 对于Map接口， HashMap是最常用的实现。
• 对于Queue接口， LinkedList是最常用的实现。
• 对于Deque接口， ArrayDeque是最常用的实现。

java.util.concurrent包中还包含多个集合实现，这些实现是线程安全的。

Collections类（与Collection接口相对）提供了对集合进行操作或返回集合的静态方法。