《On Java8》 12.集合

[funnycoding]

《On Java8》第十二章 集合

【集合章节是一个大章节我本次的目标】

1. 复习集合数据结构，明确不同集合的特性以及这些特性是怎样实现的
2. 深入到源码级别的学习，不是只停留在概念上，而是针对概念从代码和注释来求证其具体实现过程
3. 深入面试重点的HashMap ，面试中几乎必问的典型问题。

【学完之后看这一条，是没有达到的，因为书中并没有给予 HashMap 过多的篇幅，因为这章更大成分上是一个基础教学章节，告诉了读者各个集合的特性以及基本的操作，对HashMap的描述就是一句优化过的 映射集，具体更多的细节应该要到附录里那篇更深入的 集合章节去讲了】

如果一个程序只包含固定数量的对象并且对象的生命周期都是已知的，那么这是一个非常简单的程序。

【但是实际编程中我们使用集合大多是在数量未知的情况下使用，比如查询数据库中的数据。】

java.util 库提供了一套完整的集合类 Collection Framework 集合提供了完善的方法来保存对象，可以使用这些工具来解决大量问题。

集合中不同数据结构有一些其他的特性

【这些特性就是我所要关注的东西，以及这个特性具体是怎么来的。具体到源码级别】

泛型和类型安全的集合

【这章比较简单，概括一下就是使用泛型可以限定集合中保存对象的种类，减少以前保存 Obejct 对象可能存在的强制类型转换出现的运行时问题，把问题提前到了编译期】

当泛型参数与多态结合起来时，并不仅限于将确定类型的对象放入结合中，向上转型也可以像作用于其他类型一样作用于泛型：

程序输出是从 Object 的 toString() 方法产生的，该方法打印类名，后边跟着对象的散列吗的无符号十六进制（这个散列吗是通过 hashCode() 方法产生的)

基本概念

Java 采用集合类库 持有对象，并将其分为两个不同的概念，表示为类库的基本接口

1. 集合 （Collection) ：一个独立元素的序列，这些元素都服从一条或多条规则。
   • List 必须保证以插入的顺序保存元素
   • Set 不能包含重复元素
   • Queue 按照 排队规则 来确定对象产生的顺序（通常与它们被插入的顺序相同）
2. 映射 （Map）：一组成对的 键值对 对象，允许使用键来查找值。 ArrayList 使用数字来查找对象，因此在某种意义上讲，它是将数字和对象关联在一起。 map 允许我们使用一个对象来查找另一个对象，它也被称为 关联数组 因为它将对象与其他对象关联在一起。【表示关联数组 来称呼map 真没遇见过，字典到是很多】，或称作 字典。

Collection 接口概括了 List（序列） 的概念 ——一种存放一组对象的方式。 下面是个简单的示例。

这里只使用了 Collection中的方法（ add() ) ，所以使用任何继承 Collection 的对象都可以工作。

这里 add 方法说要确保 Collection 包含指定的元素（该操作可选） 是因为考虑到了 Set 的含义，因为在 Set 中，只有当元素不存在时才会添加元素。 在使用 ArrayList 或 任何其他类型的 List时， add() 总是表示 “把这个元素放入容器” ，因为 List 不关心是否存在重复元素。

添加元素组

【主要讲了下使用 Arrays 和 Collections 工具类直接添加一组元素的操作，很基础，不过看了下还是有些小的知识点可以注意下。】

这里作者说 Collections.addAll() 运行速度更快，而且很容易构建一个不包含元素的Collection ，所以优先选用这种方式。

Collection 的构造器可以接受另一个 Collection，用它来将自身初始化， 就像这样：

Collection 的 addAll() 方法只接受另一个 Collection 作为参数 所以没有工具类中的 addAll 灵活。

Collection:

Collections:

也可以直接使用 Arrays.asList() 输出一个 List，但是这里的底层实现是 数组 没法调整大小。如果尝试在这个 List 上调用 add() / remove() 方法，由于这两个方法会尝试修改数组大小，所以会在运行时抛出 " Unsupported Operation 不支持操作" 错误

【这个知识点倒是第一次知道，先看源码：】

返回由指定数组支持的固定大小的List

实际构建数组的地方：

【确实抛出了异常】

注意 snow4 ，这里告诉编译器 Arrays.asList() 生成的 List 类型的实际类型参数是什么，这里称为 显示类型参数说明【但是好像没什么用，因为ide提示这个是多余的，应该是可以根据 前面List<snow》 进行参数推导得出。

集合的打印

打印数组的时候必须使用 Arrays.toString() 但是打印集合无需任何帮助直接输出即可。

先看 集合框架里的 toString() 方法是怎么定义的。

