标签（空格分隔）： Java集合框架
问题思考
- 什么是集合框架？
- 为什么用集合框架？
- 怎么用集合框架？
问题解决
什么是集合框架
1. 什么是Collection
Collection(有时候也叫container)是一个简单的对象，它把多个元素组织成一个单元。集合可以用来存储、检索、操作、通信。通常情况下，集合代表了一个自然数据项，比如一组手牌(牌的集合)、邮件文件夹(邮件的集合)、电话目录(姓名到电话的映射)。如果你使用过Java或者其他语言，你应该很熟悉集合。
JDK1.8官方文档
集合架构层次中的根接口。 集合表示一组被称为其元素的对象。 一些集合允许重复元素，而有些则不允许。 有些有序，有些无序。 JDK不提供任何这种接口的直接实现：它提供了更多特定的子接口（如Set和List）的实现。 该接口通常用于传递集合，并在需要最大的通用性的情况下对其进行操作。
2. 什么是Collections Framework
Collections Framework是一个用来表示和操作集合的统一的架构。集合的框架包括了：
-
Interfaces:
这些是表示集合的抽象数据类型，接口允许集合完成操作，独立与其详细的实现。在面向对象的语言中，接口构成了体系架构； -
Implementations:
这些是接口的具体实现。本质上，是一些可复用的数据结构； -
Algorithms:
这些方法可以对接口实现的对象进行有用的计算，比如搜索、排序。这些算法是具有多态性的：也就是说，同样的方法可以用在合适的接口的不同实现。本质上，是一些可复用的函数。
3. 集合框架体系图
-
集合框架精简图
java-coll.png-77.4kB
-
集合框架完整图
573349f70001988006430611.gif-24.2kB
-
集合框架解构图-Collection
TB21HYoeVXXXXaLXXXXXXXXXXXX_!!581166664.jpeg-46kB
-
集合框架解构图-Map
TB2JzW7eVXXXXbRXpXXXXXXXXXX_!!581166664.jpg-23.6kB
-
集合框架通用实现类
屏幕快照 2017-03-27 下午12.35.56.png-26.7kB
为什么用集合框架
-
减少编程的工作量：通过提供有用的数据结构和算法，集合框架能让你更专注的实现程序的核心功能，而不是去做一个底层的“管道工”。Java框架通过促进无关API的互操作性，使得你不用自己去实现不同API的适配
-
提高程序的速度与质量：集合框架提供了一些有用数据结构和算法的高性能、高质量的实现。每个接口的不同的实现也是可以互换的，所以程序可以通过切换集合来做一些调整。正因为你从实现数据结构的那些苦差事中脱离出来，你才可以有更多的实现去改善你自己程序的性能和质量
-
允许无关APIs的互操作：集合接口是API之间传递集合的一个“方言”，比如我的网络管理API有一个节点名的集合，而GUI工具需要一个列标题的集合，即使是分开实现它们，我们的APIs也可以无缝的接合。
-
省力地学习和使用新API：
这是另一个领先的优势，设计者和实现者没必要在每次都重新设计API的时候都“推倒重来”地实现集合，而是直接使用标准的集合接口就好了。 -
促进软件的复用：符合标准集合接口的新数据结构本质上是可以复用的。对于操作这些新数据结构算法也是一样可以复用的。
怎么用集合框架
Map接口
1. HashMap
JDK1.8官方文档
基于哈希表的Map接口实现。此实现提供了所有可选的map操作，并允许null值和null键。（HashMap类大致相当于Hashtable，除了它是非同步的，并允许null）。这个类不保证map的顺序;特别是它不能保证在一段时间内顺序保持不变。
假设散列函数把元素在桶中均匀分布，这种实现为基本操作（get和put）提供了恒定时间的性能。集合视图的迭代需要与HashMap实例的“容量”（桶数）加上其大小（键值映射数）成比例的时间。因此，如果迭代性能很重要，不要将初始容量设置得太高（或负载因子太低）。
HashMap的一个实例有两个参数影响其性能：初始容量和负载因子。容量是哈希表中的桶数，初始容量只是创建哈希表时的容量。负载因子是在容量自动增加之前测量哈希表容量有多大的百分比。当哈希表中的元素数量超过负载因子和当前容量的乘积时，重新排列哈希表（即，内部数据结构被重新构建），以使散列表具有大约两倍原容量的桶数。
作为一般规则，默认负载因子（0.75）提供了时间和空间成本之间的均衡。较高的值会降低空间开销，但会增加查找成本（反映在HashMap类的大部分操作中，包括get和put）。在设置其初始容量时，应考虑map中预期容量及其负载因子，以便最小化rehash操作的次数。如果初始容量大于最大容量数除以负载因子，则不会发生重新排列操作。
如果要将许多映射存储在HashMap实例中，则以足够大的容量创建映射将允许映射的存储效率高于使其按需要执行自动重新排序来增长表。请注意，使用具有相同hashCode（）的许多密钥是降低任何哈希表的性能的一种可靠的方法。为了改善影响，当键是可比较的时候，这个类可以使用键之间的比较顺序来帮助打破约束关系。
请注意，此实现不同步。如果多个线程同时访问哈希映射，并且至少有一个线程在结构上修改了映射，那么它必须在外部进行同步。 （结构修改是添加或删除一个或多个映射的任何操作;仅改变与实例已经包含的密钥相关联的值不是结构性修改。）这通常通过对自然地封装映射的一些对象进行同步来实现。如果没有这样的对象存在，应该使用Collections.synchronizedMap方法“包装”map。这最好在创建时完成，以防止意外的不同步访问map：
Map m = Collections.synchronizedMap（new HashMap（...））;
所有这个类的“集合视图方法”返回的迭代器都是故障快速的：如果映射在迭代器创建之后的任何时间被结构化地修改，除了通过迭代器自己的remove方法之外，迭代器将抛出一个ConcurrentModificationException 。因此，面对并发修改，迭代器将快速而干净地失败，而不是在未来未确定的时间冒着任意的非确定性行为。
请注意，迭代器的故障快速行为无法保证，因为一般来说，在不同步并发修改的情况下，无法做出任何硬性保证。失败快速的迭代器尽力地抛出ConcurrentModificationException。因此，编写依赖于此异常的程序的正确性将是错误的：迭代器的故障快速行为应仅用于检测错误。
-
官方文档重点
- 不保证有序(比如插入的顺序)，也不保证序不随时间变化
- 允许null值和null键
- 线程不安全
-
存储结构整体
public class HashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable {
transient Node<K,V>[] table;
transient Set<Map.Entry<K,V>> entrySet;
transient int size;
int threshold;
final float loadFactor;
}
- 存储结构Node
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
}
- 存储结构TreeNode
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
TreeNode<K,V> parent; // red-black tree links
TreeNode<K,V> left;
TreeNode<K,V> right;
TreeNode<K,V> prev; // needed to unlink next upon deletion
boolean red;
}
hashMap内存结构图.png-72.4kB
2. LinkedHashMap
JDK1.8文档
哈希表和链接列表实现的Map接口，具有可预测的迭代顺序。该实现与HashMap不同之处在于它保持了双向链接列表。此链接列表定义迭代排序，通常是将键插入到map（插入顺序）中的顺序。请注意，如果将键重新插入到map中，则插入顺序不受影响。（如果m.containsKey（k）在调用之前立即返回true，则调用m.put（k，v）时，将key k重新插入到映射m中。
该实现将客户端从HashMap（和Hashtable）提供的不具体的、通常是混乱的排序中区分开，而不会导致与TreeMap相关联的成本增加。无论原始map的实现如何，它都可用于生成与原始map相同顺序的map副本：
void foo（Map m）{
Map copy = new LinkedHashMap（m）;
...
}
如果模块在输入上进行映射，复制它，然后返回由该副本决定其顺序的结果，则此技术特别有用。 （客户一般都喜欢以相同的顺序返回）提供了一个特殊的构造函数来创建一个链接的哈希映射，它的迭代顺序是最后访问条目的顺序，从最近访问到最多访问的（访问顺序）。这种map非常适合建立LRU缓存。调用put，putIfAbsent，get，getOrDefault，compute，computeIfAbsent，computeIfPresent或merge方法会导致对相应条目的访问（假设调用完成后存在）。替换方法只有在替换值时才导致条目的访问。 putAll方法按照指定map的条目集迭代器提供的键值映射的顺序为指定map中的每个映射生成一个条目访问。没有其他方法生成条目访问。特别地，对于集合视图的操作不会影响后续map的迭代顺序。
当将新的映射添加到地图时，removeEldestEntry（Map.Entry）方法可能会被覆盖，以强制执行自动删除过时映射的策略。
此类提供了所有可选的Map操作，并允许null元素。像HashMap一样，它为基本操作（add，contains和remove）提供了恒定的性能，假设散列函数在桶中将元素正确分散。由于维护链接列表的额外费用，性能可能略低于HashMap，除了一个例外：对LinkedHashMap的集合视图进行迭代需要与map的大小成比例的时间，无论其容量如何。
HashMap上的迭代可能更昂贵，需要与其容量成比例的时间。
链接的哈希映射有两个参数影响其性能：初始容量和负载因子。它们的定义与HashMap相同。但是，请注意，对于初始容量来说，选择过高的值的后果没有HashMap严重，因为此类的迭代次数不受容量的影响。
请注意，此实现不同步。如果多个线程同时访问链接的散列映射，并且至少一个线程在结构上修改映射，则必须在外部进行同步。这通常通过在自然地封装map的一些对象上同步来实现。如果没有这样的对象存在，应该使用Collections.synchronizedMap方法“包装”map。这最好在创建时完成，以防止意外的不同步访问map：
Map m = Collections.synchronizedMap（new LinkedHashMap（...））;
结构修改是添加或删除一个或多个映射的任何操作，或者在访问有序链接的散列图的情况下，影响迭代顺序。在插入有序的链接散列图中，仅改变与已经包含在map中的键相关联的值不是结构修改。在访问有序的链接散列图中，只需用get查询map就是结构修改。 ）
由所有这个类的集合视图方法返回的集合的迭代器方法返回的迭代器是fail-fast：如果映射在迭代器创建之后的任何时间被结构化地修改，除了通过迭代器自己的remove方法之外，迭代器将抛出一个ConcurrentModificationException异常。因此，面对并发修改，迭代器将快速而干净地失败，而不是在未来不确定的时间冒着任意的不确定性行为。
请注意，迭代器的故障快速行为无法保证，因为一般来说，在不同步并发修改的情况下，无法做出任何硬性保证。失败快速迭代器抛出ConcurrentModifiionException尽力而为。 因此，编写依赖于此异常的程序的正确性将是错误的：迭代器的故障快速行为应仅用于检测错误。由所有此类的所有返回的集合方法返回的Spliterator方法 集合视图方法是晚期绑定，故障快速，另外报告Spliterator.ORDERED。
-
官方文档重点
- 双向链表
- 默认按插入顺序排序，即顺序确定
- 非同步，快速失败
-
结构图整体
20161116224219368.jpg-134.9kB
-
结构图循环链表
20161116224354806.jpg-118.9kB
-
大神总结
3. TreeMap
JDK1.8文档
基于Red-Black树的NavigableMap实现。该map根据其键的自然排序，或者由map创建时提供的比较器进行排序，这取决于使用哪个构造函数。此实现为containsKey，get，put和remove操作提供了保证的log（n）时间成本。算法是Cormen，Leiserson和Rivest的算法介绍中的算法的适应性。
请注意，如果此排序的map要正确实现Map接口，则由TreeMap维护的排序（如任何排序映射）以及是否提供显式比较器必须与equals一致。 （参见可比较或比较器，以获得与equals一致的精确定义）这是因为Map接口是根据equals操作定义的，但是排序的map使用compareTo（或比较）方法来执行所有的密钥比较，所以两个从排序map的角度来说，通过该方法认为相等的键是相等的。排序map的行为是明确定义的，即使其排序与equals不一致;它只是不遵守map接口的通常规定。
请注意，此实现不同步。如果多个线程同时访问map，并且至少一个线程在结构上修改映射，则必须在外部进行同步。 （结构修改是添加或删除一个或多个map的任何操作;仅改变与现有密钥相关联的值不是结构修改。）这通常通过对自然封装map的一些对象进行同步来实现。如果没有这样的对象存在，应该使用Collections.synchronizedSortedMap方法“包装”map。这最好在创建时完成，以防止意外的不同步访问map：
SortedMap m = Collections.synchronizedSortedMap（new TreeMap（...））;
由所有这个类的“集合视图方法”返回的集合的迭代器方法返回的迭代器是故障快速的：如果映射在迭代器创建之后的任何时间被结构化地修改，除了通过迭代器自己的remove方法，迭代器会抛出一个ConcurrentModificationException。因此，面对并发修改，迭代器将快速而干净地失败，而不是在未来未确定的时间冒着任意的非确定性行为。
请注意，迭代器的故障快速行为无法保证，因为一般来说，在不同步并发修改的情况下，无法做出任何硬性保证。失败快速的迭代器尽力地抛出ConcurrentModificationException。因此，编写依赖于此异常的程序的正确性将是错误的：迭代器的故障快速行为应仅用于检测错误。
由此类中的方法返回的所有Map.Entry对及其视图都代表生成map时的快照。他们不支持Entry.setValue方法。（请注意，可以使用put更改关联地图中的映射。）
- 官方文档重点
- 红黑树算法实现
- 恒定的log(n)时间复杂度
- 默认按键的自然顺序排序，但可提供比较器
- 非同步，快速失败
4. HashTable
JDK1.8官方文档
该类实现了一个哈希表，它将键映射到值。任何非空对象都可以用作键或值。要从哈希表成功存储和检索对象，用作键的对象必须实现hashCode方法和equals方法。
Hashtable的一个实例有两个影响其性能的参数：初始容量和负载因子。容量是哈希表中的桶数，初始容量只是创建哈希表时的容量。请注意，哈希表是打开的：在“哈希冲突”的情况下，单个存储桶存储多个条目，必须依次搜索。负载因子是在容量自动增加之前允许哈希表得到满足的度量。初始容量和负载因子参数仅仅是实现的提示。关于何时以及是否调用rehash方法的具体细节是依赖于实现的。
通常，默认负载因子（.75）提供了时间和空间成本之间的良好折衷。更高的值会减少空间开销，但会增加查询条目的时间（这反映在大多数Hashtable操作中，包括get和put）。
初始容量控制了浪费空间与需要重新运行操作之间的折中，这是耗时的。如果初始容量大于Hashtable将包含的最大条目数除以其负载因子，则不会发生重新排列操作。然而，设置初始容量太高可能会浪费空间。
如果将许多条目设置为Hashtable，则以足够大的容量创建它可能会使条目更有效地插入，使其根据需要执行自动重新排序以扩展表。
此示例创建数字的散列表。它使用数字的名称作为键：
Hashtable <String，Integer>数字
= new Hashtable <String，Integer>（）;
number.put（“one”，1）;
numbers.put（“two”，2）;
numbers.put（“three”，3）;
要检索一个数字，请使用以下代码：
整数n = numbers.get（“two”）;
if（n！= null）{
System.out.println（“two =”+ n）;
}
由所有这个类的“集合视图方法”返回的集合的迭代器方法返回的迭代器是fail-fast：如果Hashtable在迭代器创建之后的任何时间被结构地修改，除了通过迭代器自己的remove方法，迭代器会抛出一个ConcurrentModificationException。因此，面对并发修改，迭代器将快速而干净地失败，而不是在未来未确定的时间冒着任意的非确定性行为。 Hashtable的键和元素方法返回的枚举不是故障快速的。
请注意，迭代器的故障快速行为无法保证，因为一般来说，在不同步并发修改的情况下，无法做出任何硬性保证。失败快速的迭代器尽力地抛出ConcurrentModificationException。因此，编写依赖于此异常的程序的正确性将是错误的：迭代器的故障快速行为应仅用于检测错误。
从Java 2平台v1.2开始，该类被改造成实现Map接口，使其成为Java Collections Framework的成员。与新的集合实现不同，Hashtable是同步的。如果不需要线程安全的实现，建议使用HashMap代替Hashtable。如果需要线程安全的高并发实现，那么建议使用ConcurrentHashMap代替Hashtable。
- 官方文档重点
- 遗留类
- 不再用
Collection接口
1. HashSet
JDK1.8官方文档
此类实现了Set接口，由哈希表（实际上是HashMap实例）支持。对集合的迭代次序不作任何保证;特别是，它不能保证订单在一段时间内保持不变。此类允许null元素。
假定散列函数正确地分散在这些存储区中，这个类可以为基本操作（add，remove，contains和size）提供恒定的时间性能。迭代此集合需要与HashSet实例的大小（元素数量）加上后备HashMap实例的“容量”（桶数）的总和成比例。因此，如果迭代性能很重要，不要将初始容量设置得太高（或负载因子太低）是非常重要的。
请注意，此实现不同步。如果多个线程并发访问哈希集，并且至少有一个线程修改该集合，那么它必须在外部进行同步。这通常通过在自然地封装集合的一些对象上进行同步来实现。如果没有这样的对象存在，则该集合应该使用Collections.synchronizedSet方法“包装”。这最好在创建时完成，以防止对该集合的意外不同步访问：
设置s = Collections.synchronizedSet（new HashSet（...））;
这个类的迭代器方法返回的迭代器是故障快速的：如果在迭代器创建之后的任何时候修改了该集合，除了通过迭代器自己的remove方法之外，迭代器会抛出一个ConcurrentModificationException异常。因此，面对并发修改，迭代器将快速而干净地失败，而不是在未来未确定的时间冒着任意的非确定性行为。
请注意，迭代器的故障快速行为无法保证，因为一般来说，在不同步并发修改的情况下，无法做出任何硬性保证。失败快速的迭代器尽力地抛出ConcurrentModificationException。因此，编写依赖于此异常的程序的正确性将是错误的：迭代器的故障快速行为应仅用于检测错误。
2. LinkedHashSet
3. TreeSet
4. ArrayList
5. LinkedList
6. Vector
JDK1.8官方文档
Vector类实现可扩展的对象数组。像数组一样，它包含可以使用整数索引访问的组件。但是，Vector的大小可以根据需要增长或缩小，以适应在向量创建后添加和删除项目。
每个向量尝试通过维护容量和容量来优化存储管理。容量总是至少与矢量大小一样大;它通常较大，因为将组件添加到向量中，向量的存储以块大小增加capacityIncrement的大小。应用程序可以在插入大量组件之前增加向量的容量;这减少了增量重新分配的数量。
这个类的迭代器和listIterator方法返回的迭代器是故障快速的：如果向量在迭代器创建之后的任何时间被结构地修改，除了通过迭代器自己的remove或add方法之外，迭代器将抛出ConcurrentModificationException。因此，面对并发修改，迭代器将快速而干净地失败，而不是在未来未确定的时间冒着任意的非确定性行为。元素方法返回的枚举不是故障快速的。
请注意，迭代器的故障快速行为无法保证，因为一般来说，在不同步并发修改的情况下，无法做出任何硬性保证。失败快速的迭代器尽力地抛出ConcurrentModificationException。因此，编写依赖于此异常的程序的正确性将是错误的：迭代器的故障快速行为应仅用于检测错误。
从Java 2平台v1.2开始，这个类被改造成实现List接口，使其成为Java Collections Framework的成员。与新的集合实现不同，Vector是同步的。如果不需要线程安全的实现，建议使用ArrayList代替Vector。
7. PriorityQueue
JDK1.8官方文档
基于优先级堆的无界优先级队列。优先级队列的元素根据其自然排序，或根据队列构造时间提供的比较器进行排序，这取决于使用哪个构造函数。优先级队列不允许空元素。依靠自然排序的优先级队列也不允许插入不可比较的对象（否则可能导致ClassCastException）。
该队列的头部是相对于指定顺序的最小元素。如果多个元素被绑定到最小值，那么头就是这些元素之一 - 关系被任意破坏。队列检索操作轮询，删除，窥视和元素访问队列头部的元素。
优先级队列是无限制的，但是具有管理用于在队列上存储元素的数组的大小的内部容量。它始终至少与队列大小一样大。当元素被添加到优先级队列中时，其容量会自动增长。没有规定增长政策的细节。
该类及其迭代器实现了Collection和Iterator接口的所有可选方法。方法iterator（）中提供的迭代器不能保证以任何特定顺序遍历优先级队列的元素。如果需要有序遍历，请考虑使用Arrays.sort（pq.toArray（））。
请注意，此实现不同步。如果任何线程修改队列，多线程不应同时访问PriorityQueue实例。而是使用线程安全的PriorityBlockingQueue类。
实现注意：此实现为入队和出队方法（offer，poll，remove（）和add）提供O（log（n））时间; remove（Object）和contains（Object）方法的线性时间;和检索方法（窥视，元素和大小）的恒定时间。
网友评论