最全的集合干货送给大家（三）-阿里云开发者社区

AbstractQueue 抽象类

这个类是 Queue 接口的骨干实现，当实现不允许为 null 元素时，使用此类中的实现是比较合适的。add, remove, element 是基于 offer, poll 和 peek 方法的。扩展此类 Queue 实现必须最低开销的定义一个方法 Queue.offer，该方法不允许插入 null 元素，以及方法 peek，poll，size，iterator。通常，还会覆盖其他方法。如果无法满足这些要求，请考虑用继承替代。

PriorityQueue 类

PriorityQueue 是 AbstractQueue 的实现类，优先级队列的元素根据自然排序或者通过在构造函数时期提供 Comparator 来排序，具体根据构造器判断。一个优先级队列不允许 null 元素依赖于自然排序的优先级队列也不允许插入不可比较的对象（这样做可能导致 ClassCastException ）。

队列的头在某种意义上是指定顺序的最后一个元素。队列检索操作 poll, remove, peek 和 element 访问队列头部元素。
优先级队列是无限制的，但具有内部 capacity，用于控制用于在队列中存储元素的数组大小。它总是至少像 queue 的容量一样大。作为新添加进来的元素，它的容量会自动增长。
该类以及迭代器实现了 Collection、Iterator 接口的所有可选方法。这个迭代器提供了 iterator() 方法不能保证以任何特定顺序遍历优先级队列的元素。如果你需要有序遍历，考虑使用 Arrays.sort(pq.toArray())。
注意这个实现不是线程安全的，多线程不应该并发访问 PriorityQueue 实例如果有某个线程修改了队列的话，使用线程安全的类 PriorityBlockingQueue。

AbstractSequentialList 抽象类

AbstractSequentialList 是 List 一系列子类接口的核心接口，以求最大限度的减少实现此接口的工作量，由顺序访问数据存储(例如链接链表)支持。对于随机访问的数据(像是数组)，应该优先使用 AbstractList。

在这个概念上，这个接口可以说是与 AbstractList 类相反的，它实现了随机访问方法，提供了 get(int index), set(int index,E element), add(int index,E element) 和 remove(int index) 方法在列表的迭代器上
要实现一个列表，程序员只需要扩展这个类并且提供 listIterator 和 size 方法即可。对于不可修改的列表来说，程序员需要实现列表迭代器的 hasNext(), next(), hasPrevious(), previous() 和 index() 方法
对于允许修改的 list，程序员应该额外实现 list 迭代器的 set 方法，对于可变大小的列表，程序员应该额外实现迭代器的 r emove 方法和 add 方法

LinkedList 类

LinkedList 是一个双向链表，实现了所有 List 列表的可选择性操作，允许存储任何元素(包括 null 值)。它的主要特性如下：

LinkedList 所有的操作都可以表现为双向性的，索引到链表的操作将遍历从头到尾，视哪个距离近为遍历顺序。
注意这个实现也不是线程安全的，如果多个线程并发访问链表，并且至少其中的一个线程修改了链表的结构，那么这个链表必须进行外部加锁。(结构化的操作指的是任何添加或者删除至少一个元素的操作，仅仅对已有元素的值进行修改不是结构化的操作)。
如果没有这样的链表存在，这个链表应该用 Collections.synchronizedList 方法进行包装，最好在创建时间就这样做，避免意外的非同步对链表的访问

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

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

03、Map 接口

Map 是一个支持 key-value 存储的对象，Map 不能包含重复的 key，每个键最多映射一个值。这个接口代替了 Dictionary 类，Dictionary 是一个抽象类而不是接口。

Map 接口提供了三个集合的片段，它允许将 map 的内容视为一组键，值的集合和一组 key-value 映射。map 的顺序定义为 map 映射集合上的迭代器返回其元素的顺序。一些 map 实现，像是 TreeMap 类，保证了 map 的次数；其他的实现，像是 HashMap，则没有保证。
一般用途的 map 实现类应该提供两个标准的构造器：一个空 map 创建一个 void (无参数)构造器。和一个只有单个 Map 类型参数的构造器。后者的构造器允许用户复制任意 map，生成所需类的有效映射。无法强制执行此建议(因为接口不能包含构造器)但 JDK 中的所有通用映射实现都符合要求。
一些 map 实现包含在内的对键和值有限制例如，一些实现禁止 null keys 和 values，一些实现对 keys 的类型有限制。尝试插入不合格的键或值会引发未经检查的异常，比如 NullPointerException 或者 ClassCastException 尝试查询不合格的 key 或 value 也可能抛出异常，或者可能返回 false；一些实现允许前者的行为，一些实现允许后者的行为