该方法是在 AbstractCollection 中进行的定义

【

返回此集合的字符串表示形式。

字符串表示形式包含一个集合元素的列表，这些元素按其迭代器返回的顺序排列，并括在方括号（“ []”）中。

相邻元素之间用字符“，”（逗号和空格）分隔。

元素通过String.valueOf（Object）转换为字符串。

】

【我又加了几个元素，这样就能看到 HashSet 的无序性了:】

这个例子就很好的展示各个集合的不同特性：

首先集合类库分为两个主要类型 Collection 和 Map。

它们的主要区别在于集合中的每个 槽 slot 保存元素的个数， Collection 每个只保存一个元素，Map 则存放了两个元素，即 键——值。

ArrayList 和 LinkedList 按插入顺序保存元素。这两者之间的区别不仅在于执行某些类型操作时的性能，而且 LinkedList 包含的操作多于 ArrayList 。在之后一章详细探索。

HashSet ，TreeSet，LinkedHashSet 是 Set类型，从输出中可以看到， Set 不存储重复数据，并且不同 Set 实现存储元素的方式也不同。

HashSet 使用相当复杂的方法存储元素，现在只需要知道 这种技术是检索元素最快的方法。因此存储顺序看上去没有意义（当只关心某事物是否是 Set 成员 而存储顺序不重要的情况下）。

如果存储顺序很重要，则可以使用 TreeSet，它将按照比较结果升序保存对象

【问题：】

【确实，按照英文字母的排序顺序保存，但是这里仅仅是字符串元素，如果是复杂的对象呢？】

【LinkedHashSet 按照元素添加顺序保存对象。】

Map 使用 Key 来查找对象，就像一个简单的数据库。所关联的对象称为 Value(值)

Map中的 Key 只存储一次。【后面再put 相同key，则value会进行覆盖】

HashMap中保存的 key-value 不是插入顺序，因为 HashMap 实现了非常快速的算法来控制顺序。

TreeMap 跟 TreeSet一样，根据比较结果的升序来保存 Key。

LinkedHashMap 在保持 HashMap 查找速度的同时**按 Key 的插入顺序保存 Key。**

列表 List

List 承诺将元素保存在特定的序列中。 List 在 Collection 的基础上增添了许多方法，允许在 List 的中间 **插入 和 删除**元素

有两种类型的 List：

• 基本的 ArrayList 查询快，在List中间 增删慢。
• LinkedList 在List中插入和删除的速度快，优化了顺序访问。 LinkedList 对于随机访问来说速度慢，但是比 ArrayList 的特征集更大。

看代码：

【这个类实际上是对各种工具类 API 的使用与总结，没有很复杂的结构】

当确定元素是否属于某个 List 寻找某个元素的索引，以及通过引用从 List 中删除元素时，都会用到 equals() 方法 【这个很关键，需要追根溯源看一下源码】请务必注意 List 行为会根据 equals() 行为而发生变化。

1. IndexOf 与 equals() 之间的关联

2. remove() 与 equals() 之间的关联

3. retainAll() 与 equals() 之间的关联

可以在 List 中间插入元素，就像输出9那样，但是这会带来一个问题：对于 ArrayList 来说，插入元素是代价高昂的操作。是否意味着永远不应该在 ArrayList 的中间插入元素，并最好转换为 LinkedList？ 不，它只是意味着你应该知道这个问题，如果你开始在某个 ArryList 中间执行很多插入操作，并且程序开始变慢，那么你应该知道 使用不恰当的数据结构就是罪魁祸首（发现此类瓶颈最佳方式是使用分析器 profiler)

【所以一定要明白数据结构的正确使用方法】

subList() 从更大的列表中创建子List 切片

retainAll()是一个 “集合交集” 操作，再次注意，产生的结果行为依赖于 equals()方法 第14个输出语句展示了使用索引来删除元素的结果，与通过对象来删除元素相比，它显得更加直观，因为在使用索引时，不必担心 equals() 行为【这里怎么解？】

removeAll() 方法也基于 equals() 方法运行的.

set() 方法的命名不合时宜，因为它与 Set 类存在潜在冲突，这里使用 replace 可能更合适，因为他的功能是使用第二个参数替代 第一个索引参数处的元素

迭代器 Iterators

任何集合中，都必须有某种方式可以插入元素并再次获取它们。对于 List 来说，add() 是插入元素的方式，get() 是获取元素的方式。

如果从更高层次的角度考虑问题，会发现有个缺点：要使用集合，必须对集合的确切类型编程：

