对象排序
原文：
docs.oracle.com/javase/tutorial/collections/interfaces/order.html
一个List l可以按以下方式排序。
Collections.sort(l);
如果List包含String元素，则将按字母顺序对其进行排序。如果包含Date元素，则将按时间顺序对其进行排序。这是如何发生的呢？String和Date都实现了Comparable接口。Comparable实现为一个类提供了*自然排序*，允许该类的对象自动排序。下表总结了一些更重要的实现Comparable`接口的 Java 平台类。
实现 Comparable 接口的类
| 类 | 自然排序 |
Byte |
有符号数值 |
Character |
无符号数值 |
Long |
有符号数值 |
Integer |
有符号数值 |
Short |
有符号数值 |
Double |
有符号数值 |
Float |
有符号数值 |
BigInteger |
有符号数值 |
BigDecimal |
有符号数值 |
Boolean |
Boolean.FALSE < Boolean.TRUE |
File |
基于路径名的系统相关字典序 |
String |
字典序 |
Date |
时间顺序 |
CollationKey |
区域特定字典序 |
如果你尝试对一个不实现Comparable接口的列表进行排序，Collections.sort(list)将抛出一个ClassCastException。同样，如果你尝试使用comparator对无法相互比较的列表进行排序，Collections.sort(list, comparator)将抛出ClassCastException。可以相互比较的元素被称为可相互比较的。尽管不同类型的元素可能是可相互比较的，但这里列出的类中没有一个允许跨类比较。
如果你只想对可比较元素的列表进行排序或创建排序的集合，那么关于Comparable接口，这就是你真正需要知道的全部内容。如果你想要实现自己的Comparable类型，那么下一节将对你感兴趣。
编写自己的可比较类型
Comparable接口包含以下方法。
public interface Comparable<T> { public int compareTo(T o); }
compareTo方法比较接收对象与指定对象，并根据接收对象是小于、等于还是大于指定对象返回负整数、0 或正整数。如果指定对象无法与接收对象比较，则该方法会抛出ClassCastException。
下面的类代表一个人的名字，实现了Comparable。examples/Name.java
import java.util.*; public class Name implements Comparable<Name> { private final String firstName, lastName; public Name(String firstName, String lastName) { if (firstName == null || lastName == null) throw new NullPointerException(); this.firstName = firstName; this.lastName = lastName; } public String firstName() { return firstName; } public String lastName() { return lastName; } public boolean equals(Object o) { if (!(o instanceof Name)) return false; Name n = (Name) o; return n.firstName.equals(firstName) && n.lastName.equals(lastName); } public int hashCode() { return 31*firstName.hashCode() + lastName.hashCode(); } public String toString() { return firstName + " " + lastName; } public int compareTo(Name n) { int lastCmp = lastName.compareTo(n.lastName); return (lastCmp != 0 ? lastCmp : firstName.compareTo(n.firstName)); } }
为了保持前面的示例简洁，该类有一定的限制：它不支持中间名，要求同时有名和姓，而且在任何方面都没有国际化。尽管如此，它阐明了以下重要点：
Name对象是不可变的。其他条件相同的情况下，不可变类型是最好的选择，特别是对于将用作Set中的元素或Map中的键的对象。如果在集合中修改它们的元素或键，这些集合将会中断。- 构造函数检查其参数是否为
null。这确保所有的Name对象都是格式良好的，以便其他方法永远不会抛出NullPointerException。 hashCode方法被重新定义。这对于重新定义equals方法的任何类都是必不可少的。（相等的对象必须具有相等的哈希码。）equals方法在指定对象为null或不合适类型时返回false。compareTo方法在这些情况下会抛出运行时异常。这两种行为都是各自方法的一般契约所要求的。toString方法已被重新定义，以便以人类可读的形式打印Name。这总是一个好主意，特别是对于将要放入集合中的对象。各种集合类型的toString方法依赖于它们的元素、键和值的toString方法。
由于本节是关于元素排序的，让我们再谈一下 Name 的 compareTo 方法。它实现了标准的名称排序算法，其中姓氏优先于名字。这正是你在自然排序中想要的。如果自然排序是不自然的，那将会非常令人困惑！
看一下 compareTo 的实现方式，因为它是相当典型的。首先，你比较对象的最重要部分（在这种情况下是姓）。通常情况下，你可以直接使用部分类型的自然排序。在这种情况下，部分是一个 String，自然（词典）排序正是所需的。如果比较结果不是零，表示相等，你就完成了：只需返回结果。如果最重要的部分相等，你继续比较下一个最重要的部分。在这种情况下，只有两个部分——名和姓。如果有更多的部分，你会按照明显的方式继续，比较部分直到找到两个不相等的部分或者你正在比较最不重要的部分，此时你会返回比较的结果。
为了展示它是如何工作的，这里是一个构建名称列表并对其进行排序的程序。
import java.util.*; public class NameSort { public static void main(String[] args) { Name nameArray[] = { new Name("John", "Smith"), new Name("Karl", "Ng"), new Name("Jeff", "Smith"), new Name("Tom", "Rich") }; List<Name> names = Arrays.asList(nameArray); Collections.sort(names); System.out.println(names); } }
如果你运行这个程序，这是它打印的内容。
[Karl Ng, Tom Rich, Jeff Smith, John Smith]
compareTo方法的行为有四个限制，我们现在不会详细讨论，因为它们相当技术性和乏味，并且最好留在 API 文档中。所有实现Comparable的类都必须遵守这些限制，因此如果您正在编写实现它的类，请阅读Comparable的文档。尝试对违反这些限制的对象列表进行排序会导致未定义的行为。从技术上讲，这些限制确保自然排序是实现它的类的对象上的全序；这是确保排序是明确定义的必要条件。
比较器
如果您想按照除自然排序之外的顺序对一些对象进行排序怎么办？或者如果您想对一些不实现Comparable接口的对象进行排序怎么办？要做到这两点，您需要提供一个Comparator — 一个封装排序的对象。与Comparable接口一样，Comparator接口由一个方法组成。
public interface Comparator<T> { int compare(T o1, T o2); }
compare方法比较其两个参数，根据第一个参数是否小于、等于或大于第二个参数返回负整数、0 或正整数。如果任一参数的类型对于Comparator不合适，则compare方法会抛出ClassCastException。
大部分关于Comparable的内容也适用于Comparator。编写compare方法几乎与编写compareTo方法相同，只是前者将两个对象作为参数传递。compare方法必须遵守与Comparable的compareTo方法相同的四个技术限制，原因是Comparator必须对其比较的对象引入一个全序。
假设您有一个名为Employee的类，如下所示。
public class Employee implements Comparable<Employee> { public Name name() { ... } public int number() { ... } public Date hireDate() { ... } ... }
假设Employee实例的自然排序是根据员工姓名（如前面的示例中定义的）的Name排序。不幸的是，老板要求按资历顺序列出员工名单。这意味着我们需要做一些工作，但不多。以下程序将生成所需的列表。
import java.util.*; public class EmpSort { static final Comparator<Employee> SENIORITY_ORDER = new Comparator<Employee>() { public int compare(Employee e1, Employee e2) { return e2.hireDate().compareTo(e1.hireDate()); } }; // Employee database static final Collection<Employee> employees = ... ; public static void main(String[] args) { List<Employee> e = new ArrayList<Employee>(employees); Collections.sort(e, SENIORITY_ORDER); System.out.println(e); } }
程序中的Comparator相当简单。它依赖于应用于hireDate访问器方法返回的值的Date的自然排序。请注意，Comparator将其第二个参数的入职日期传递给其第一个参数，而不是反过来。原因是最近入职的员工资历最低；按照入职日期排序会将列表按照逆资历顺序排列。有时人们用来实现这种效果的另一种技术是保持参数顺序，但对比较结果取反。
// Don't do this!! return -r1.hireDate().compareTo(r2.hireDate());
你应该始终使用前一种技术而不是后一种，因为后一种不能保证有效。原因是compareTo方法如果其参数小于调用它的对象，则可以返回任何负的int。有一个负的int在取反后仍然是负的，尽管这看起来很奇怪。
-Integer.MIN_VALUE == Integer.MIN_VALUE
前面程序中的Comparator用于对List进行排序很好，但它有一个缺陷：它不能用于对已排序的集合（如TreeSet）进行排序，因为它生成的排序与equals不兼容。这意味着这个Comparator将把equals方法不认为相等的对象等同起来。特别是，任何在同一天入职的两名员工将被视为相等。当你对List进行排序时，这并不重要；但当你使用Comparator对已排序的集合进行排序时，这是致命的。如果你使用这个Comparator将多名在同一天入职的员工插入TreeSet，只有第一个会被添加到集合中；第二个将被视为重复元素并被忽略。
要解决这个问题，只需微调Comparator，使其生成一个与equals兼容的排序。换句话说，调整它使得当使用compare进行比较时，只有那些在使用equals进行比较时也被视为相等的元素才被视为相等。做法是执行一个两部分比较（如对Name），其中第一部分是我们感兴趣的部分——在这种情况下是入职日期——第二部分是一个唯一标识对象的属性。在这里，员工编号是显而易见的属性。这是产生的Comparator。
static final Comparator<Employee> SENIORITY_ORDER = new Comparator<Employee>() { public int compare(Employee e1, Employee e2) { int dateCmp = e2.hireDate().compareTo(e1.hireDate()); if (dateCmp != 0) return dateCmp; return (e1.number() < e2.number() ? -1 : (e1.number() == e2.number() ? 0 : 1)); } };
最后一点：你可能会想要用更简单的方式替换Comparator中的最后一个return语句：
return e1.number() - e2.number();
不要这样做，除非你绝对确定没有人会有负的员工编号！这个技巧通常不起作用，因为有符号整数类型不足以表示任意两个有符号整数的差值。如果i是一个很大的正整数，而j是一个很大的负整数，i - j会溢出并返回一个负整数。所得到的comparator违反了我们一直谈论的四个技术限制之一（传递性），并产生可怕的、微妙的错误。这不仅仅是理论上的担忧；人们会因此受到伤害。
SortedSet 接口
原文：
docs.oracle.com/javase/tutorial/collections/interfaces/sorted-set.html
SortedSet 是一个按升序维护其元素的集合，根据元素的自然顺序或在 SortedSet 创建时提供的 Comparator 进行排序。除了正常的 Set 操作外，SortedSet 接口还提供以下操作：
Range view— 允许对排序集合进行任意范围操作Endpoints— 返回排序集合中的第一个或最后一个元素Comparator access— 返回用于对集合进行排序的Comparator（如果有的话）
SortedSet 接口的代码如下。
public interface SortedSet<E> extends Set<E> { // Range-view SortedSet<E> subSet(E fromElement, E toElement); SortedSet<E> headSet(E toElement); SortedSet<E> tailSet(E fromElement); // Endpoints E first(); E last(); // Comparator access Comparator<? super E> comparator(); }
集合操作
SortedSet 从 Set 继承的操作在排序集合和普通集合上的行为完全相同，但有两个例外：
iterator操作返回的Iterator按顺序遍历排序集合。toArray返回的数组按顺序包含了排序后的集合元素。
尽管接口不保证，但 Java 平台的 SortedSet 实现的 toString 方法返回一个包含排序集合所有元素的字符串，按顺序排列。
标准构造函数
按照惯例，所有通用的 Collection 实现都提供一个标准的转换构造函数，接受一个 Collection；SortedSet 实现也不例外。在 TreeSet 中，这个构造函数创建一个根据元素的自然顺序排序的实例。这可能是一个错误。最好动态检查指定的集合是否是 SortedSet 实例，如果是，则根据相同的标准（比较器或自然顺序）对新的 TreeSet 进行排序。因为 TreeSet 采取了它的方法，它还提供一个接受 SortedSet 的构造函数，并返回一个包含相同元素并根据相同标准排序的新 TreeSet。请注意，参数的编译时类型，而不是运行时类型，决定调用这两个构造函数中的哪一个（以及是否保留排序标准）。
SortedSet 实现通常还提供一个构造函数，接受一个 Comparator 并返回一个根据指定 Comparator 排序的空集合。如果传递 null 给这个构造函数，它将返回一个根据元素的自然顺序排序的集合。
范围视图操作
range-view操作在某种程度上类似于List接口提供的操作，但有一个重大区别。排序集的范围视图即使在直接修改支持的排序集的情况下仍然有效。这是因为排序集的范围视图的端点是元素空间中的绝对点，而不是备份集合中的特定元素，这对于列表是成立的。排序集的range-view实际上只是窗口，显示在元素空间的指定部分中集合的任何部分。对排序集的range-view的更改会写回到支持的排序集中，反之亦然。因此，长时间使用排序集上的range-view是可以的，不像列表上的range-view那样。
排序集提供三种range-view操作。第一种是subSet，类似于subList，需要两个端点。端点不是索引，而是对象，并且必须与排序集中的元素可比，使用Set的Comparator或其元素的自然排序，取决于Set用于对自身排序的方式。与subList类似，范围是半开的，包括其低端点但不包括高端点。
因此，下面这行代码告诉你在名为dictionary的字符串SortedSet中包含多少个介于"doorbell"和"pickle"之间的单词，包括"doorbell"但不包括"pickle"。
int count = dictionary.subSet("doorbell", "pickle").size();
以类似的方式，以下一行代码可以删除所有以字母f开头的元素。
dictionary.subSet("f", "g").clear();
类似的技巧可以用来打印一个表格，告诉你每个字母开头的单词有多少个。
for (char ch = 'a'; ch <= 'z'; ) { String from = String.valueOf(ch++); String to = String.valueOf(ch); System.out.println(from + ": " + dictionary.subSet(from, to).size()); }
假设你想查看一个闭区间，其中包含两个端点，而不是一个开区间。如果元素类型允许计算元素空间中给定值的后继，只需请求从lowEndpoint到successor(highEndpoint)的subSet。虽然这并不是完全明显的，但在String的自然排序中，字符串s的后继是s + "\0"，也就是在s后附加一个null字符。
因此，以下一行代码告诉你在字典中包含多少个介于"doorbell"和"pickle"之间的单词，包括doorbell 和 pickle。
count = dictionary.subSet("doorbell", "pickle\0").size();
类似的技巧可以用来查看一个开区间，其中不包含任何端点。从lowEndpoint到highEndpoint的开区间视图是从successor(lowEndpoint)到highEndpoint的半开区间。使用以下代码计算介于"doorbell"和"pickle"之间的单词数量，不包括两者。
count = dictionary.subSet("doorbell\0", "pickle").size();
SortedSet 接口包含两个更多的 range-view 操作 — headSet 和 tailSet，两者都接受一个 Object 参数。前者返回一个视图，显示了支持 SortedSet 的初始部分，直到但不包括指定的对象。后者返回一个视图，显示了支持 SortedSet 的最终部分，从指定的对象开始，一直到支持 SortedSet 的末尾。因此，以下代码允许您将字典视为两个不相交的 卷（a-m 和 n-z）。
SortedSet<String> volume1 = dictionary.headSet("n"); SortedSet<String> volume2 = dictionary.tailSet("n");
端点操作
SortedSet 接口包含返回排序集合中第一个和最后一个元素的操作，分别称为 first 和 last。除了它们的明显用途外，last 还允许解决 SortedSet 接口中的一个缺陷。您希望对 SortedSet 进行的一件事是进入 Set 的内部并向前或向后迭代。从内部向前迭代很容易：只需获取一个 tailSet 并对其进行迭代。不幸的是，向后迭代没有简单的方法。
以下习语获取了元素空间中小于指定对象 o 的第一个元素。
Object predecessor = ss.headSet(o).last();
这是从排序集合内部的某一点向后移动一个元素的好方法。可以重复应用它来向后迭代，但这非常低效，每返回一个元素都需要查找。
比较器访问器
SortedSet 接口包含一个名为 comparator 的访问器方法，返回用于对集合进行排序的 Comparator，如果集合根据其元素的 自然顺序 进行排序，则返回 null。提供此方法是为了可以将排序集合复制到具有相同顺序的新排序集合中。它被描述为 SortedSet 构造函数使用的 先前。
排序地图接口
原文：
docs.oracle.com/javase/tutorial/collections/interfaces/sorted-map.html
一个SortedMap是一个维护其条目按升序排列的Map，根据键的自然顺序排序，或者根据在创建SortedMap时提供的Comparator排序。自然排序和Comparator在对象排序部分讨论。SortedMap接口提供了常规Map操作以及以下操作：
Range view— 在排序地图上执行任意范围操作Endpoints— 返回排序地图中的第一个或最后一个键Comparator access— 返回用于对地图进行排序的Comparator（如果有的话）。
以下接口是SortedSet的Map模拟。
public interface SortedMap<K, V> extends Map<K, V>{ Comparator<? super K> comparator(); SortedMap<K, V> subMap(K fromKey, K toKey); SortedMap<K, V> headMap(K toKey); SortedMap<K, V> tailMap(K fromKey); K firstKey(); K lastKey(); }
地图操作
SortedMap从Map继承的操作在排序地图和普通地图上的行为相同，有两个例外：
- 任何排序地图的
Collection视图上的iterator操作返回的Iterator按顺序遍历集合。 Collection视图的toArray操作返回的数组按顺序包含键、值或条目。
虽然接口不能保证，但 Java 平台所有SortedMap实现中Collection视图的toString方法返回一个字符串，其中包含视图中的所有元素，按顺序排列。
标准构造函数
按照惯例，所有通用Map实现都提供一个标准转换构造函数，接受一个Map；SortedMap实现也不例外。在TreeMap中，这个构造函数创建一个根据其键的自然顺序排序其条目的实例。这可能是一个错误。最好动态检查指定的Map实例是否是SortedMap，如果是，则根据相同的标准（比较器或自然顺序）对新地图进行排序。因为TreeMap采取了它的方法，它还提供了一个接受SortedMap的构造函数，并返回一个包含与给定SortedMap相同映射的新TreeMap，根据相同标准排序。请注意，参数的编译时类型，而不是运行时类型，决定了是否优先调用SortedMap构造函数而不是普通的map构造函数。
按照惯例，SortedMap实现还提供一个接受Comparator的构造函数，并返回根据指定Comparator排序的空地图。如果将null传递给此构造函数，则返回一个根据其键的自然顺序对其映射进行排序的Map。
与 SortedSet 的比较
因为这个接口是SortedSet的精确Map模拟，所以在 SortedSet 接口部分中的所有习语和代码示例都适用于SortedMap，只需进行微不足道的修改。
接口总结
原文：
docs.oracle.com/javase/tutorial/collections/interfaces/summary.html
核心集合接口是 Java 集合框架的基础。
Java 集合框架层次结构由两个不同的接口树组成：
- 第一个树以
Collection接口开始，该接口提供了所有集合使用的基本功能，如add和remove方法。它的子接口——Set、List和Queue——提供了更专门化的集合。 Set接口不允许重复元素。这对于存储诸如一副牌或学生记录之类的集合非常有用。Set接口有一个子接口，SortedSet，用于对集合中的元素进行排序。List接口提供了一个有序的集合，用于需要精确控制每个元素插入位置的情况。您可以通过它们的确切位置从List中检索元素。Queue接口允许额外的插入、提取和检查操作。Queue中的元素通常按照 FIFO 顺序排序。Deque接口允许在两端进行插入、删除和检查操作。Deque中的元素可以同时用于 LIFO 和 FIFO。- 第二个树以
Map接口开始，类似于Hashtable将键和值进行映射。 Map的子接口SortedMap将其键值对按升序或按Comparator指定的顺序维护。
这些接口允许集合在不考虑其表示细节的情况下进行操作。
问题和练习：接口
原文：
docs.oracle.com/javase/tutorial/collections/interfaces/QandE/questions.html
问题
- 在本课程的开始，您了解到核心集合接口被组织成两个不同的继承树。特别是一个接口被认为不是真正的
Collection，因此位于自己的树的顶部。这个接口的名称是什么？ - 集合框架中的每个接口都使用
语法声明，告诉您它是泛型的。当您声明一个Collection实例时，指定它将包含的对象类型有什么优势？ - 什么接口代表不允许重复元素的集合？
- 什么接口形成了集合层次结构的根？
- 什么接口代表可能包含重复元素的有序集合？
- 什么接口代表在处理之前保存元素的集合？
- 什么接口代表将键映射到值的类型？
- 什么接口代表双端队列？
- 列出遍历
List元素的三种不同方法。 - 真或假：聚合操作是修改基础集合的变异操作。
练习
- 编写一个以随机顺序打印其参数的程序。不要复制参数数组。演示如何使用流和传统的增强 for 语句打印元素。
- 取
FindDups示例，并修改它以使用SortedSet而不是Set。指定一个Comparator，以便在排序和识别集合元素时忽略大小写。 - 编写一个方法，接受一个
List并对每个元素应用String.trim。 - 考虑四个核心接口，
Set、List、Queue和Map。对于以下四个任务中的每一个，指定哪个核心接口最适合，并解释如何使用它来实现任务。
- Whimsical Toys Inc（WTI）需要记录所有员工的姓名。每个月，将从这些记录中随机选择一个员工以获得免费玩具。
- WTI 已决定每个新产品都将以员工的名字命名，但只使用名字的第一个字母，并且每个名字只能使用一次。准备一个独特的名字列表。
- WTI 决定只想使用最受欢迎的名字来命名其玩具。统计每个名字的员工数量。
- WTI 为当地的长曲棍球队购买季票，将由员工共享。为这项受欢迎的运动创建一个等待名单。
检查你的答案。
课程：聚合操作
原文：
docs.oracle.com/javase/tutorial/collections/streams/index.html
注意：要更好地理解本节中的概念，请查看 Lambda 表达式和方法引用部分。
您使用集合做什么？您不仅仅将对象存储在集合中并将其留在那里。在大多数情况下，您使用集合来检索其中存储的项目。
再次考虑 Lambda 表达式部分中描述的场景。假设您正在创建一个社交网络应用。您希望创建一个功能，使管理员能够对满足某些条件的社交网络应用成员执行任何操作，例如发送消息。
与之前一样，假设这个社交网络应用的成员由以下Person类表示：
public class Person { public enum Sex { MALE, FEMALE } String name; LocalDate birthday; Sex gender; String emailAddress; // ... public int getAge() { // ... } public String getName() { // ... } }
Java 中文官方教程 2022 版（二十七）（2）https://developer.aliyun.com/article/1486849