AbstractMap 抽象类

这个抽象类是 Map 接口的骨干实现，以求最大化的减少实现类的工作量。

为了实现不可修改的 map，程序员仅需要继承这个类并且提供 entrySet 方法的实现，它将会返回一组 map 映射的某一段。通常，返回的集合将在 AbstractSet 之上实现。这个 set 不应该支持 add 或者 remove 方法，并且它的迭代器也不支持 remove 方法。
为了实现可修改的 map，程序员必须额外重写这个类的 put 方法(否则就会抛出 UnsupportedOperationException)，并且 entrySet.iterator() 返回的 iterator 必须实现 remove() 方法。
程序员应该提供一个无返回值(无参数)的 map 构造器，

HashMap 类

哈希表基于 Map 接口的实现，这个实现提供可选择的 map，并且允许空 value 值和空 key，可以认为 HashMap 是 Hashtable 的增强版，可以认为 HashMap 不是可同步的(非线程安全)和允许空值外，可以认为 HashMap 顺序性，也就是说，它不能保证其内部的顺序一成不变

这个实现为基本操作 (get、set) 提供了固定开销的性能，假设哈希函数将元素均匀的分散在各个桶中，遍历结束这个 Collection 的视图需要恒定的时间，包括 HashMap 实例(桶的数量)加上( key-value 映射的数量)。因此，如果遍历元素是很重要的话，不要去把初始容量设置的太高(或者负载因子太低)。
一个 HashMap 实例有两个参数扮演着重要的角色，初始容量和负载因子，这个初始容量是 hash 表桶的数量，并且初始容量只是创建哈希表时的最初的容量，这个负载因子是一种衡量哈希表的填充程度，在其容量自动增加之前获取，当哈希表中存在足够数量的 entry，以至于超过了负载因子和当前容量，这个哈希表会进行重新哈希操作，内部的数据结构重新 rebuilt，这样的哈希表大约有两倍的桶数量
作为一般的规则，这个默认的负载因子 0.75 提供了一个好的平衡点在时间和空间利用上面，这个值越高，就越会降低空间开销，但是会增加查找成本(反应在大部分 HashMap 的操作上面包括 get 、 put )，预期数量 map 中的 entry 链和加载因子当设置初始容量的时候应该被考虑进去，以便降低最小数量的重新 hash 操作。如果初始容量要比(最大数量的 entry 链/负载因子)大则不用重新哈希，将一直能够操作。
注意这个实现类 (HashMap) 不是同步的(非线程安全的)，如果多个线程同时影响到了 hash map，并且至少一个线程修改了 map 的结构，那么必须借助外力的同步操作。( adds 或者 deletes 一个或多个映射是一个结构化的修改操作。仅仅改变 key 的 value 值不是一个结构化的修改)。如果不存在此类对象，这个 map 应该被 Collections.synchronizedMap 封装，最好是在创建的时候就封装好，去阻止偶然的对 map 的非同步访问

Map m = Collections.synchronizedMap(new HashMap());

支持 fail-fast 快速失败机制

TreeMap 类

一个基于 NavigableMap 实现的红黑树。这个 map 根据 key 自然排序存储，或者通过 Comparator 基于 NavigableMap 实现的红黑树。这个 map 根据 key 自然排序存储，或者通过 Comparator 进行定制排序

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

SortedMap m = Collections.synchronizedSortedMap(new TreeMap(...))

方法重写。最好在创建时这么做，以防止对集合的意外不同步访问
这个实现持有 fail-fast 机制。
此类中的方法返回所有的 Map.Entry 对及其试图表示生成时映射的快照。他们不支持 Entry.setValue 方法

LinkedHashMap 类

LinkedHashMap 是 map 接口的哈希表和链表的实现，具有可预测的迭代顺序。这个实现与 HashMap 不同之处在于它维护了一个贯穿其所有条目的双向链表。这个链表定义了遍历顺序，通常是插入 map 中的顺序。注意重新插入并不会影响其插入的顺序。如果在 containsKey(k) 时调用 m.put(k,v)，则将 key 插入到 map 中会在调用之前返回 true。

此实现使其客户端免受 HashMap, Hashtable 未指定的，混乱的排序。而不会导致像 TreeMap 一样的性能开销，无论原始 map 的实现如何，它都可用于生成与原始 map 具有相同顺序的 map 副本。