• 如果原本是使用 List 编码的，后来发现如果能够将相同的代码应用于 Set 会更方便，此时应该怎么做？ 如果假设想从一开始就编写一段通用代码，它不关心正在使用什么类型的集合，因此她可以用于不同类型的集合。 那么如何才能不重写代码就可以应用于不同类型的集合？

List list = new ArrayList(); 【这样使用接口来创建集合？】

迭代器（也是一种设计模式） 的概念实现了这种抽象。

迭代器是一个对象，它在一个序列中移动并选择该序列中的每个对象，而客户端程序员不知道或不该关心底层序列的数据结构。

迭代器通常被称为轻量级对象，因为其创建代价小。因此经常可以看到一些对 迭代器的奇怪约束，比如 Java 中的 Iterator 只能单向移动，Iterator 只能用来：

1. 使用 iterator() 方法要求集合返回一个 Iterator。该 Iterator 将准备好返回序列中的第一个元素。
2. 使用 next() 方法获得序列中的下一个元素。
3. 使用 hasNext() 方法检查序列中是否还有元素。
4. 使用 remove() 方法，将迭代器最近返回的那个元素删除。

有了 Iterator，就不必在为集合中元素的数量操心了。 这是由 hasNext() 和 next() 关心的事情。

如果只遍历 List ，并不打算修改其对象本身，使用 for-in 语法更简单。

Iterator 可以删除由 next() 生成的最后一个元素，这意味着调用 remove() 之前必须调用 next

看一下源码，为什么调用 remove() 之前必须调用 next()

1. ArrayList 中 Iterator 的实现：

这个字段 在删除的时候需要使用，默认值为 -1

调用 next 对这个值进行赋值

如果没有调用 next ，默认值为-1的情况下调用 remove 则抛出该异常

现在考虑创建一个 display() 方法，不必知道具体的集合类型：

这里遍历不同的集合，只需要获取其迭代器就可以遍历该集合所有元素，而不必知道其确切集合类型。

display() 方法不包含任何关于它所遍历的集合的类型信息，这也展示了 Iterator 将遍历集合的操作与集合的底层结构分离的威力，出于这个原因，我们有时会说：迭代器统一了对集合的访问方式。

我们可以使用 Iterator 接口生成上一个示例更简洁的版本，该接口描述了可以产生 Iterator 的任何东西：

【这句话没太理解，直接看代码吧】

【看完代码明白了，只要类实现了Iterable 则必然可以产生 Iterator，所以方法参数直接将最顶层父类作为参数就可以进一步简化调用】

放2张图就都懂了。

List Iterator

ListIterator 是一个功能更为强大的 迭代器子类。它只能由各种 List 类生成。

Iterator 只能向前移动【那么问题来了，想访问后一个元素咋办？】，而 ListIterator 可以双向移动【牛逼了】。

它还可以生成相对于迭代器在列表中指向的当前位置的后一个和前一个元素的索引，并且可以使用 set() 方法替换它访问过的最近一个元素。

可以通过 listIterator() 方法来生成指向 List 开头的 ListIterator，还可以传入一个参数 listIterator(n) 创建一个从一开始就指向索引为n处元素的 ListIterator。

下面上代码：

public class ListIterator {
    public static void main(String[] args) {
        List<Pet> pets = Pets.list(8);
        java.util.ListIterator<Pet> it = pets.listIterator();

        // 打印所有元素和 以及下一个元素和上一个元素的索引值
        while (it.hasNext()) {
            System.out.print(it.next() + ", " + it.nextIndex() + ", " + it.previousIndex() + "; ");
        }
        System.out.println();

        // 打印前一个元素:
        while (it.hasPrevious()) {
            System.out.print(it.previous().id() + " ");
        }
        System.out.println();

        // 打印整个集合
        System.out.println(pets);

        // 获取从第三个元素开始的迭代器
        it = pets.listIterator(3);
        while (it.hasNext()) {
            it.next();
            // 替换List从第三个开始的元素
            it.set(Pets.get());
        }

        System.out.println("last" + pets);
    }
}

Pets.get() 方法用来从位置 3 开始替换 List 中的所有 Pet 对象。

【最主要的特性还是 ListIterator 可以双向移动】

【那么问题来了，这里又需要看代码是怎样实现的双向移动的了】

ListIterator 的源码级分析

链表 LinkedList

LinkedList 也像ArrayList 一样实现了基本的 List 接口，但是它在 List 中间执行 插入 /删除 操作时 比 ArrayList 更高效。然而 随机访问操作耗时比 ArrayList 要更高。

【那么问题来了，概念是这么说的，具体是怎样实现才导致了 LinkedList 和 ArrayList 之间的差异呢？这肯定是根据不同使用创建来设计的不同数据结构，这需要看源码来探究原因】

