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

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、集合实现类特征图

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

08、相关集合的面试题

碍于篇幅的原因，这里就不贴出来具体的面试题和答案了，我提供了一些面试题的相关文章，请你参考

经典 Java 集合面试题 https://blog.csdn.net/u010775025/article/details/79315361

关于集合类的使用 https://github.com/hollischuang/toBeTopJavaer

Java 集合必会 14 问（精选面试题整理）https://www.jianshu.com/p/939b8a672070

相关阅读：

Comparable 和 Comparator 的理解^[7]

for 、foreach 、iterator 三种遍历方式的比较^[8]

ArrayList 相关方法介绍及源码分析^[9]

LinkedList 基本示例及源码解析^[10]

文章参考：

https://www.journaldev.com/1260/collections-in-java-tutorial#collections-class

https://blog.csdn.net/markzy/article/details/79789655

https://www.cnblogs.com/cxuanBlog/p/10927538.html

https://docs.oracle.com/javase/tutorial/collections/algorithms/

参考资料

[1]

for 、foreach 、iterator 三种遍历方式的比较: https://www.cnblogs.com/cxuanBlog/p/10927538.html

[2]

ArrayList相关方法介绍及源码分析: https://www.cnblogs.com/cxuanBlog/p/10949552.html

[3]

LinkedList 基本示例及源码解析: https://www.cnblogs.com/cxuanBlog/p/10952578.html

[4]

图解集合6：LinkedHashMap: https://www.cnblogs.com/xrq730/p/5052323.html

[5]

Comparable 和 Comparator的理解: https://www.cnblogs.com/cxuanBlog/p/10927495.html

[6]

JAVA基础——Arrays工具类十大常用方法: https://www.cnblogs.com/hysum/p/7094232.html

[7]

Comparable 和 Comparator的理解: https://www.cnblogs.com/cxuanBlog/p/10927495.html

[8]

for 、foreach 、iterator 三种遍历方式的比较: https://www.cnblogs.com/cxuanBlog/p/10927538.html

[9]

ArrayList相关方法介绍及源码分析: https://www.cnblogs.com/cxuanBlog/p/10949552.html

[10]

LinkedList 基本示例及源码解析: https://www.cnblogs.com/cxuanBlog/p/10952578.html