最全的集合干货送给大家（二）

SortedSet 接口

SortedSet 接口直接继承于 Set 接口，提供了一个进一步对元素进行排序的 set。使用 Comparable 对元素进行自然排序或者使用 Comparator 在创建时对元素提供定制的排序规则。set 的迭代器将按升序元素顺序遍历集合。

• 所有插入到 SortedSet 中的元素都必须实现 Comparable 接口(或者接口定制的构造器)。进一步来说，所有内部的元素都必须相互比较：e1.compareTo(e2) 或者 comparator.compare(e1, e2) 并且不会抛出 ClassCastException。违反此限制将导致方法抛出 ClassCastException。
  
• 请注意：如果排序集要正确实现 Set 接口，则排序集维护的排序必须与 equals 一致。(查阅 Comparable 接口或者 Comparator 接口)。这是因为 Set 接口是根据 equals 操作定义的。但是有序集合使用 compareTo 执行所有元素的比较。因此从排序集的角度看，这种方法认为相等的两个元素是相等的。即使排序与 equals 不一致，排序集的行为也是正常运行的。它只是不遵守一般的 Set 接口定义。
  
• 所有 SortedSet 实现类都应该提供四个标准的构造器：
  

• 一个 void（无参数）构造函数，它根据元素的自然顺序创建一个空的有序集。
  
• 一个创建了单个 Comparator 类型参数的构造函数，它创建一个根据指定比较器排序的空排序集
  
• 一个创建了单个 Comparator 类型参数的构造函数，它创建一个新的有序集合，其元素与其参数相同，并根据元素的自然顺序进行排序
  
• 一个创建了单个 SortedSet 类型参数的构造器，它创建了一个新的有序集，其元素和输入有序集的顺序相同。由于接口不能包含构造函数，因此无法强制执行。
  

AbstractCollection 抽象类

AbstractCollection 这个接口是 Collection 接口的一个核心实现，采用抽象方法提供部分代码的实现，用来简化实现此接口所需要的工作量，此接口提供了一些对于实现类的说明，并提供了一系列标准。

• 为了实现不可修改的 collection，程序员应该继承这个类并提供 iterator 和 size 方法(迭代器需要实现 hasNext() 和 next() 方法)
  
• 为了实现可修改的 collection，程序员需要额外重写类的 add 方法，iterator 方法返回的 Iterator 迭代器也必须实现 remove 方法
  

AbstractList 抽象类

AbstractList 接口位于中间层，向下是具体的实现类，向上是定义的抽象标准，AbstractList 继承了AbstractCollection 并实现了**List **接口，具体继承体系见下图AbstractCollection 继承体系

此接口也是 List 继承类层次的核心接口，以求最大限度的减少实现此接口的工作量，由顺序访问数据存储(数组)支持。对于序列访问的数据(像是链表)，应该优先使用 AbstractSequentialList。

• 为了实现不可修改的 list，程序员仅需要扩展这个类，并提供 get 和 list.size() 的实现就可以了。
  
• 如果要实现可修改的 list，程序员必须额外重写 set(int,Object) set(int,E) 方法(否则会抛出 UnsupportedOperationException 的异常)，如果 list 是可变大小的，程序员必须额外重写 add(int,Object) , add(int, E) and remove(int) 方法
  

ArrayList 类

ArrayList 是实现了 List 接口的可扩容数组(动态数组)，它的内部是基于数组实现的。它的具体定义如下：

publicclass ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable {...}

• ArrayList 可以实现所有可选择的列表操作，允许所有的元素，包括空值。ArrayList 还提供了内部存储 list 的方法，它能够完全替代 Vector，只有一点除外，ArrayList 不是线程安全的容器。
  
• 每一个 ArrayList 实例都有一个容量的概念，这个数组的容量就是 list 用来存储元素的容量。它内部的 capacity 属性能够快速增长，依照元素添加进 ArrayList 后，它总是能够自动增长。
  
• 注意这个实现类不是线程安全的，如果多个线程中至少有两个线程修改了 ArrayList 的结构的话那么最终 ArrayList 中元素的个数和值可能就会发生变化。
  
• 如果不存在此对象，则应使用 Collections.synchronizedList "包装"该对象，最好在创建时期就这么做,防止意外的不同步列表访问。
  

List list = Collections.synchronizedList(new ArrayList(...))

• Iterator 和 listIterator 都会返回 iterators，并且都是支持 fail-fast 机制的。如果创建后再进行结构化修改的话，除了通过迭代器自己以外的任何方式，都会抛出 ConcurrentModificationException。因此，面对并发修改的情况，iterator 能够快速触发 fail-fast 机制，而不是冒着潜在的风险。
  更多关于 ArrayList 的用法，请参考ArrayList 相关方法介绍及源码分析^[2]
  

Vector 类

Vector 类实现了可增长的对象数组。像数组一样，它包含可以使用整数索引访问元素。但是，Vector 的大小可以根据需要增大或减小，以便在创建 Vector 后添加和删除。

• 每一个 vector 都试图去维护 capacity 和 capacityIncrement 来优化内部存储。capacity 总是要保持和 vector 一样的大小。随着新元素的增加，它的容量也在一直变大。vector 的存储以 capacityIncrement 的大小增加。应用程序可以在插入大量元素之前增加 vector 的容量，这就会减少重新分配的次数，降低重新分配带来的影响。
  