LinkedList 还添加了一些方法，使其可以被用作栈、队列或双端队列(deque)。在这些方法中，有些比彼此之间可能只是一些名称有差异，或者只存在些许差异，以使得这些名字在特定用法的上下文中更加适用（特别是在 Queue 中）

【为什么这么说？】

例如：

• getFirst() 和 element() 是相同的，它们都返回列表的第一个元素，而并不删除它，如果 List 为空，则抛出 NoSuchElementException 异常。 peek() 方法与这两个方法稍有差异，当列表为空时返回 null；
• removeFirst() 和 remove() 也是相同的，它们删除并返回列表的头部元素，并在列表为空时抛出 NoSuchElementException异常， poll() 稍有差异，它在列表为空时 返回 null。
• addFirst() 在列表的开头插入一个元素。
• offer() 与 add() 和 addLast() 相同。 它们都在列表的尾部添加一个元素。
• removeLatst() 删除并返回列表的最后一个元素。

【那么问题来了，为什么有这些功能相同的方法呢？万事不决看源码】

1. getFirst() / element()

看完这俩我明白了，elemtn 不就是对 getFirst() 的封装吗？

poll / removeFirst / remove

看完源码我决定回过头看作者刚才的说明【些比彼此之间可能只是一些名称有差异，或者只存在些许差异，以使得这些名字在特定用法的上下文中更加适用】

【看来还得继续往下学，下面应该有这题的答案，看到 Queue 和 Deque 的时候看看有没有收获】

下面的示例展示了这些功能之间的相似性和差异性。它并不是重复执行 ListFeatures.java 中所示的行为

这个例子很简单，就是对不同的 API 的调用。

Pets.list() 的结果被传递给 LinkedList 的构造器，以便使用它来填充 LinkedList。

如果查看 Queue 接口就会发现吗，它在 LinkedList 的基础上添加了 element()

offer() ,peek() poll() remove() 方法，以使其可以完成一个 Queue 的实现。

【问题来了，这些方法 LinkedList 也存在啊，并不能说是在其基础上添加的】

堆栈 Stack

堆栈的数据结构特点： 后进先出（LIOF），所以往堆栈中添加元素的操作也叫做压栈，可以将堆栈想象成弹匣，先弹出的总是后压入的子弹。

它有时被称为 叠加栈(pushdown stack)，因为最后压入的栈的元素，第一个被弹出。

Java 1.0 中附带了一个 Stack 类，但是设计的很糟糕（为了向后兼容，这些错误的设计被保留了下来）

Java 6 添加了 ArrayDeque类，其中包含直接实现了堆栈功能的方法，看代码：

这里可以看出 弹出元素的顺序与添加元素的相反，同时，即时该数据结构被作为一个堆栈在使用，我们仍然必须将其声明为 Deque。

有时一个命名为 Stack 的类更能把事情讲清楚。

这里引入了使用泛型的类定义的最简单的示例。类名称后面的 类型参数 《T》 告诉编译器这是一个参数化类型，而其中的类型参数 会在使用类时被实际的类型替换。

所以这个类是在声明 【我们再定义一个可以持有类型 T 对象的 Stack】 ，Stack 是用 ArrayDeque 实现的， 而 ArrayDeque 也被告知它将持有 T 类型对象。

Api:

• push() 将元素入栈

• peek () 方法返回栈顶元素

• pop() 删除并返回栈顶元素

下面将写测试代码来演示这个类的功能：

很简单，就不多说了。

这里还需要注意下类名可能的冲突，因为我们的类与 java.util 中的 Stack 发生冲突，所以如果我们要指名使用自己的类需要用全限定符来定位：

【很简单，没啥好说的，Stack 这块就完事了，记得 ArrayDeque 实现了 Stack的功能，以及 Java 最早的Stack 有重大缺陷就完事了。但是这个缺陷在哪里，还得去看源码！】

Stack缺陷源码分析

集合 Set

Set 不保存重复的元素。如果试图将相同对象的多个实例添加到 Set 中，它会组织这种重复行为。 Set 最常见的用途是测试归属性，可以轻松查询某个对象是否在一个 Set 中。因此，查找通常是Set最重要的操作，通常使用 HashSet实现，因为该实现对快速查找进行了优化。

好了，上面的一段话有不少信息，但是有很多是需要深入到具体代码的:

• Set 不保存重复元素【深入代码—为什么不保存，是根据什么来计算是否重复的，虽然我知道是根据 hash 算法，但是只知道这个还是不够的。】
• Set 最常用的是测试归属性，查询某元素是否在 Set 中存在 【用途，或者我最常用的是拿 Set 来去重。】
• Set 最常用实现是 HashSet，其对快速查询进行了优化【这个是必须看代码才能分析的了，怎样对查询性能进行优化的。】