void foo(Map m) {
  Map copy = new LinkedHashMap(m);
}

它提供一个特殊的 LinkedHashMap(int,float,boolean) 构造器来创建 LinkedHashMap，其遍历顺序是其最后一次访问的顺序。这种类型的 map 很适合构建 LRU 缓存图解集合 6：LinkedHashMap^[4]
可以重写 removeEldestEntry(Map.Entry) 方法，以便在将新映射添加到 map 时强制删除过期映射的策略。
这个类提供了所有可选择的 map 操作，并且允许 null 元素。像 HashMap，它为基础操作(add,contains,remove)提供了恒定的时间消耗，假定散列函数在桶之间正确分配了元素。由于维护链表的额外开销，性能可能会低于 HashMap，有一条除外：遍历 LinkedHashMap 中的 collection-views 需要与 map.size 成正比，无论其容量如何。HashMap 的迭代看起来开销更大，因为还要求时间与其容量成正比。
LinkedHashMap 有两个因素影响了它的构成：初始容量和加载因子。他们也定义在 HashMap。注意，对于此类，选择过高的容量的初始值代价小于 HashMap，因为此类的迭代次数不受容量的影响。
注意这个实现不是线程安全的。如果多线程并发访问 LinkedHashMap，并且至少一个线程修改了 map，必须进行外部加锁。这通常通过在自然封装集合的某个对象上进行同步来实现
如果没有这个对象存在，这个 set 应该使用

Map m = Collections.synchronizedMap(new LinkedHashMap(...))

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

Hashtable 类

Hashtable 类实现了一个哈希表，能够将键映射到值。任何非空对象都可以用作键或值。

为了从哈希表中成功存储和检索对象，这个对象的 key 必须实现 hashCode 方法和 equals 方法。
Hashtable 的实例有两个参数影响它的构成：初始容量和加载因子。容量就是哈希表中桶的数量，初始容量就是哈希表创建出来的容量。注意这个哈希表是开放的：为了避免哈希冲突，一个桶存储了多个 entries 必须按顺序搜索。负载因子是衡量哈希表在其容量自动增加之前可以变得多大。初始容量和负载系数参数仅仅是实现的提示。关于何时以及是否调用 rehash 方法的确切细节是依赖于实现的
大致上来说，默认的负载因子 0.75 提供了一个空间和时间开销的平衡。此值太高会减少空间开销但是会增加查找的时间成本，这会反应在 get、put 操作中。
初始容量控制了浪费空间与 rehash 操作需求之间的权衡，这是非常耗时的。如果初始容量 > entries 链条数目 / load factor，则 rehash 操作永远不会发生。然而，设置初始容量太高会浪费空间。
下面例子展示了一个基础用法

// 放置元素
Hashtable<String, Integer> numbers = new Hashtable<String, Integer>();
numbers.put("one", 1);
numbers.put("two", 2);
numbers.put("three", 3);
// 取出元素
Integer n = numbers.get("two");
if(n != null){
  System.out.println("two = " + n);
}

此实现类支持 fail-fast 机制
与新的集合实现不同，Hashtable 是线程安全的。如果不需要线程安全的容器，推荐使用 HashMap，如果需要多线程高并发，推荐使用 ConcurrentHashMap。

IdentityHashMap 类