• 这个类 iterator() 方法和 listIterator() 方法返回的 iterators 是有快速失败机制的：如果 vector 在创建了 iterator 之后经过了结构化的修改，除了调用迭代器内部的 remove 或者 add 方法之外的其他方法，都会抛出 ConcurrentModificationException
  
• elements 方法返回的 Enumeration 则没有 fail-fast 机制。
  

Stack 堆栈类

Stack 类代表了后进先出 (LIFO) 对象的堆栈。它继承了 Vector 类，并且有五个操作允许 vector 像 stack 一样看待。提供了通常用的 push 和 pop 操作，以及在栈顶的 peek 方法，测试 stack 是否为空的 empty 方法，和一个寻找与栈顶距离的 search 方法。

第一次创建栈，不包含任何元素。一个更完善，可靠性更强的 LIFO 栈操作由 Deque 接口和他的实现提供，应该优先使用这个类

Deque<Integer> stack = new ArrayDeque<Integer>()

AbstractSet 抽象类

继承体系和 AbstractList 基本相同，除了 AbstractList 实现了 List 接口，而 AbstractSet 实现了 Set 接口。

• AbstractSet 是 Set 接口的骨干实现，以求最大限度的减少实现此接口的工作量。
  
• 通过扩展此类来实现集合的过程与通过扩展 AbstractCollection 实现集合的过程相同。除了这个类的子类中的所有方法和构造函数必须遵守 Set 接口强加的附加约束（例如，add 方法不允许将对象的多个实例添加到集合中）
  
• 注意这个类没有重写任何 AbstractCollection 的实现，它仅仅增加了 equals 和 hashCode 实现。
  

HashSet 类

HashSet 类是 Set 接口的实现类，由哈希表支持(实际上 HashSet 是 HashMap 的一个实例)。它不能保证集合的迭代顺序；特别是，它不保证顺序会随着时间的推移保持不变(也就是无序的)。这个类允许 null 元素。

• 这个类为基本操作 (add,remove,contains,size) 提供恒定的时间和性能，假设 hash 功能在桶之间正确的分散元素迭代此 set 需要的时间与 HashSet 实例大小(元素的数量)加上 HashMap 实例的 capacity (桶的数量)是成正比。因此，如果迭代性能很重要的话，那么不要设置初始 capacity 太高(或者负载因子太低)是很重要的。
  
• 注意这个实现不是线程安全的。如果多线程并发访问 HashSet ，并且至少一个线程修改了 set ，必须进行外部加锁。这通常通过在自然封装集合的某个对象上进行同步来实现
  
• 如果没有这个对象存在，这个 set 应该使用 Collections.synchronizedSet 方法重写。最好在创建时这么做，以防止对集合的意外不同步访问
  
• 这个实现持有 fail-fast 机制。
  

TreeSet 类

TreeSet 类是一个基于 TreeMap 的 NavigableSet 实现。这些元素使用他们的自然排序或者在创建时提供的 Comparator 进行排序，具体取决于使用的构造函数。

• 此实现为基本操作 add,remove 和 contains 提供了 log(n) 的时间成本。
  
• 注意这个实现不是线程安全的。如果多线程并发访问 TreeSet ，并且至少一个线程修改了 set ，必须进行外部加锁。这通常通过在自然封装集合的某个对象上进行同步来实现
  
• 如果没有这个对象存在，这个 set 应该使用

SortedSet s = Collections.synchronizedSortedSet(new TreeSet(...))

• 方法重写。最好在创建时这么做，以防止对集合的意外不同步访问
• 这个实现持有 fail-fast 机制。
  

LinkedHashSet 类

LinkedHashSet 类继承于 Set，先来看一下 LinkedHashSet 的继承体系：

LinkedHashSet 是 Set 接口的 Hash 表和 LinkedList 的实现，具有可预测的迭代次序。这个实现不同于 HashSet 的是它维护着一个贯穿所有条目的双向链表。此链表定义了元素插入集合的顺序。注意：如果元素重新插入，则插入顺序不会受到影响。

• 此实现免受 HashSet 混乱的排序。但不会导致像 TreeSet 相关的开销增加。无论原始集的实现如何，它都可用于生成与原始集合具有相同顺序的集合的副本：
  

void foo(Set s) {
  Set copy = new LinkedHashSet(s);
}

• 这个 class 提供所有可选择的 set 操作，并且允许 null 元素。像 HashSet，它为基础操作(add,contains,remove) 提供了固定的基础操作。
  
• LinkedHashSet 有两个影响其构成的参数：初始容量和加载因子。它们的定义与 HashSet 完全相同。但请注意：对于此类，选择过高的初始容量值的开销要比 HashSet 小，因为此类的迭代次数不受容量影响。
  
• 注意这个实现也不是线程安全的，如果多线程同时访问 LinkedHashSet ，并且其中一个线程修改了 set ，必须进行外部加锁。这通常通过在自然封装集合的某个对象上进行同步来实现
  
• 如果没有这样的对象存在，这个 set 应该使用 Collections.synchronizedSet 方法最好在创建时就这样做，防止意外地不同步访问该集
  
• 该类也支持 fail-fast 机制