Set 与 Collection 的接口相同，因此没有任何额外功能，不像前面两种不同类型的 List 【那么问题来了， List 的额外功能呢？我好像没有总结】，实际上 Set 就是一个 Collection，只是行为不同（这是继承和多态思想的典型应用：表现不同的行为） Set 根据对象的 ”值” 确定归属性。更复杂的放在后面

可以看到，循环了一万次，确实没有重复添加。

这里 HashSet 内维持了一个 map，添加元素的时候实际上是将元素存入这个 Map中。

e 作为 map的 Key

由于 HashMap key是唯一的，所以 HashSet 的元素自然不会重复，原来是这样。

早期 Java 版本中的 HashSet 产生的输出没有可辨别的顺序【也就是说是无序的】，这是出于对速度的追求，HashSet 使用了 散列算法【也就是 hash算法？】。由 HashSet 维护的 顺序与 TreeSet 或 LinkedHashSet 不同，因为它们的实现具有不同的元素存储方式。 TreeSet 将元素存储在 红-黑树数据结构中，而 HashSet 使用散列函数。LinkedHashSet 因为查询速度的原因也使用了散列，但是看起来使用了链表来维护元素的插入顺序。看起来散列算法好像已经改变了，Integer 按顺序排序，但是不能依赖此行为。

小结一下：

• HashSet 早期无序，后有序，使用散列算法为了保证速度
• TreeSet 红-黑树数据额结构
• LinkedHashSet 也使用了散列算法，看起来按数字顺序排序，但是书上说不能依赖此行为，也就是不能总是假设LinkedHashSet 是按数字顺序排序的

可以看到，HashSet保存String类型，输出的顺序并没有按照字母表来排序。

换成 TreeSet 之后果然按照字母表顺序排列好输出的了。

【那么问题来了，是不是也需要看下源码是怎样排列的呢？盲猜这里还跟红黑树的数据结构特性有关系】

下面是 Set 最常见的操作之后一是 用 contains() 测试成员的归属性，但是也有一些其他操作，这可能会让你想起小学学过的维恩图（译者：利用图形的交合表示多个集合之间的逻辑关系）

【这玩意俺们是高中学到集合才接触到的啊。。。国外小学就学这个了吗？】

下面看代码— Set的各种操作：

【这些操作确实非常简单和直观，就不多说了。】

能够产生么给元素都唯一的列表是相当有用的功能。例如，假设想要累出 SetOperations.java 文件中的所有单词，可以通 java.nio.file.Files.readAllLines() 方法打开一个文件，并将其作为一个 List<String》读取，每个 String 都是输入文件中的一行

这里我使用的是绝对路径去读取这个文件。

像这样写文件名的话是无法读取到的

同时输出也和样例不一样，因为我加了不少自己的注解。。。

这里的代码是逐步浏览文件中的每一行，并使用 String.split() 将其分解为单词。

这里使用正则表达式 【\\W +】 这意味着它会依据一个或多个(即+) 非单词字母来拆分字符串。

每个结果都添加到 words 中，因为是 TrerSet 所以会对结果进行排序。 这里排序是指按 字母顺序(lexicographically) 完成的，因此大写的和小写的字幕位于不同的组中。

如果想按 字母顺序（alphabetically) 对其进行排序，可以向 TreeSet 构造器传入 String.CASE_INSENSTIVE_ORDER 比较器（比较器是一个建立排序顺序的对象）

Comparator 比较器将在数组章节进行详细介绍。

映射 Map

将对象映射到其他对象的能力是解决编程问题的有效方法。

例如：有一个程序，被用来检查 Java 的 Random 类的随机性。理想情况下，Random 会产生完美的数字分布，但为了测试这一点，需要生成大量的随机数，并计算落在各种范围内的数字个数。

Map 可以很容易地解决这个问题。在这个例子中，Key是Random 生成的数字，而Value 则是出现的次数。

自动包装机制将随机生成的 int 转换为可以与 HashMap 一起使用的 Integer 引用。

如果 Key 不在集合中，则 get() 返回 null，否则该值进行递增。

下面的例子使用 String 描述来查找 Pet对象。还展示了通过使用 containsKey() 和 containsValue() 方法测试一个Map是否包含某个 Key 或 Value：

【例子很简单，就是给HashMap中保存了几组 String-Pet 的键值对，然后取出其中一个并调用 Api 查看取出的这个对象是否在 Map中存在的例子。】