IdentityHashMap 是比较小众的 Map 实现了，它使用哈希表实现 Map 接口，在比较键和值时使用引用相等性替换对象相等性。换句话说，在 IdentityHashMap 中两个 key，k1 和 k2 当且仅当 k1 == k2 时被认为是相等的。(在正常的 Map 实现中(类似 HashMap)，两个键 k1 和 k2 当且仅当 k1 == null ? k2 == null : k1.equals(k2)时被认为时相等的

这个类不是一个通用的 Map 实现！虽然这个类实现了 Map 接口，但它故意违反了 Map 的约定，该约定要求在比较对象时使用 equals 方法，此类仅适用于需要引用相等语义的极少数情况。
此类提供所有可选择的 map 操作，并且允许 null 值和 null key。这个类不保证 map 的顺序，特别的，它不保证顺序会随着时间的推移保持不变。
同 HashMap，IdentityHashMap 也是无序的，并且该类不是线程安全的，如果要使之线程安全，可以调用 Collections.synchronizedMap(new IdentityHashMap(...))方法来实现。
支持 fail-fast 机制

WeakHashMap 类

WeakHashMap 类基于哈希表的 Map 基础实现，带有弱键。WeakHashMap 中的 entry 当不再使用时还会自动移除。更准确的说，给定 key 的映射的存在将不会阻止 key 被垃圾收集器丢弃。

基于 map 接口，是一种弱键相连，WeakHashMap 里面的键会自动回收
支持 null 值和 null 键。和 HashMap 有些相似
fast-fail 机制
不允许重复
WeakHashMap 经常用作缓存关于 HashMap 的具体存储结构

相关更详细的 WeakHashMap 解析，见下面这篇文章 http://ifeve.com/weakhashmap/

SortedMap 抽象类

SortedMap 是一个提供了在 key 上全部排序的 map。这个 map 根据 key 的 Comparable 自然排序，提供了在创建时期的 map 排序。遍历有序映射的集合片段(由

entrySet、keySet 和 values 方法返回)时能够反应此顺序的影响。

所有插入到 sorted map 的 key 都必须实现 Comparable 接口(或者接受定制的 Comparator 接口)。进一步来讲，所有的 key 都必须相互比较形如 k1.compareTo(k2) 或者 comparator.compare(k1,k2) 对其中的任何 key 都不能抛出 ClassCastException。试图违反此限制将导致违规方法或构造函数抛出 ClassCastException
所有一般情况下的 sortedmap 实现类提供四个标准的构造器。

一个无返回值(无参数)的构造器，它根据 key 的自然排序创建类一个空 sorted map。
一个有单个 Comparator 类型参数的构造函数，它根据指定比较器创建了一个空的 sorted map 排序。
一个有单个 map 类型参数的构造函数，它创建了一个相同 key-value 映射参数的 map，根据 key 来自然排序。
一个有单个 SortedMap 类型的构造器，它创建了一个新的有序映射，其具有相同的键 - 值映射和与输入有序映射相同的顺序。

04、Comparable && Comparator

具体描述请详见Comparable 和 Comparator 的理解^[5]

05、Collections 类

Collections 不属于 Java 框架继承树上的内容，它属于单独的分支，Collections 是一个包装类，它的作用就是为集合框架提供某些功能实现，此类只包括静态方法操作或者返回 collections。

同步包装

同步包装器将自动同步（线程安全性）添加到任意集合。六个核心集合接口（ Collection，Set，List，Map，SortedSet 和 SortedMap）中的每一个都有一个静态工厂方法。

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

不可修改的包装

不可修改的包装器通过拦截修改集合的操作并抛出 UnsupportedOperationException，主要用在下面两个情景：

构建集合后使其不可变。在这种情况下，最好不要去获取返回 collection 的引用，这样有利于保证不变性
允许某些客户端以只读方式访问你的数据结构。你保留对返回的 collection 的引用，但分发对包装器的引用。通过这种方式，客户可以查看但不能修改，同时保持完全访问权限。

这些方法是：

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

线程安全的 Collections

Java1.5 并发包 (java.util.concurrent) 提供了线程安全的 collections 允许遍历的时候进行修改，通过设计 iterator 为 fail-fast 并抛出 ConcurrentModificationException。一些实现类是CopyOnWriteArrayList，ConcurrentHashMap，CopyOnWriteArraySet

Collections 算法

此类包含用于集合框架算法的方法，例如二进制搜索，排序，重排，反向等。

有兴趣的读者可以阅读https://docs.oracle.com/javase/tutorial/collections/algorithms/ 本篇暂不探讨算法问题。

06、Arrays 类

这个类包含各种各样的操作数组的方法(例如排序和查找)。这个类也包含一个静态工厂把数组当作列表来对待。如果指定数组的引用为 null，这个类中的方法都会抛出 NullPointerException，除非有另外说明。

详细的用法请参考JAVA 基础——Arrays 工具类十大常用方法^[6]

07、集合实现类特征图

下图汇总了部分集合框架的主要实现类的特征图，让你能有清晰明了看出每个实现类之间的差异性

集合	排序	随机访问	key-value 存储	重复元素	空元素	线程安全
ArrayList	Y	Y	N	Y	Y	N
LinkedList	Y	N	N	Y	Y	N
HashSet	N	N	N	N	Y	N
TreeSet	Y	N	N	N	N	N
HashMap	N	Y	Y	N	Y	N
TreeMap	Y	Y	Y	N	N	N
Vector	Y	Y	N	Y	Y	Y
Hashtable	N	Y	Y	N	N	Y
ConcurrentHashMap	N	Y	Y	N	N	Y
Stack	Y	N	N	Y	Y	Y
CopyOnWriteArrayList	Y	Y	N	Y	Y	Y