Map与数组和其他 Collection 一样，可以轻松地扩展到多个维度，只需要创建一个 Map 的 Map （这些 Map 的值可以是其他集合，甚至是其他 Map）。因此，能够很容易地将集合组合起来以快速生成强大的数据结构。

假设你正在追踪有多个宠物的人，只需要一个 Map《Person,List《Pet》》 即可

代码挺简单的，一个是获取所有Key的集合，一个是打印所有 Value 还有就是根据 Keyset 来遍历 对应key 的value

队列 Queue

队列是一个典型的 先进先出 FIFO 集合。

即从集合的一段放入事物，再从另一端去获取它们，事物放入集合的顺序和被取出的顺序是相同的。

队列通常被当做一种可靠的讲对象从程序的某个区域传输到另一个区域的途径。队列在并发编程中尤其重要，因为它们可以安全地将对象从一个任务传输到另一个任务。

LinkedList 实现了 Queue 接口，并且提供了一些方法以支持队列行为，因此 LikedList 可以用作 Queue 的一种实现。

通过将 LinkedList 向上转换为 Queue，下面的示例使用了在 Queue 接口中 与 Queue 相关的方法：

例子很简单，就是写了一个静态方法，remove 一个 Queue中的所有元素并打印，这里的入参是 Queue，真正的实参 是 LinkedList

offer() 是与 Queue 相关的方法之一，它在允许的情况下，在队列的尾部插入一个元素，或者返回 false()。

peek() 和 element 都是返回第一个元素 且不删除。 如果队列为空 element() 抛出异常，peek 返回 null。

poll() He remove（） 都删除并返回队头元素。但如果队列为空 poll() 返回 null，remove() 抛出异常。

自动包装机制会自动将 nextInx() 的int 结果转换为 Integer 对象， 将char 转为 Chracter对象。

Queue 接口窄化了 LinkedList 方法的访问权限，因此只有 Queue 中的方法才能使用，因此能够访问到的 LinkedList 的方法会变少。

与 Queue 相关的方法提供了完整而独立的功能。也就是说，对于 Queue 所继承的 Collection，在不需要使用它的任何方法的情况下，可以拥有一个可用的 Queue。

优先级队列 PropertyQueue

先进先出描述了最典型的队列规则。队列规则是指在给定队列中的一组元素的情况下，确定下一个弹出队列的元素的规则。先进先出声明的是下一个弹出元素应该是等待时间最长的元素。

【意思就是按等待时间倒序】

优先级队列声明下一个弹出的元素是最需要的元素（优先级最高）【说明队列中可以设置不同元素的权重】。

例如，在飞机场，当飞机临近起飞时，这架班次的飞机的乘客可以在办理登机手续时排到队头。

如果构建一个消息传递系统，某些消息比其他消息更重要，应该尽快处理，而不管它们何时到达队列。

在 Java 5 中添加了 PriorityQueue ，以便自动实现这种行为。

【老规矩，看源码】

这是 Priority 的 offer() 添加元素的方法 关键就在于 siftUp() 函数

根据方法注释以及方法名就可以知道，这里面有排序的行为。

当对象被添加到 PriorityQueue 中时，该对象会在队列中被排序。

默认的排序使用队列中对象的自然顺序（natural order) ，也可以通过提供自己的 Comparator 排序器来修改这个顺序。

PriorityQueue 确保在调用 peek()，pool() 或 remove() 的时候，获得的元素将是队列中优先级最高的。

看了下，PriorityQueue 的 peek() 方法没有什么特殊的处理，只是返回队列的第0个元素，那么怎样确保返回的是优先级最高的元素呢？那么文章肯定再这个队列里。

【看注释，该队列是平衡的二进制堆。等等的，挺复杂，反正知道这个队列很不寻常就行了。】

【据我观察这里peek元素的顺序的结果是按照自然顺序排列的】

优先队列是允许重复的，最小的值具有最高的优先级（如果是String, 空格也算作值，并且比字母的优先级高。）

为了展示如果通过自己提供的比较器对象来改变顺序，第三个对优先队列构造器的调用和第二个对优先队列构造器的调用使用了由 Collection.reverseOrder() 产生的反序 Comparator。

Integer，String，和 Character 可以与 PriorityQueue 一起使用，是因为这些类已经内置了自然排序器。

如果想在 PriorityQueue中使用自己的类，则必须包含额外的功能以产生自然排序，或者必须提供自己的 Comparator。在附录中有一个更复杂的例子来演示这种情况

【所以，优先的队列使用必须是实现好排序器的类】

集合与迭代器

【之前总结的一个集合类中迭代器模式的UML类图】

Collection 是所有序列集合的顶层接口，它可能会被认为是一种 附属接口（incidental interface)，即 因为要表示其他若干个接口的共性而出现的接口。

此外 java.util.AbstractCollection 类提供了 Collection 的默认实现，使得你快要创建 AbstractCollection 的子类，而其中没有不必要的代码重复。

使用接口描述的一个理由是它可以创建更通用的代码。通过针对接口而非具体实现来编写代码。我们的代码可以应用于更多类型的对象。如果一个方法的入参是 Collection，则任何实现该接口的类都可以使用。这也就使得一个新类可以取实现 Collection 接口，以便该方法可以使用它。

标准 C++ 类库中的集合并没有共同的基类——集合之间所有的共性都是通过迭代器实现的。

在 Java中，也遵循了 C++ 的方式，即用迭代器 而不是 Collection 来表示集合之间的共性。

但是这两种方法绑定在了一起，因为实现 Collection 就意味着要提供获取迭代器的 iterator() 方法：

两个版本的 display() 都可以使用 Map 或 Collection的子类型来工作。而且 Collection 接口 和 Iterator 都将 display() 方法与低层集合的特定实现解耦。

【意思都是针对接口编程，而没有去对特殊的集合实现子类做多余的处理】

当需要实现一个不是 Collection 的外部类的时候，让它去实现 Collection 接口可能非常麻烦或困难，因此使用 Iterator 就会变得很吸引人。

例如如果我们通过继承一个持有 Pet 对象的类来创建一个 Collection的实现，那么我们必须实现 Collection 所有方法，即使我们不在 display() 中使用它们。虽然可以通过继承 AbstractCollection 很容易的实现，但是无论如何都需要强制的去实现iterator() 和 size() 方法 。这些方法 AbstractCollection 没有实现，但是 AbstractCollection 中的其他方法会用的。

【因为只有能获取迭代器 才能使用 for-in循环来遍历，而实现了 Collection 就必须能使用for-in，所以必须实现获取迭代器的方法吧。】

remove() 是一个可选操作，这里可以不必实现，如果调用，则抛出一个异常即可。

你可能认为 因为 iterator() 返回一个 Iterator《Pet》，匿名内部类可以使用菱形语法进行类型推断，但是事实上这不起作用，类型推断仍然非常有限。

这个例子表明，如果实现 Collection 就必须实现 iterator() 并且只拿实现 iterator() 与继承 AbstractCollection 相比，花费的代价只有略微减少。

但是如果已经继承了别的类，那么就不能继承 AbstractCollection 了。 在这种情况下，只能实现顶层 Collection 接口并实现所有方法，此时，继承并提供创建迭代器的能力要容易的多。

【确实非常方便，只要提供一个返回对应迭代器的接口的方法即使用对应的 display() 方法】

生成 Iterator 是将序列与消费该序列方法连接在一起耦合度最小的方式，并且与实现 Collection相比，它在序列类上所施加的约束也小的多。

【不需要实现 Collection 接口并实现其中的方法，只要提供迭代器就行，方便】

for-in 和 迭代器

目前为止，for-in 语法主要用于数组，但是它也适用于任何 Collection 对象。实际上在使用 ArrayList 时，已经看到了一些使用它的示例，下面是一个更通用的证明：

非常简单 就不多说了。 主要展示了使用 for-in 是 Collection 对象的特征。

这样做的原因是 Java 5 引入了 Iterable 接口。该接口包含了一个能够生成 iterator() 的方法。 for-in 使用此 Iterable 接口来遍历序列。

因此只要实现了 Iterable 接口的类，都可以使用for-in 来遍历。

iterator() 返回的是实现了 Iterator《String》 的匿名内部类的实例，该匿名内部类可以遍历数组中的每个单词。 main() 方法中可以看到 实现 Iterable 接口的类确实可以用于 for-in 语句。

在 Java5 中，许多类都是 Iterable 的，主要包括 所有的 Collection类（但不包括各种 Maps）。

System.getenv() 返回一个Map，entrySet() 产生一个由 Map.Entry 的元素构成的Set，并且Set 是一个 Iterable，所以可以用于 for-in 循环。

for-in 语句适用于数组或其他任何 Iterable，但是这并不意味着数组肯定也是个 Iterable，也不会发生任何自动装箱：

【这句话有点美整明白】

尝试将数组作为一个 Iterable 参数传递会导致失败。

这说明不存在任何从数组到 Iterable 的自动转换，必须手工执行这种操作

【总结：实现了 Iterable 的接口就可以使用for-in 语法， Collection 和 Iterable 都可以用 for-in 遍历，但是当自定义类无法继承 AbstractCollection 的时候，实现一个 Iterator 会方便很多】

适配器方法惯用法

需求：有一个 Iterable 类，你想要添加一种或多种在 for-in 语句中使用这个类的方法。例如 可以选择正向还是逆向遍历一个单词列表。如果直接继承并覆盖 iterator() 方法，则只能替换现有方法，而不能实现 遍历顺序的选择。

一种解决方案是 适配器方法（Adapter Method) 。适配器部分来自于设计模式，因为必须要提供特定的接口来满足 for-in 语句。

如果已经有一个接口，并且需要另一个接口时，则编写 适配器就可以解决这个问题。

在这个例子中，如果希望在默认的正向迭代器的基础上添加产生反向迭代器的能力，因此不能使用覆盖，相反，而是添加了一个能生成 Iterable 对象的方法，该对象看用于 for-in 语句。这使得我们可以提供多种 for-in语句的方式。

【说实话，这个操作我光看这段话是没想明白的，所以也是一个提升的知识点，直接敲代码吧】

【这个操作真挺牛逼，以前真没这么玩过，下面开始分析代码】

在主方法中 如果直接将 ral 对象放在 for-in 语句中，则会得到默认的正向迭代器，如果调用 reversed() 获取实现了逆向遍历的 迭代器，则会产生不同的行为。

【这里关键就在于自己实现了一个逆向的迭代器，那段实现是核心。】

下面再来个添加两种适配器的方法：

【这里添加了一个是逆向迭代器，一个是被打乱的List 的迭代器】

注意，第二个方法 random() 没有创建它自己的 iterator，而是直接返回被打乱的 List 中的 Iterator。

从输出中可以看到，Collection.shuffle() 方法不会影响到原始数组，而只是打乱了 shuffled 中的引用，之所以这样，是因为 randimize() 方法用一个 ArrayList 将 Arrays.asList() 的结果包装了起来，如果这个由 Arrays.asList() 生成的 List 被直接打乱，那么它将修改底层数组，看下面：

可以看到如果不用 ArrayList 在数组外面包一层的话，直接在 Arrays.asList 转出来的数组上调用 shuffle 的话，原数组会被打乱。

在第一种情况下 Arrays.asList() 的输出被传递给了 ArrayList 的构造器，这将穿件一个引用 ia 的元素的 ArryList，因此打乱这些引用不会修改该数组。 如果直接使用 Arrays.asList 则打乱会修改 ia数组的顺序。

重要的还是要注意 Arrays.asList() 生成一个 List对象，该对象使用底层数组作为其物理实现，如果执行的操作会修改这个List 并且不希望修改原始数组，那么就应该创建一个副本来保护原数组。

【这个点非常关键，看注释很清楚的说到对List的改写会同时改变原数组，确实有可能在这踩坑。】

这一章终于结束了，耗时两天，收获不少。

本章小结

简单集合分类

1. 数组将数字索引与对象关联，它保存类型明确的对象，因此在查找对象时不必做类型转换。数组的大小不可改变。

2. Collection保存单一元素，Map保存键值对映射。使用泛型可以指定集合中保存的对象的类型。集合的泛型不能设置为基本类型，但是会自动拆装箱。集合会自动调整大小。

3. List 也将数字与元素关联，因此数组和List 都是有序集合。

4. 访问用 ArrayList 增删用LinkedList

5. 队列和栈的行为都是由 LinkedList 提供的。【换句话说 LinkedList 包含了链表，队列，栈 三种数据结构？】

6. Map是一种将对象与对象关联的设计。HashMap 为快速访问而设计，TreeMap 保持键始终处于排序状态，LinkedHashMap 按插入顺序保存元素，使用散列提供快速访问的能力。

7. Set 不接受重复元素 HashSet 访问速度最快， TreeSet 保持元素处于拍哦徐状态 LikedHashSet 按插入顺序保存元素，使用散列算法保证快速访问能力。

8. 不要使用遗留类 Stack,Vector,HashTable.

除了 TreeSet 之外的 Set 都具有和 Collcetion 完全相同的接口。

List 和 Collection 存在着明显的不同，尽管 List 所要求的的方法都在 Collection 中。

Queue 接口中的方法是独立的，在创建具有 Queue 功能的实现时，不需要使用 Collection 方法。

Map 和 Collection之间唯一的交集是 Map 可以使用 entrySet() 和 values() 方法来产生 Collction。

标记接口 java.util.RandomAccess 附加在 ArrayList 上，但没有附加到 LinkedList 上，为根据特定List 动态改变其行为的算法提供了信息。

从面向对象的继承层次结构来看，这种组织结构确实有些奇怪。

集合类库一直以来都是设计难题，解决这些问题涉及到要去满足经常彼此之间互为牵制的各方面需求。所以要在各处充满妥协。

【完】

类图：