Ryuu 的个人博客

刚接触事件的人可能觉得触发事件是很容易的，只需将事件定义好，并在需要触发时调用相关的事件处理程序就可以了，底层的多播委托将会依次执行这些处理程序。实际上触发事件并不是如此简单。若根本没有事件对应的处理程序会怎样？若多个线程都要检测并调用事件处理程序，而线程之间互相争夺，会怎样？C# 6.0 引入的 null 条件运算符 (null-conditional operator，又称 null 传播运算符 (null-propagation operator)) 可用更加清晰的写法来解决这些问题。

1
2
3
4
5
6
7
8
9
10
11

public class EventSource
{
    private int counter;
    private EventHandler<int> Updated;

    public void RaiseUpdates()
    {
        counter++;
        Updated(this, counter);
    }
}

这种旧写法有个明显的问题：如在对象上出发 Updated 事件是并没有事件处理程序与之相关，将会发生 NullReferenceException，因为 C# 用 null 值表示这种没有处理程序与之相关的情况。于是，触发事件前，必须先判断事件处理程序是否为 null。

1
2
3
4
5
6

public void RaiseUpdates()
{
    counter++;
    if(Updated != null)
        Updated(this, counter);
}

但这种写法依然有 bug。当程序线程执行完 if 判断了 Updated 不为 null 后，可能会有另一个线程打断该线程，并解除订阅，这样的话依然会引发 NullReferenceException，虽然这种情况很少见。

这个 bug 很难诊断，也很难修复。想重现该错误，必须按照上述线程的执行顺序执行。一些开发老手在此问题上吃过亏，他们知道其危险，改用另一个种写法：

1
2
3
4
5
6
7

public void RaiseUpdates()
{
    counter++;
    var handler = Updated;
    if(handler != null)
        handler(this, counter);
}

此方法是可行的，线程是安全的。但是从阅读的角度来看，看代码的人不太明白为何这样改后就能确保线程安全。

var handler = Updated; 这是对赋值号的右侧做 *浅拷贝 (shallow copy)*，也就是创建一个新的引用，指向其事件处理程序。因此，即使是 Updated 被其他线程注销，变为 null。也不会影响 handler，handler 依然保存了原先记录的事件订阅者。这段代码实际上是通过浅拷贝为事件订阅这做了份快照，触发事件时通过快照来触发事件处理程序。

触发事件是一项简单的任务，不该用这么冗长且费解的方式去完成。

有了 null 条件运算符，可以用更清晰的写法来实现：

1
2
3
4
5

public void RaiseUpdates()
{
    counter++;
    Updated?.Invoke(this, counter);
}

采用了 null 条件运算符 (也就是 ?.) 安全地调用事件处理程序。该运算符首先对左侧内容进行 null 判断，若非 null 执行右侧内容。若为 null 则跳过此语句。

从语义上来说这和 if 类似。但区别在于 ?. 运算符左侧的内容只会计算一次。

由于 C# 不许 ?. 运算符右侧直接出现一对括号，因此必须用 Invoke() 去触发事件。每定义一种委托或事件，编译器都会为此生成类型安全的 Invoke()，这意味着，通过 Invoke 方法触发事件，使得代码篇幅更小，且线程安全。

有了这种简单且清晰的写法后，原来的写法需要改一改了。以后触发事件都应采用此写法。

成员访问运算符和表达式 - C# 参考

Java 用起来如此舒适的一个因素在于，它是一门安全的语言 (safe language)。这意味着，它对于缓冲区溢出、数组越界、非法指针以及其他的内存破坏错误都自动免疫，而这些错误却困扰着诸如 C 和 C++ 这样的不安全语言。在一门安全语言中，在设计类时，无论系统的其他部分发生什么问题，类的约束都可以保持为真。对于那些 “把所有内存当作一个巨大的数组来对待” 的语言来说，这是不可能的。

即使在安全的语言中，如果不采取一点措施，还是无法与其它的类隔离开来。建设类的客户端会尽其所能来破坏这个类的约束条件，因此你必须保护性地设计程序。实际上，只有当有人试图破坏系统的安全性时，才可能发生这种情况；更有可能的是，对你的 API 产生误解的程序员，所导致的各种不可预期的行为，只好由类来处理。无论是何种情况，编写面对客户端的不良行为仍保持健壮性的类，这是非常值得投入时间去做的事情。

如果没有对象的帮助，另一个类不可能修改对象的内部状态，但是对象很容易在无意识的情况下提供帮助。例如 下面的类表示一段不可变的时间周期：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

// Broken "immutable" time period class
public class Period {
    private final Date start;
    private final Date end;

    public Period(Date start, Date end) {
        if (start.compareTo(end) > 0)
            throw new IllegalArgumentException(start + " after " + end);
        this.start = start;
        this.end = end;
    }

    public Date start() {
        return start;
    }

    public Date end() {
        return end;
    }
}

乍看之下，此类似乎是不可变的，并且加了周期的起始时间 (start) 不能在结束时间 (end) 之后。然而，因为 Date 类本身是可变的，因此很容易违反这个约束条件：

1
2
3
4
5

// Attack the internals of a Period instance
Date start = new Date();
Date end = new Date();
Period p = new Period(start, end);
end.setYear(78); // Modifies internals of p!

从 Java 8 开始，修正这个问题最明显的方式是使用 Instant (或 LocalDateTime，或者 ZonedDateTime) 代替 Date，因为 Instant (以及另一个 java.time 类) 是不可变类 (见17条)。Date 已经过时了，不应该在新代码中使用。

为了保护 Period 实例的内部信息，避免受到此攻击，对于构造器的每个可变参数进行保护性拷贝 (defensive copy) 是必要的，并且使用备份对象作为 Period 实例的组件，而不使用原始的对象：

1
2
3
4
5
6
7

// Repaired constructor - makes defensive copies of parameters
public Period(Date start, Date end) {
    this.start = new Date(start.getTime());
    this.end = new Date(end.getTime());
    if (this.start.compareTo(this.end) > 0)
        throw new IllegalArgumentException(this.start + " after " + this.end);
}

用了新的构造器之后，上述的攻击对于 Period 实例不再有效。注意，保护性拷贝是在检查参数的有效性 (见第38条) 之前进行的，并且有效性检查是针对拷贝之后的对象，而不是针对原始的对象。虽然这样做看起来有点不太自然，却是必要的。这样做可以避免在 “危险阶段” 期间从另一个线程改变类的参数，这里的危险阶段是指从检査参数开始，直到拷贝参数之间的时间段。在计算机安全社区中，这被称作Time-Of-Check / Time-Of-Use 或者 TOCTOU 攻击 [ViegaO1]。

同时也请注意，没有用 Date 的 clone 方法来进行保护性拷贝。因为 Date 是非 final 的， 不能保证 clone 方法一定返回类为 java.util.Date 的对象：有可能返回专门出于恶意的目的而设计的不可信子类实例。例如，子类可以在每个实例被创建的时候，把指向该实例的引用记录到一个私有的静态列表中，并且允许攻击者访问这个列表。这将使得攻击者可以 自由地控制所有的实例。为了阻止这种攻击，对于参数类型可以被不可信任方子类化的参数，不使用 clone 方法进行保护性拷贝。

虽然替换构造器就可以成功地避免上述的攻击，但是改变 Period 实例仍然是有可能的，因为它的访问方法提供了对其可变内部成员的访问能力：**(Ryuu：原始方法返回的是其成员的视图，这样会导致 Period 可被修改)**

1
2
3
4
5
6
7
8

// Repaired accessors - make defensive copies of internal fields
public Date start() {
    return new Date(start.getTime());
}

public Date end() {
    return new Date(end.getTime());
}

采用了新的构造器和新的访问方法之后，Period 真正是不可变的了。不管程序员是多么恶意，或者多么不合格，都绝对不会违反 “周期的起始时间不能落后于结束时间” 的约束条件。因为除了 Period 类自身之外，其他任何类都无法访问 Period实例中的任何一个可变域。这些域被真正封装在对象的内部。

访问方法与构造器不同，它们在进行保护性拷贝的时候允许使用 clone 方法。之所以如此， 是因为我们知道，Period 内部的 Date 对象的类是 java.util.Date，而不可能是其他某个潜在的不可信子类。也就是说，基于第11条中所阐述的原因，一般情况下，最好使用构造器或者静态工厂。

参数的保护性拷贝并不仅仅针对不可变类。每当编写方法或者构造器时，如果它要允许客户提供的对象进入到内部数据结构中，则有必要考虑，客户提供的对象是否有可能是可变的。如果是，就考虑你的类是否能够容忍对象进入数据结构之后发生变化。如果答案是否定的，就必须对该对象进行保护性拷贝，并且让拷贝之后的对象，而不是原始对象进入到数据结构中。例如，如果你正在考虑使用由客户提供的对象引用作为内部 Set 实例的元素，或者 作为内部Map实例的键 (key)，就应该意识到，如果这个对象在插入之后再被修改，Set 或者 Map 的约束条件就会遭到破坏。

在内部组件被返回给客户端之前，对它们进行保护性拷贝也是同样的道理。不管类是否为不可变的，在把一个指向内部可变组件的引用返回给客户端之前，也应该加倍认真地考虑。 解决方案是，应该返回保护性拷贝。记住长度非零的数组总是可变的。因此，在把内部数组返回给客户端之前，应该总要进行保护性拷贝。另一种解决方案是，给客户端返回该数组的不可变视图（immutableview)。这两种方法在第13条中都已经演示过了。

可以肯定地说，只要有可能，都应该使用不可变的对象作为对象内部的组件，这样就不必再为保护性拷贝（见第15条）操心。在前面的 Period 例子中，有经验的程序员通常使用 Date.getTime() 返回的 long 基本类型作为内部的时间表示法， 而不是使用 Date 对象引用。他们之所以这样做，主要因为 Date 是可变的。

保护性拷贝可能会带来相关的性能损失，这种说法并不总是正确的。如果类信任它的调用者不会修改内部的组件，可能因为类及其客户端都是同一个包的双方，那么不进行保护性拷贝也是可以的。在这种情况下，类的文档中就必须淸楚地说明，调用者绝不能修改可受影响的参数或者返回值。

即使跨越包的作用范围，也并不总是适合在将可变参数整合到对象中之前，对它进行保护性拷贝。有一些方法和构造器的调用，要求参数所引用的对象必须有个显式的交接过程。当客户端调用这样的方法时，它承诺以后不再直接修改该对象。如果方法或者构造器 期望接管一个由客户端提供的可变对象，它就必须在文档中明确地指明这一点。

如果类所包含的方法或者构造器的调用需要移交对象的控制权，这个类就无法让自身抵御恶意的客户端。只有当类和它的客户端之间有着互相的信任，或者破坏类的约束条件不会伤害到除了客户端之外的其他对象时，这种类才是可以接受的。后一种情形的例子是包装类模式 (wrapper class pattern) (见第18条)。根据包装类的本质特征，客户端只需在对象被包装 之后直接访问它，就可以破坏包装类的约束条件，但是，这么做往往只会伤害到客户端自己。

总结：如果类具有从客户端得到或者返回到客户端的可变组件，类就必须保护性地拷贝这些组件。如果拷贝的成本受到限制，并且类信任它的客户端不会不恰当地修改组件，就可以在文档中指明客户端的职责是不得修改受到影响的组件，以此来代替保护性拷贝。

自从有了编程这门职业，开发者需要把计算机中板寸的信息转换成更便于人阅读的格式。C# 语言中的相关 API 可以追溯到几十年前诞生的 C 语言，但是这些旧习惯应该改变，C# 6.0 提供了内插字符串 (Interpolated String) 这项新功能可以更好的用来设置字符串格式。

与旧习惯相比，这项功能有很多好处。开发者可用他们写出可读性更高的代码，编译器也可以用它实现更为完备的静态类型检查机制，降低程序出错概率。此外，它还可以提供更加丰富的语法，令你可以用更为合适的表达式来生成自己想要的字符串的格式。

String.Format() 虽然可使用，但是会导致一些问题。

1. 开发者必须对生成的字符串进行测试及验证。所有的替换操作都是根据格式字符串中的序号来完成的，而编译器不会验证格式字符串后的参数个数与有待替换的序号数是否相等。如果两者不相等，那么程序在运行时将抛出异常。
2. 格式字符串中的序号与 params 数组中的位置必须对应。而阅读代码的人不太容易看出数组中的字符串是不是按照正确顺序排列。必须允许代码，并检查生成的字符串，才能确认这一点。

不妨用 C# 提供的新特性简化代码编写工作，这项新特性就是内插字符串，这种语法糖 (syntactic sugar)，的功能是极其强大的。

内插字符串以 $ 开头，不像传统的格式字符串把序号放在一对花括号，并用其指代的 params 数组中的对应元素，而是直接在花括号中编写 C# 表达式。

1. 开发者能直接在字符串中看到待替换的内容，代码可读性高。
2. 表达式在字符串内，每一个有待替换的部分都能与替换部分的表达式对应。

花括号中的内容叫作表达式而不是泛称为语句，其不能使用 if / else 或 while 等控制流语句来做替换。若需要控制流语句做替换，那么必须把这些逻辑写成方法，在内插字符串里嵌入该方法的调用结果。

字符串内插机制是通过库代码完成的，那些代码与当前的 string.Format() 类似 (至于如何实现国际化，见第五条)。内插字符串会在必要的时候把变量从其他类型转换为 string 类型：

1

Console.WriteLine($"The value of pi is {Math.PI}");

由字符串内插操作生成的代码会调用一个参数为 params 对象数组的格式化方法。 Math.PI 是 double 类型，而 double 类型是值类型，因此，必须将其自动转换为 Object 才行。此转换需装箱，**若此代码运行很频繁，或需要在短小的循环中反复执行，那么会严重影响性能 (见第9条)**。该情况下，开发者应自己去做字符串转换，这样就不需要给表达式中的数值装箱了：

1

Console.WriteLine($"The value of pi is {Math.PI.ToString()}");

如果 ToString() 直接返回的文本不符合你的要求，那么可以修改其他参数，创造你想要的文本：

1

Console.WriteLine($"The value of pi is {Math.PI.ToString("F2")}")

可使用标准格式说明符 (C# 语言内建说明符) 来调整字符串格式。我们有可能需要对字符串做一些处理，或是把表达式返回的对象格式化，只需要在大括号中的表达式后面加上冒号，并将格式说明符写在右侧。

1

Console.WriteLine($"The value of pi is {Math.PI:F2}");

由于条件表达式也使用冒号，因此，如果在内插字符串中用冒号，那么 C# 可能会把他理解成格式说明符的前导符，而不将其视为条件表达式的一部分，这行代码是无法编译的：

1

Console.WriteLine($"The value of pi is {round ? Math.PI.ToString(): Math.PI.ToString("F2")}");

可以用小括号将整个内容括起，编译器就不会再把冒号是为格式字符串的前导符了。

1

Console.WriteLine($"The value of pi is {(round ? Math.PI.ToString() : Math.PI.ToString("F2"))}");

可以通过 null 合并运算符 (null-coalescing operator) 与 null 条件运算符 (null-conditional operator，也称为 null-propagation operator (null 传播运算符)) 更清晰的处理那些可能缺失的值：

1

Console.WriteLine($"The customer's name is {c?.name ?? "Name is missing"}");

通过示例可以看出，花括号中还可以嵌入字符串，凡是位于 { 和 } 之间的字符，就都会被当作此表达式中的 C# 代码，并加以解析 (冒号除外，他是用来表示右侧的内容是格式说明符)。

内插字符串可以嵌套。合理利用此方法，可以极大的简化编程工作量。

1
2
3
4
5

Console.WriteLine(
    $@"Record is {(
        records.TryGetValue(index, out string result) ? result : $"No record found at index {index}"
    )}"
);

如果查找的记录不存在，那么就会执行条件表达式的 false 部分，从而令嵌套的内插字符串生效，该字符串会返回一条消息，指出要查找位置的记录不存在。

可以使用 LINQ 查询操作来创建内容,其本身也支持利用内插字符串调整查询结果格式：

1
2
3
4
5
6
7
8
9

var output = $@"The First five items are: {
    src.Take(
        5
    ).Select(
        n => $@"Item: {n.ToString()}"
    ).Aggregate(
        (c, a) => $@"{Environment.NewLine}{a}"
    )
}";

上面的这种写法可能不太会出现在正式的产品代码中，但可以看出，内插字符串和 C# 之间结合的相当密切。ASP.NET MVC 框架中的 Razor View 引擎也支持内插字符串，使得开发者在编写 Web 应用程序时能够更便捷地以 HTML 的形式来输出信息。默认的 MVC 应用程序本身就演示了怎样在 Razor View 中使用内插字符串，以下示例节选自 controller 部分，它可以显示当前登入的用户名：

1

<a asp-controller="Message" asp-action="Index" title="Manage"> Hello@User.GetUserName()!</a>

构建应用程序中的其他 HTML 页面时，也可以采用这个技巧，更为精确地表达你想输出的内容。

上述实例展示了内插字符串的强大功能，虽然这些功能可用传统格式化字符串实现，但是比较麻烦。值得注意的地方在于，内插字符串本身也会解析称为一条普通的字符串 (将其中的填充部分解析填充后，其与普通字符串无差别)。使用内插字符串创建 SQL 命令是极其危险的：内插字符串不会创建参数化的 SQL 查询 (parameterized SQL query)，只会形成一个普通的 string 对象，参数已经全部被写入至该 string 中了。不只是 SQL 命令，凡是需要留到运行时去解析的信息都有此风险，开发者需要特别小心。

在每个覆盖了 equals 方法的类中，都必须覆盖 hashCode 方法。如果不这样做，就会违反 hashCode 的通用约定，从而导致该类无法结合所有基于散列的集合一起正常运作，这类集合包括 HashMap 和 HashSet。下面是约定的内容，摘自 Object 规范：

• 在应用程序的执行期间，只要对象的 equals 方法的比较操作所用到的信息没有被修改，那么对同一个对象的多次调用，hashCode 方法都必须始终返回同一个值。在一个应用程序与另一个程序的执行过程中，执行 hashCode 方法所返回的值可以不一致。
• 如果两个对象根据 equals(Object) 方法比较相等，调用这两个对象中的 hashCode 方法都必须产生同样的整数结果。
• 如果两个对象根据 equals(Object) 方法比较不相等，调用这两个对象中的 hashCode 方法，则不一定要求 hashCode 方法必须产生不同的结果 (哈希碰撞)。但是程序员应该知道，给不相等的对象产生截然不同的整数结果，有可能提高散列表（hash table）的性能。

因没有覆盖 hashCode 而违反的关键约定是第二条：相等的对象必须具有相等的散列码 (hash code)。根据类的 equals 方法，两个截然不同的实例在逻辑上有可能是相等的，但是根据 Object 类的 hashCode 方法，它们仅仅是两个没有任何共同之处的对象。因此，对象的 hashCode 方法返回两个看起来是随机的整数，而不是根据第二个约定所要求的那样，返回两个相等的整数。

假设在 HashMap 中用第10条中出现过的 PhoneNumber 类的实例作为键：

1
2

HashMap<PhoneNumber, String> m = new HashMap<>();
m.put(new PhoneNumber(707, 867, 5309), "Jenny");

你可能期望 m.get(new PhoneNumber(707, 867, 5309)) 会返回 “Jenny”，但它实际上返回的是 null。注意，这里涉及两个 PhoneNumber 实例：第一个被插入 HashMap 中，第二个实例与第一个相等，用于从 Map 中根据 PhoneNumber 去获取用户名字。由于 PhoneNumber 类没有覆盖 hashCode 方法，从而导致两个相等的实例具有不相等的散列码，违反了 hashCode 的约定。因此，put 方法把电话号码对象存放在一个散列桶 (hash bucket)中，get 方法却在另一个散列桶中查找这个电话号码。即使这两个实例正好被放到同一个散列桶中，get 方法也必定会返回 null，因为 HashMap 有一项优化，可以将与每个项相关联的散列码缓存起来，如果散列码不匹配，也就不再去检验对象的等同性。

修正这个问题非常简单，只需为PhoneNumber类提供一个适当的 hashCode 方法即可。那么，hashCode 方法应该是什么样的呢？编写一个合法但并不好用的 hashCode 方法没有任何价值。例如，下面这个方法总是合法的，但是它永远都不应该被正式使用：

1
2
3
4
5

// The worst possible legal hashCode implementation -never use!
@Override
public int hashCode() {
    return 42;
}

上面这个 hashCode 方法是合法的，因为它确保了相等的对象总是具有同样的散列码。但它也极为恶劣，因为它使得每个对象都具有同样的散列码。因此，每个对象都被映射到同一个散列桶中，使散列表退化为链表 (linked list)。它使得本该线性时间运行的程序变成了以平方级时间在运行。对于规模很大的散列表而言，这会关系到散列表能否正常工作。

一个好的散列函数通常倾向于 “为不相等的对象产生不相等的散列码”。这正是hashCode约定中第三条的含义。理想情况下，散列函数应该把集合中不相等的实例均匀地分布到所有可能的int值上。要想完全达到这种理想的情形是非常困难的。幸运的是，相对接近这种理想情形则并不太困难。下面给出一种简单的解决办法：

1. 声明一个 int 变量并命名为 result，将它初始化为对象中第一个关键域的散列码 c，如步骤 2.1 中计算所示 (如第10条所述，关键域是指影响 equals 比较的域)。

2. 对象中剩下的每一个关键域 f 都完成以下步骤：

   1. 为该域计算 int 类型的散列码 c :

      1. 若该域是基本类型，则计算 Type.hashCode(f)。这里的 Type 是装箱基本类型的类，与 f 的类型相对应。

      2. 若该域是一个对象引用，并且该类的 equals 方法通过递归地调用 equals 的方式来比较这个域，则同样为这个域递归地调用 hashCode。

         若需要更复杂的比较，则为这个域计算一个 “范式” (canonical representation)，然后针对这个范式调用 hashCode。

         若这个域的值为 null，则返回 0 (或者其他某个常数，但通常是0)。

      3. 如果该域是一个数组，则要把每一个元素当作单独的域来处理。

      递归地应用上述规则，对每个重要的元素计算一个散列码，然后根据步骤 2.2 中的做法把这些散列值组合起来。

      若数组域中没有重要的元素，可以使用一个常量，但最好不要用 0。

      若数组域中的所有元素都很重要，可以使用 Arrays.hashCode 方法。

   2. 按照下面的公式，把步骤 2.1 中计算得到的散列码 c 合并到 result 中：

      1	result = 31 * result + c;

3. 返回 result 。

   (Ryuu：附上 java 源码的实现，你会发现这就是作者提供的解决方案。这并不奇怪，本书作者 Joshua Bloch，曾任职 Sun 公司 进行 Java 的开发)

   1 2 3 4

   // java.util.Objects public static int hash(Object... values) { return Arrays.hashCode(values); }

   1 2 3 4 5 6 7 8 9 10 11 12

   // java.util.Arrays public static int hashCode(Object a[]) { if (a == null) return 0; int result = 1; for (Object element : a) result = 31 * result + (element == null ? 0 : element.hashCode()); return result; }

   写完了 hashCode 方法之后，问问自己相等的实例是否都具有相等的散列码。要编写单元测试来验证你的推断 (除非利用 AutoValue 生成 equals 和 hashCode 方法，这样你就可以放心地省略这些测试)。如果相等的实例有着不相等的散列码，则要找出原因，并修正错误。

覆盖 equals 方法看起来容易，但是许多的覆盖方式会导致错误，并且产严重后果。最容易避免这类问题的办法就是不覆盖 equals 方法，在这种情况下，类的每个实例都只与它自身相等。如果满足以下任何一个条件：

1. 类的每个实例本质上都是唯一的。

   对于代表活动的实体，而不是值 (value) 的类来说的却如此，例如 Thread。

   Object 提供的 equals 实现对于这些类来说是正确的。

2. 类没有必要提供 “逻辑相等” (logical equality) 的测试功能。

   例如，java.util.regex.Pattern 可以覆盖 equals，以检查两个 Pattern 实例是否代表同一个正则表达式，但是设计者并不认为客户需要或者期望这样的功能。

   在这类情况下，Object 继承得到的 equals 实现已经足够了。

3. 超类已经覆盖了 equals，超类的行为对于这个类也是合适的。

   大多数的 Set 实现都从 AbstractSet 继承了 equals 实现， List 实现从 AbstractList 继承了 equals 实现，Map 实现从 AbstractMap 继承了 equals 实现。

那么什么时候应该覆盖 equals 方法呢？如果类具有自己的 “逻辑相等” (logical equality) 概念，而且超类还没有覆盖 equals。这通常属于 “值类” (value class) 的情况。值类仅仅是表示值的类，例如 Integer 或者 String。程序员在利用 equals 方法来比较值对象的引用时，希望知道它们逻辑上是否相等，而不是像了解它们是否指向同一个对象。为了满足要求，必须覆盖 equals 方法，这样做也使得这个类的实例可以被用作映射表的键和值，或者集合的元素，使映射或集合表现出预期的行为。

有一种值类不需要覆盖 equals 方法，即用实例受控 (见第1条) 确保 “每个值至多只存在一个对象”的类。枚举类型(见第34条)就属于这种类。对于这种类而言，逻辑相同与对象等同是一回事，此时 Object 的 equals 方法等同于逻辑意义上的 equals 方法。

在覆盖 equals 方法的时候，必须遵守它的通用约定。以下是约定内容，Object 的规范。

equals 方法实现了等价关系 (equivalence relation)，其属性如下：(Ryuu : 感觉自己回到了离散数学)

• 自反性 (reflexive)

  对于任何非 null 的引用 x，x.equals(x) 必须返回 true。

• 对称性 (symmetric)

  对于任意非 null 的引用 x，y。当且仅当 x.equals(y) 返回 true 时，y.equals(x) 必须返回 true。

• 传递性 (transitive)

  对于任何非 null 的引用 x，y，z。如果 x.equals(y) 且 y.equals(z) 返回 true，x.equals(z) 也必须返回 true。

• 一致性 (consistent)

  对于任何非 null 的引用 x，y，只要 equals 的比较操作在对象中所用的信息没有被修改，任意次对 x.equals(y) 的调用，一致返回 true 或一致返回 false。

• 对于任何非 null 的引用值 x，x.equals(null) 必须返回 false。

除非你对数学特别感兴趣，否则这些规则看起来有点让人恐惧，但是不要忽视这些规则，如果违反了，程序很容易出错且很难找到错误根源。一个类的实例通常会被频繁的传递给另一个类的实例。许多类，包括所有的集合类 (collection class) 在内，都依赖于传递给它们的对象是否遵守了 equals 约定。

幸运的是，虽然这些约定看起来很吓人。实际上并不复杂。一旦了解了这些约定，要遵守它们并不困难。

自反性 (Reflexivity) —— 仅仅说明对象等于自身。假如违反，将该类的实例添加到集合中，调用集合的 contains 方法，将告知该集合不包含刚刚添加的元素。

对称性 (Symmetry) —— 任何两个对象对于 “它们是否等同” 的问题都必须保持一致。违反该条件的清醒不难想象。以下类实现了一个不区分大小写的字符串。字符串由 toString 保存，但在 equals 操作中被忽略。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

// Broken - violates symmetry
public final class CaseInsensitiveString {
    private final String s;

    public CaseInsensitiveString(String s) {
        this.s = Objects.requireNonNull(s);
    }

    // Broken - violates symmetry
    @Override
    public boolean equals(Object o) {
        if (o instanceof CaseInsensitiveString)
            return s.equalsIgnoreCase(((CaseInsensitiveString) o).s);
        if (o instanceof String) // One-way interoperability!
            return s.equalsIgnoreCase((String) o);
        return false;
    }

    public static void main(String[] args) {
        CaseInsensitiveString cis = new CaseInsensitiveString("Polish");
        String s = "Polish";
        System.out.println(cis.equals(s)); // true
        System.out.println(s.equals(cis)); // false
    }
}

在该类中 equals 企图与普通字符串对象进行互操作。正如注释结果，问题在于 CaseInsensitiveString 类中的 equals 知道普通字符串对象，但 String 类中的 equals 方法却不知道 CaseInsensitiveString 。显然这违反了对称性。

若将 CaseInsensitiveString 的对象置入集合：

1
2
3

List<CaseInsensitiveString> list = new ArrayList<>();
list.add(cis);
System.out.println(list.contains(s)); // false

在当前的 OpenJDK list.contains(s) 返回的是 false，实际上根据实现的不同，可能会返回 true 或者抛出一个运行时异常。

一旦违反了 equals 约定，当其他对象面对你的对象时，你完全不知道这些对象的行为会怎么样。

为解决该问题，只需把企图与 String 互操作的这段代码从 equals 方法中去掉就可以了：

1
2
3
4

@Override
public boolean equals(Object o) {
    return o instanceof CaseInsensitiveString && ((CaseInsensitiveString) o).s.equalsIgnoreCase(s);
}

传递性 (Transitivity) —— 若一个对象等于第二个对象，第二个对象等于第三个对象，则第一个对象等于第三个对象。用子类举例，将一个新的值组件 (value component) 添加到了超类中。子类增加的信息会影响 equals 的比较结果。首先以一个不可变的二维整型 Point 类作为开始：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

public class Point {
    private final int x;
    private final int y;

    public Point(int x, int y) {
        this.x = x;
        this.y = y;
    }

    @Override
    public boolean equals(Object o) {
        if (!(o instanceof Point p)) return false;
        return x == p.x && y == p.y;
    }
}

假如想要扩展这个类，为其添加颜色信息：

1
2
3
4
5
6
7
8

public class ColorPoint extends Point {
    private final Color color;

    public ColorPoint(int x, int y, Color color) {
        super(x, y);
        this.color = color;
    }
}

如果完全不提供 equals 方法，而是直接从 Point 继承过来，在 equals 做比较的时候颜色信息就被忽略了。虽然这不会违反 equals 约定，但很明显此方案是无法接受的。假设编写了一个 equals 方法，只有当它的参数是另一个有色点，并且具有相同的位置和颜色时，他才会返回 true：

1
2
3
4
5
6

// Broken - violates symmetry
@Override
public boolean equals(Object o) {
    if (!(o instanceof ColorPoint)) return false;
    return super.equals(o) && ((ColorPoint) o).color == color;
}

问题在于，比较普通点和有色点，以及相反的情况时，可能会得到不同的结果。前一种忽略了颜色信息，而后一种则总是返回 false，因为参数的类型不正确。

1
2
3
4

Point p = new Point(1, 2);
ColorPoint cp = new ColorPoint(1, 2, Color.RED);
System.out.println(p.equals(cp)); // true
System.out.println(cp.equals(p)); // false

可以做以下的尝试来修正上述问题，让 ColorPoint.equals 在进行 “混合比较” 时忽略颜色信息：

1
2
3
4
5
6
7
8
9
10
11
12

// Broken - violates transitivity!
@Override
public boolean equals(Object o) {
    if (!(o instanceof Point)) return false;

    // If o is a normal Point,do a color-blind comparison
    if (!(o instanceof ColorPoint))
        return o.equals(this);

    // o is a ColorPoint; do a full comparison
    return super.equals(o) && ((ColorPoint) o).color == color;
}

这种方法提供了对称性，但是牺牲了传递性：

1
2
3
4
5
6

ColorPoint p1 = new ColorPoint(1, 2, Color.RED);
Point p2 = new Point(1, 2);
ColorPoint p3 = new ColorPoint(1, 2, Color.BLUE);
System.out.println(p1.equals(p2)); // true
System.out.println(p2.equals(p3)); // true
System.out.println(p1.equals(p3)); // false

前两种是不考虑颜色的色盲比较，而第三种却考虑了颜色。

此外，该方法还可能导致无限的递归：假设 Point 有两个子类，ColorPoint 和 SmellPoint，它们各自都带有这种 equals 方法。那么对于 colorPoint.equals(smellpoint) 的调用将抛出 StackOverflowError 异常。

那么该如何解决呢？事实上，这是面向对象语言中关于等价关系的一个基本问题。无法在扩展可实例化的类的同时，既增加新的值组件，同时又保留 equals 约定，除非愿意放弃面向对象的抽象所带来的优势。

你可能听说过，在 equals 方法中用 getClass 测试代替 instanceof 测试，可以扩展可实例化的类和新增值组件，同时保留 equals 约定：

1
2
3
4
5
6
7

// Broken - violates Liskov substitution principle
@Override
public boolean equals(Object o) {
    if (o == null || getClass() != o.getClass()) return false;
    Point point = (Point) o;
    return x == point.x && y == point.y;
}

这段程序只有当对象具有相同的实现类事，才能使对象等同。但其结果是无法令人接受的：Point 子类的实例仍然是一个 Point，它仍然需要发挥作用，但是如果采用了这种方法，它将无法完成任务！

假设要编写一个方法，以检验某个点是否在单位圆中，以下是可采用的一种方法：

1
2
3
4
5
6
7
8
9

// Initialize unitCircle to contain all Points on the unit circle
private static final Set<Point> unitCircle = Set.of(
        new Point(1, 0), new Point(0, 1),
        new Point(-1, 0), new Point(0, -1)
);

public static boolean onUnitCircle(Point p) {
    return unitCircle.contains(p);
}

虽然这可能不是最好的方法，但是这是可行的。

但是，若通过某种不添加值组件的方法扩展 Point，例如让它的构造器记录创建了多少个实例：

1
2
3
4
5
6
7
8
9
10
11
12

public class CounterPoint extends Point {
    private static final AtomicInteger counter = new AtomicInteger();

    public CounterPoint(int x, int y) {
        super(x, y);
        counter.incrementAndGet();
    }

    public static int numberCreated() {
        return counter.get();
    }
}

里氏替换原则 (Liskov substitution principle) 认为，一个类型的任何重要属性也将适用于它的子类型。因此为该类型编写的任何方法，在他的子类型上也应该同样运行得很好 [Liskov 87]。若将 CounterPoint 实例传递给 onUnitCircle 方法。若在 Point 类中使用了基于 getClass 的 equals 方法，则返回 false。这是因为 onUnitCircle 方法所用的 HashSet 这样的集合，利用 equals 方法检验包含条件，没有任何 CounterPoint 实例与任何 Point 对应。但是，如果在 Point 上使用适当的基于 instanceof 的 equals 方法，当遇到 CounterPoint 时，相同的 onUnitCircle 方法就会工作得很好。遵从第18条 “复合优先于继承” 的建议。不再让 ColorPoint 扩展 Point，而是在 ColorPoint 中加入一个私有的 Point，以及一个公有的视图 (view) 方法 (见第6条)，此方法返回一个与该有色点处在相同位置的普通 Point 对象：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

// Add a value component without violating the equals contract
public class ColorPoint {
    private final Point point;
    private final Color color;

    public ColorPoint(Point point, Color color) {
        this.point = point;
        this.color = color;
    }

    /**
     * Returns the point-view of this color point.
     * @return point
     */
    public Point asPoint() {
        return point;
    }

    @Override
    public boolean equals(Object o) {
        if (!(o instanceof ColorPoint that)) return false;
        return that.point.equals(point) && that.color.equals(color);
    }
}

在 Java 平台类库中，有一些类扩展了可实例化类，添加了新的值组件。例如，java.sql.Timestamp 对 java.util.Date 进行扩展，并增加了 nanoseconds 域。Timestamp 的 equals 实现确实违反了对称性，如果 Timestamp 和 Date 对象用于同一个集合中，或者以其他的方式被混合在一起，则会引起不正确的行为。Timestamp 类有一个免责声明，告诫程序员不要混合使用 Date 和 Timestamp 对象。只要不把它们混合在一起就不会有麻烦。除此之外，没有其他的措施可以防止此问题，并且错误将很难调试。Timestamp 的这种行为是个错误，不值得效仿。

1
2
3
4

// java.util.Date * DON'T DO THIS!
public boolean equals(Object obj) {
    return obj instanceof Date && getTime() == ((Date) obj).getTime();
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

// java.sql.Timestamp extends java.util.Date * DON'T DO THIS!
public boolean equals(java.lang.Object ts) {
  if (ts instanceof Timestamp) {
    return this.equals((Timestamp)ts);
  } else {
    return false;
  }
}

public boolean equals(Timestamp ts) {
    if (super.equals(ts)) {
        if  (nanos == ts.nanos) {
            return true;
        } else {
            return false;
        }
    } else {
        return false;
    }
}

注意，你可以在一个抽象 (abstract) 类的子类中增加新的值组件且不违反 equals 约定。对于根据第23条建议而得到的那种类层次结构来说，这一点十分重要。例如，有一抽象类 Shape ，没有任何的值组件，Circle 子类添加了一个 radius 域，Rectangle 子类添加了 length 和 width 域。只要不能直接创造超类的实例，前面所述的种种问题都不会发生。

一致性 (Consistency) —— 如果两个对象相等，那么它们将始终保持相等，除非它们中有一个对象 (或者两个) 被修改了。换句话说，可变对象在不同的时候可以与不同的对象相等，而不可变对象则不会这样。当编写一个类时，应仔细考虑它是否应该是不可变的 (见第17条)。如果认为它应是不可变的，就必须保证 equals 方法满足这样的限制条件：相等的永远相等，不相等的永远不相等。

无论如何，不要使 equals 方法依赖于不可靠的资源。如果违反了这条禁令，想要满足一致性要求将十分困难。例如，java.net.URL 的 equals 方法依赖于对 URL 中主机 IP 地址的比较。随时间的推移，不能确保产生相同的结果，IP 地址有可能发生变化。这会违反 equals 约定，在实践中可能引发一些问题。URL equals 方法是一个大错误，不应该模仿。遗憾的是，因为兼容性的要求，这一行为无法被改变。为了避免发生这种问题，equals 方法应该对驻留在内存中的对象执行确定性的计算。

1
2
3
4
5
6
7
8

// java.net.URL * DON'T DO THIS!
transient URLStreamHandler handler;

public boolean equals(Object obj) {
    if (!(obj instanceof URL)) return false;
    URL u2 = (URL)obj;
    return handler.equals(this, u2);
}

1
2
3
4

// java.net.URLStreamHandler * DON'T DO THIS!
protected boolean equals(URL u1, URL u2) {
    return Objects.equals(u1.getRef(), u2.getRef()) && sameFile(u1, u2);
}

非空性 (Non-nullity) —— 暂且如此称呼。所有的对象都不能等于 null。尽管很难想象，在什么情况下 o.equals(null) 调用会意外地返回 true，但是意外抛出 NullPointerException 异常的情况不难想象。通用约定不允许抛出 NullPointerException 异常。许多类的 equals 方法都通过一个显式的 null 测试来防止该情况：

1
2
3
4
5
6

// Unnessasary!
@Override
public boolean equals(Object o) {
    if(o == null) return false;
    ...
}

然而这项测试是不必要的。为了测试其参数的等同性，equals 方法必须先把参数转换为适当的类型，以便可以调用它的访问方法，或者访问它的域。在进行转换之前， equals 方法必须使用 instanceof 操作符，检查其参数的类型是否正确：

1
2
3
4
5
6

@Override
public boolean equals(Object o) {
    if (!(o instanceof MyType)) return false;
    MyType mt = (MyType) o;
    ...
}

如果漏掉类型检查，并且传递给 equals 方法的参数又是错误的类型，那么equals 方法将会抛出 ClassCastException 异常，这违反了 equals 约定。但是，**如果 instanceof 操作符的第一个操作数为 null，那么，不管第二个操作数是哪种类型，instanceof 操作符都会指定应该返回的 false [JLS，15.20.2]**。因此如果把 null 传给 equals 方法，类型检查就会返回 false，所以不需要显示的 null 检查。

结合所有这些要求，得出了以下实现高质量 equals 方法的诀窍：

1. 使用 == 操作符检查 “参数是否为这个对象的引用”。

   如果是，则返回 true。这只不过是一种性能优化，如果比较操作性能消耗过大，就值得这么做。

2. 使用 instanceof 操作符检查 “参数是否为正确的类型”。

   如果不是，则返回 false。一般来说，”正确的类型”是指 equals 方法所在的类。某些情况下是指该类所实现的某个接口。如果类实现的接口改进了 equals 约定，允许了在实现了该接口的类之间进行比较，那么就使用接口。集合接口如Set、List、Map 和 Map.Entry 具有这样的特性。

3. 把参数转换成正确的类型。

   因为转换之前进行过 instanceof 测试，所以确保会成功。

4. 对于该类的每个 “关键” (significant) 域，检查参数中的域是否与该对象中对应的域相匹配。

   如果这些测试全部通过，返回 true；否则返回 false。

   如果第二步中的类型是接口，就必须通过接口方法访问参数中的域；

   如果该类型是类，也许就能直接访问其参数，这要取决于它们的可访问性。

对于对象引用域，可以递归地调用 equals 方法；

对于既不是 float 也不是 double 类型的基本类型域，可以使用 == 操作符进行比较；

对于 float 域，可以使用静态 Float.compare(float, float) 方法； 对于 double 域，使用 Double.compare(double, double)。对这两个域进行特殊处理是有必要的，因为存在着 Float.NaN、-0.0f 以及类似的 double 常量；详细信息请参考 JLS 15.21.1 或者 Float.equals 的文档。虽然可以用静态方法 Float.compare Double.compare 进行比较，但是每次比较都要进行自动装箱，这将导致性能下降。对于数组域，则要把以上这些指导原则应用到每一个元素上。如果数组域的每个元素都很重要，可以使用 Arrays.equals 方法。

有些对象引用域包含 null 可能是合法的，所以，为了避免可能导致 NullPointerException 异常，使用静态方法 Objects.equals(Object, Object) 来检查这些类域的等同性。

对于有些类，比如前面提到的CaseInsensitiveString类，域的比较要比简单的等同性测试复杂得多。如果是这种情况，可能希望保存该域的一个“范式”（canonical form），这样equals方法就可以根据这些范式进行低开销的精确比较，而不是高开销的非精确比较。这种方法对于不可变类（见第17条）是最为合适的；如果对象可能发生变化，就必须使其范式保持最新。

域的比较顺序可能会影响equals方法的性能。为了获得最佳的性能，应该最先比较最有可能不一致的域，或者是开销最低的域，最理想的情况是两个条件同时满足的域。不应该比较那些不属于对象逻辑状态的域，例如用于同步操作的 Lock 域。也不需要比较衍生域 (derived field)，因为这些域可以由 “关键域” (significant field)计算获得，但是这样做有可能提高 equals 方法的性能。如果衍生域代表了整个对象的综合描述，比较这个域可以节省在比较失败时去比较实际数据所需要的开销。例如，假设有一个 Polygon 类，缓存了其面积。若两个多边形面积不同，则没有必要去比较它们的边和顶点。

在编写完equals方法之后，应该问自己三个问题：它是否是对称的、传递的、一致的？并且不要只是自问，还要编写单元测试来检验这些特性，除非用AutoValue (后面会讲到) 生成 equals 方法，在这种情况下就可以放心地省略测试。如果答案是否定的，就要找出原因，再相应地修改 equals 方法。当然， equals 方法也必须满足其他两个特性 (自反性和非空性)，但是这两种特性通常会自动满足。

根据上面的诀窍构建 equals 方法的具体例子：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

// Class with a typical equals method
public final class PhoneNumber {
    private final short areaCode, prefix, lineNum;

    public PhoneNumber(int areaCode, int prefix, int lineNum) {
        this.areaCode = rangeCheck(areaCode, 999, "areaCode");
        this.prefix = rangeCheck(prefix, 999, "prefix");
        this.lineNum = rangeCheck(lineNum, 9999, "line num");
    }

    private static short rangeCheck(int val, int max, String arg) {
        if (val < 0 || val > max) throw new IllegalArgumentException(arg + " : " + val);
        return (short) val;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (!(o instanceof PhoneNumber that)) return false;
        return areaCode == that.areaCode && prefix == that.prefix && lineNum == that.lineNum;
    }
}

下面是最后的一些告诫：

• 覆盖 equals 时总要覆盖 hashCode

  为了让关注点在 equals 方法上，本条建议中都没有覆盖 hashCode，详情见第11条。

• 不要企图让 equals 方法过于智能。

  如果只是简单地测试域中的值是否相等，则不难做到遵守 equals 约定。如果想过度地去寻求各种等价关系，则很容易陷入麻烦之中。把任何一种别名形式考虑到等价的范围内，往往不会是个好主意。例如，File类不应该试图把指向同一个文件的符号链接 (symbolic link) 当作相等的对象来看待。所幸 File 类没有这样做。

• 不要将 equals 声明中的 Object 对象替换为其他的类型。

  程序员编写出下面这样的 equals 方法并不鲜见，这会使程序员花上数个小时都搞不清为什么它不能正常工作：

  1 2 3 4 5

  // DON'T DO THIS! @Override public boolean equals(MyClass o) { ... }

  问题在于，这个方法并没有 重写 (override) Object.equals，因为它的参数应该是 Object 类型，相反，它重载 (overload) 了 Object.equals (见52条)。在正常 equals 方法的基础上，再提供一个 “强类型” (strongly typed) 的 equals 方法，这是无法接受的，因为会导致子类中的 Override 注解产生错误的正值，带来错误的安全感。
  @Override 注解的用法一致，就如本条目中所示，可以防止犯这种错误 (见第40条)。这个equals方法不能编译，错误消息会告诉你到底哪里出了问题：

  1 2 3 4 5

  // Still broken, but won't compile @Override public boolean equals(MyClass o) { ... }

编写和测试 equals (及 hashCode) 方法都是十分烦琐的，得到的代码也很琐碎。代替手工编写和测试这些方法的最佳途径，是使用 Google 开源的 AutoValue 框架，它会自动替你生成这些方法，通过类中的单个注解就能触发。在大多数情况下，AutoValue 生成的方法本质上与你亲自编写的方法是一样的。

IDE 也有工具可以生成 equals 和 hashCode 方法，但得到的源代码比使用 Auto-Value 的更加冗长，可读性也更差，它无法自动追踪类中的变化，因此需要进行测试。也就是说，让 IDE 生成 equals (及 hashCode) 方法，通常优于手工实现它们，因为 IDE 不会犯粗心的错误，但是程序员会犯错。

总而言之，不要轻易重写 equals 方法，除非迫不得已。因为在许多情况下，从 Object 处继承的实现正是你想要的。如果覆盖 equals，一定要比较这个类的所有关键域，并且查看它们是否遵守 equals 约定的所有五个条款。

Java 类库中包括许多必须通过调用 close 方法来手工关闭的资源。例如 InputStream、OutputStream 和 java.sql.Connection。客户端经常会忽略资源的关闭。虽然这其中的许多资源都是用终结方法作为安全网，但是效果并不理想(见第8条)。

根据经验，try-finally 语句是确保资源会被适时关闭的最佳方法，就算发生异常或者返回也一样：

1
2
3
4
5
6
7
8

public static String firstLineOfFile(String path) throws IOException {
    BufferedReader br = new BufferedReader(new FileReader(path));
    try {
        return br.readLine();
    } finally {
        br.close();
    }
}

这看起来似乎没有什么问题，但如果再加入一个资源，就会变得糟糕了：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

public static void copy(String src, String dst) throws IOException {
    FileInputStream in = new FileInputStream(src);
    try {
        OutputStream out = new FileOutputStream(dst);
        try {
            byte[] buf = new byte[BUFFER_SIZE];
            int n;
            while ((n = in.read(buf)) >= 0)
                out.write(buf, 0, n);
        } finally {
            out.close();
        }
    } finally {
        in.close();
    }
}

这可能让人难以置信，不过就算优秀的程序员也经常犯这样的错误。Joshua Bloch (本书作者) 在《Java Puzzlers》[Bloch5] 第88页犯过该错误，时隔多年都无人发现。事实上，在 2007年，close 方法在 Java 类库中有 2/3 都用错了。

即使用 try-finally 语句正确地关闭了资源 (如前两段代码)，依然存在许多不足。因为在 try 块和 finally 块中的代码，都会抛出异常。例如，在 firstLineOfFile 中，如果因为物理设备损坏，那么调用 readLine、close 就会抛出异常。这种情况下第二个异常完全抹除了第一个异常。在异常堆栈轨迹中，完全没有第一个异常的记录，这会导致调试变得非常复杂，因为通常需要看到第一个异常才能诊断出问题何在，虽然可以通过编写代码来禁止第二个异常，保留第一个异常，但是实现起来太繁琐了。

当 Java 7 引入 try-with-resources 语句时 [JLS，14.20.3]，所有这些问题一下子就全部解决了。要使用这个构造的资源，必须先实现 AutoCloseable 接口，其中包括了单个返回 void 的 close 方法。Java 类库与第三方类库中的许多类和接口，现在都实现或扩展了 AutoCloseable 接口。如果编写了一个类，它代表的是必须被关闭的资源，那么这个类也应该实现 AutoCloseable。

以下是使用 try-with-resources 的两个范例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

// try-with-resources - the best way to close resources!
public static String firstLineOfFile(String path) throws IOException {
    try (BufferedReader br = new BufferedReader(new FileReader(path))) {
        return br.readLine();
    }
}

// try-with-resources on multiple resources - short and sweet
public static void copy(String src, String dst) throws IOException {
    try (FileInputStream in = new FileInputStream(src); OutputStream out = new FileOutputStream(dst)) {
        byte[] buf = new byte[BUFFER_SIZE];
        int n;
        while ((n = in.read(buf)) >= 0)
            out.write(buf, 0, n);
    }
}

使用 try-with-resources 不仅使代码变得更简洁易懂，也更容易进行诊断。以 firstLineOfFile 为例，如果调用 readLine 和 (不可见的) close 方法都抛出异常，后一个异常就会被禁止，以保留第一个异常。事实上，为了保留你想看到的那个异常，即使是多个异常都可以被禁止。这些异常禁止并不是被简单的抛弃了，而是会被打印在堆栈轨迹中，并注明它们是被禁止的异常。通过编程调用 getSuppressed 方法可以访问到它们，getSuppressed 方法也已经添加在 Java 7 的 Throwalble 中了。

在 try-with-resources 语句中还可以使用 catch 子句，就像在平时的 try-finally 语句中一样。这样既可以处理异常，又不需要再套一层代码。

该 firstLineOfFile 方法没有抛出异常，但如果他无法打开文件，或者无法从中读取，就会返回一个默认值：

1
2
3
4
5
6
7
8

// try-with-resources with a catch clause
public static String firstLineOfFile(String path, String defaultVal) {
    try (BufferedReader br = new BufferedReader(new FileReader(path))) {
        return br.readLine();
    } catch (IOException e) {
        return defaultVal;
    }
}

在处理必须关闭的资源时，始终优先考虑 try-with-resources ，而不是用 try-finally。这样得到的代码将更加简洁、清晰。产生的异常也更有价值，这是 try-finally 不能做到的。

Java 类库中包含了几种注解类型。一般来说，其中最重要的是 @Override 注解。该注解仅能用于方法声明，表示被注解的方法声明覆盖了超类中的一个方法声明。坚持使用该注解，可以防止一大类的非法错误。请看代码段

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

/**
 * Can you spot the bug?
 * result: 260
 */
public class Bigram {
    private final char first;
    private final char second;

    public Bigram(char first, char second) {
        this.first = first;
        this.second = second;
    }

    public boolean equals(Bigram b) {
        return first == b.first && second == b.second;
    }

    public int hashCode() {
        return 31 * first + second;
    }

    public static void main(String[] args) {
        Set<Bigram> s = new HashSet<>();
        for (int i = 0; i < 10; i++) {
            for (char ch = 'a'; ch <= 'z'; ch++) {
                s.add(new Bigram(ch, ch));
            }
        }
        System.out.println(s.size());
    }
}

该程序将反复的把 26 个双字母组合添加进集合中 (每个字母组合都由两个相同的小写字母组成)，随后打印该集合的大小。结果见注释，期望的结果是 26 ，因为存在重复添加相同字母组合的情况。

显然 Bigram 类的创建者原本想覆盖 equals 方法(见第10条)，同时还记得覆盖 hashCode。实际上 equals 没有被重写，而是被重载了。重写 Object.equals 必须定义一个参数为 Object 类型的 equals 方法，但Bigram 类中定义的是 Bigram 类型，因此 Bigram 类从Object 类继承了equals ，该 equals 比较对象的同一性 (identity)，就像 == 操作符一样。所以对于每一个 bigram 的重复添加，都被看做是不同的，这就是结果为 260 的原因。

幸运的是，编译器可以可以帮助你发现这个错误，但是需要告知编译器想要重写 Object.equals才行。用 @Override 标注Bigram.equals，如下

1
2
3
4
5
6
7
8

/**
* DON'T DO THIS!
* Error: Method does not override method from its superclass
*/
@Override
public boolean equals(Bigram b) {
    return first == b.first && second == b.second;
}

如果插入这个注解，会发现错误信息。将其改正为：

1
2
3
4
5
6
7

@Override
public boolean equals(Object o) {
    if (!(o instanceof Bigram))
        return false;
    Bigram b = (Bigram) o;
    return first == b.first && second == b.second;
}

因此，应在想要重写超类声明的每个方法中使用 Override 注解。

Java 是一门面向对象的程序语言，Java 具备面向对象的3个基本特征：封装、继承与多态。分派调用过程将会解释多态性特征的一些最基本的体现，如 Java 虚拟机如何实现 “重载” 和 “重写”。

静态分派

“分派” (Dispatch) 本身就带有动态性，一般不应用在静态语境中，在英文原版的 《Java 虚拟机规范》和《Java 语言规范》里的说法都是 “Method Overload Resolution”，实际应当归于 “解析”。但许多翻译的中文资料将其称为 “静态分派”。

为解释静态分派与重载 (Overload)，请看如下代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

/**
 * hello, guy!
 * hello, guy!
 */
public class StaticDispatch {
    public static void main(String[] args) {
        Human man = new Man();
        Human woman = new Woman();
        StaticDispatch sd = new StaticDispatch();
        sd.sayHello(man);
        sd.sayHello(woman);
    }

    static abstract class Human {
    }

    static class Man extends Human {
    }

    static class Woman extends Human {
    }

    private void sayHello(Human guy) {
        System.out.println("hello, guy!");
    }

    private void sayHello(Man guy) {
        System.out.println("hello, gentleman!");
    }

    private void sayHello(Woman guy) {
        System.out.println("hello, lady!");
    }
}

相信对 Java 稍有了解的程序员看完代码后都能判断出正确的结果。但为何虚拟机会选择执行参数为 Human 的重载呢？首先需要弄清两个关键概念：

1

Human man = new Man();

以上代码中的 “Human” 称为变量的 “静态类型” (Static Type)，或者叫做 “外观类型” (Apparent Type)，后面的 “Man” 则被称为变量的 “实际类型” (Actual Type) 或者叫 “运行时类型” (Runtime Type)。外观类型和实际类型在程序中都可能会发生变化，区别是外观类型的变化仅仅在使用时发生，变量本身的外观类型不会改变，并且最终的外观类型在编译期是可知的；而实际类型变化的结果在运行期才可以确定，编译器在编译程序的时候并不知道一个对象的实际类型是什么。

不妨通过以下代码解释

1
2
3
4
5
6

// 实际类型变化
Human human = new Random().nextBoolean() ? new Man() : new Woman();

// 外观类型变化
sd.sayHello((Man) human);
sd.sayHello((Woman) human);

human 的实际类型是可变的 (根据 nextBoolean() 的值决定)，编译期是不可知的，必须等到运行时才可以确定。human 的外观类型是 Human，可以在使用时临时改变类型，但这种改变在编译期是可知的，两次 sayHello 的调用，在编译期完全可以明确是 Man 还是 Women。

回到最先的代码 main 中两次调用 sd.sayHello ，此时调用哪个重载版本完全取决于传入参数的数据类型。代码中定义了两个实际类型不同，外观类型却相同的对象。虚拟机 (准确的来说是编译器) 重载时是通过参数的外观类型而不是实际类型作为判定依据的。外观类型在编译期可知，在编译阶段 Javac 编译器根据参数的外观类型决定了使用哪个重载版本，因此选择了 sayHello(Human) 作为调用的目标，并将这个方法的符号引用写到 main 里的两条invokevirtual 指令的参数中，如下反汇编的 26: 与 31:。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

// javap -c 反汇编
public static void main(java.lang.String[]);
    Code:
       0: new           #7                  // class StaticDispatch$Man
       3: dup
       4: invokespecial #9                  // Method StaticDispatch$Man."<init>":()V
       7: astore_1
       8: new           #10                 // class StaticDispatch$Woman
      11: dup
      12: invokespecial #12                 // Method StaticDispatch$Woman."<init>":()V
      15: astore_2
      16: new           #13                 // class StaticDispatch
      19: dup
      20: invokespecial #15                 // Method "<init>":()V
      23: astore_3
      24: aload_3
      25: aload_1
      26: invokevirtual #16                 // Method sayHello:(LStaticDispatch$Human;)V
      29: aload_3
      30: aload_2
      31: invokevirtual #16                 // Method sayHello:(LStaticDispatch$Human;)V
      34: return

所有依赖外观类型来决定方法执行版本的分派动作，都称为静态分派。静态分派最典型的应用表现就是方法的重载。静态分派发生在编译阶段，因此确定静态分派的动作实际上不是由虚拟机来执行，这也是一些资料选择把静态分派归于 “解析” 而不是 “分派” 的原因。

(未完待续)

动态分派

动态分派与 Java 语言动态性的另一重要体现 —— 重写 (Override) 有着很密切的关联。请看如下代码段

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

/**
 * man say hello
 * woman say hello
 * woman say hello
 */
public class StaticDispatch {
    public static void main(String[] args) {
        Human man = new Man();
        Human woman = new Woman();
        man.sayHello();
        woman.sayHello();
        man = new Woman();
        man.sayHello();
    }

    static abstract class Human {
        protected abstract void sayHello();
    }

    static class Man extends Human {
        @Override
        public void sayHello() {
            System.out.println("man say hello");
        }
    }

    static class Woman extends Human {
        @Override
        protected void sayHello() {
            System.out.println("woman say hello");
        }
    }
}

对于习惯了面向对象的 Java 程序员来说，运行结果正如预期。但 Java 虚拟机是如何判断应该调用哪个方法的？

显然这里的选择调用的方法不可能再根据外观类型来决定。因为该实例的两个对象外观类型都是 Human 产生了不同的行为。man 在两次调用中还执行了两个不同的方法。原因很明显，因为这两个变量的实际类型不同。

Java 是如何根据实际类型来分派方法执行的版本的呢？请看如下代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

public static void main(java.lang.String[]);
    Code:
       0: new           #7                  // class dispatch/DynamicDispatch$Man
       3: dup
       4: invokespecial #9                  // Method dispatch/DynamicDispatch$Man."<init>":()V
       7: astore_1
       8: new           #10                 // class dispatch/DynamicDispatch$Woman
      11: dup
      12: invokespecial #12                 // Method dispatch/DynamicDispatch$Woman."<init>":()V
      15: astore_2
      16: aload_1
      17: invokevirtual #13                 // Method dispatch/DynamicDispatch$Human.sayHello:()V
      20: aload_2
      21: invokevirtual #13                 // Method dispatch/DynamicDispatch$Human.sayHello:()V
      24: new           #10                 // class dispatch/DynamicDispatch$Woman
      27: dup
      28: invokespecial #12                 // Method dispatch/DynamicDispatch$Woman."<init>":()V
      31: astore_1
      32: aload_1
      33: invokevirtual #13                 // Method dispatch/DynamicDispatch$Human.sayHello:()V
      36: return

0 ~ 15 行是准备动作，建立 man 和 woman 的内存空间、调用 Man 和 Woman 类型的实例构造器，将这个实例引用存放到第 1、2 个局部变量表的变量槽中，这些动作实际对应以下的 Java 源码：

1
2

Human man = new Man();
Human woman = new Woman();

16 ~ 21 的 aload 指令分别把刚刚创建的两个对象的引用压到栈顶，这两个对象是执行 sayHello 的所有者，称为接收者 (Receiver)；17 和 21 行是方法调用指令，这两条调用指令单从字节码角度来看，无论是指令(都是 invokevirtual) 还是参数 ( 都是常量池中第 22 项的常量，注释显示了这个常量是 Human.sayHello 的符号引用) 都完全一样，但是这两句指令最终执行的目标方法并不相同。解决问题的关键必须从 invokevirtual 指令本身入手，要弄清楚它是如何确定调用方法版本、如何实现多态查找来着手分析才行。

根据 《Java 虚拟机规范》，invokevirtual 指令的运行时解析过程大致分为以下几个部分：

1. 找到操作数栈顶的第一个元素所指向的对象的实际类型，记作 C

2. 如果在类型 C 中找到与常量中的描述符和简单名称都相符的方法，则进行访问权限校验，

   如果通过则返回这个方法的直接引用，查找过程结束；

   不通过则返回 java.lang.IllegalAccessError 异常。

3. 否则，按继承关系自下而上依次对 C 的各个父类进行第二步的搜索及验证。

4. 若始终没有合适的方法，抛出 java.lang.AbstractMethodError 异常。

正是因为 invokevirtual 指令执行的第一步就是在运行期确定接收者的实际类型，所以两次调用中的 invokevirtual 指令并不是把常量池中方法的符号引用解析到直接引用上就结束了，还会根据方法接收者的实际类型来选择方法版本，这个过程就是 Java 语言中方法重写的本质。这种在运行期根据实际类型确定方法执行版本的分派过程称为动态分派。

这种多态性的根源在于虚方法调用指令 invokevirtual 的执行逻辑，所以这只会对方法有效，对字段无效，因为字段不使用这条指令。在 Java 中只有虚方法存在，没有虚字段。字段永远不参与多态，哪个类的方法访问某个名字的的字段时，该名字指的就是这个类能看到的那个字段。当子类声明了与父类同名的字段时，虽然在子类的内存中两个字段都会存在，但子类的字段会遮蔽父类的同名字段。

请看如下代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

// DON'T DO THIS!
/**
 * I'm Son, I have $0
 * I'm Son, I have $4
 * This guy has $2
 */
public class FieldHasNoPolymorphic {
    public static void main(String[] args) {
        Father guy = new Son();
        System.out.println("This guy has $" + guy.money);
    }

    static class Father {
        public int money = 1;

        public Father() {
            money = 2;
            showMeTheMoney();
        }

        public void showMeTheMoney() {
            System.out.println("I'm Father, I have $" + money);
        }
    }

    static class Son extends Father {
        public int money = 1;

        public Son() {
            money = 4;
            showMeTheMoney();
        }

        public void showMeTheMoney() {
            System.out.println("I'm Son, I have $" + money);
        }
    }
}

输出的两句都是 “I’m Son”，因为 Son 类在创建的时候，首先隐式调用了 Father 的构造函数，而 Father 构造函数中对 showMeTheMoney 的调用是一次虚方法的调用，执行的版本是 Son::showMeTheMoney 方法，所以输出的是 “I’m Son”。虽然父类的 money 已经初始化成 2，但 Son::showMeTheMoney 方法中访问的是子类的 money，这里的结果是 0，因为它要到子类的构造函数执行时才会被初始化。之后子类构造方法执行输出 4，main 的最后一句通过外观类型访问到了父类中的 money，输出 2。

单分派与多分派

方法的接收者与方法的参数统称为方法的宗量，该定义最早出现在《Java 与模式》。根据分派基于多少种宗量，可将分派划分为单分派和多分派两种。单分派是根据一个宗量对目标方法进行选择，多分派则是根据多于一个宗量对目标方法进行选择。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

/**
 * father choose 360
 * son choose qq
 */
public class Dispatch {
    public static void main(String[] args) {
        Father father = new Father();
        father.hardChoice(new _360());
        Father son = new Son();
        son.hardChoice(new QQ());
    }

    static class QQ {
        
    }

    static class _360 {
        
    }

    public static class Father {
        public void hardChoice(QQ arg) {
            System.out.println("father choose qq");
        }

        public void hardChoice(_360 arg) {
            System.out.println("father choose 360");
        }
    }

    public static class Son extends Father {
        public void hardChoice(QQ arg) {
            System.out.println("son choose qq");
        }

        public void hardChoice(_360 arg) {
            System.out.println("son choose 360");
        }
    }
}

这两次 hardChoice 的结果已在注释标注，重点是编译阶段中编译器的静态分派过程。选择目标方法的依据有两点：一是外观类型是 Father 还是 Son，二是方法参数是 QQ 还是 360.这次选择结果的最终产物是产生了两条 invokevirtual 指令，两条指令的参数分别为常量池中指向 Father::hardChoice(360) 及 Father::hardChoice(QQ) 方法的符号引用。因为是根据两个宗量进行选择，所以 Java 语言的静态分派属于多分派类型。

再看运行阶段中虚拟机的动态分派的过程。在执行 “son.hardChoice(new QQ());”，也就是指对应的 invokevirtual 指令时，由于编译期已经决定目标方法的签名必须为 hardChoice(QQ) ，虚拟机不管关心此时传递过来的参数到底是什么，因为其外观类型、实际类型都不会对选择构成任何影响，唯一可以影响虚拟机的该方法接受者的实际类型是 Father 还是 Son。因为只有一个宗量作为选择的依据，所以 Java 语言的动态分派属于单分派类型。

根据上述论证，如今的 Java 语言是一门静态多分派、动态单分派的语言。强调如今是因为这个结论未必会一直保持。 C# 3.0 及之前的版本与 Java 一样是动态单分派语言，但在 C# 4.0 加入dynamic 类型后，就可以很方便的实现多分派。JDK 10 时 Java 语言出现新关键字 var，但请不要将其与 C# dynamic 混淆，实际上 Java var 对应的是 C# var。它们与 dynamic 有本质区别：var 是在编译时根据声明语句的右侧表达式类型进行静态推断的，本质上这是一种语法糖(见 Effective-CSharp-1优先使用隐式类型的局部变量)；而 dynamic 在编译时完全不关心类型是什么，等到运行的时候再做类型判断。 与 C# dynamic 功能相近的是 JDK 9 时通过 JEP 276 引入的 jdk.dynalink 模块，使用 jdk.dynalink 可以实现在表达式中使用动态类型，Javac 编译器可以将其操作翻译为 invokedynamic 指令的调用点。

虚拟机动态分派实现

前文介绍的分派过程，作为对于 Java 虚拟机概念模型的解释已基本足够了，明确的解释了虚拟机在分派时会做什么这个问题。但要问 Java 虚拟机 “具体如何做到”，答案则可能因虚拟机的实现而不同而有差别。

动态分派是执行非常频繁的动作，且动态分派的方法版本选择过程需要运行时在接收者类型的方法元数据中搜索合适的目标方法。因此， Java 虚拟机实现基于执行性能的顾虑，真正运行时一般不会如此频繁地去反复搜索类型元数据，面对这种情况，一种基础且常见的优化手段是为类型在方注区中建立一个虚方法表（Virtual Method Table，也称为 vtable，与此对应的、在 invokeinterface 执行时也会用到接口方法表 —— Interface Method Table，简称 itable)，使用虚方法表索引代替元数据查找以提高性能。

虚方法表中存放着各个方法的实际入口地址。如果某个方法在子类中没有被重写，子类的虚方法表中的地址入口将与父类相同方法的入口地址一致，都是指向父类的实现入口。如果子类重写了这个方法，子类虚方法表中的地址则会被替换为指向子类实现版本的入口地址。

为了程序实现方便，拥有相同签名的方法，在父类、子类的虚方法表中都应当具有一样的索引序号，这样当类型变换时，仅需要变更查找的虚方法表，就可以从不同的虚方法表中按索引转换出所需的入口地址。虚方法表一般在类加载的连接阶段进行初始化，准备了类的变量初始值后，虚拟机会把该类的虚方法表也一同初始化完毕。

上述的查虚方法表是分派调用的一种优化手段，由于 Java 对象里面的方法默认 (即不使用 final) 就是虚方法，虚拟机除了使用虚方法表之外，为了进一步提高性能，还会用类型继承关系分析 (Class Hierarchy Analysis，CHA)、守护内联 (Guarded Inlining)、内存缓存 (Inline Cache) 等多种非稳定的激进优化来争取更大的性能空间。

Cpu 对于可能被多次访的内存区域，会将其复制到 cache 中，之后访问不再从主存中获取，提升效率。从 ram 到 cache 的复制过程(Block Transfer)，复制单位为 linesize ，此处为 64 byte。

请看如下代码段，1 与 2 所需时间差不多，甚至 2 有时时间比 1 还长 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

// int : 4 byte
// cache line : 64 byte
int[] arr = new int[1 << 26];

// 1
long t1 = System.currentTimeMillis();
for (int i = 0; i < arr.length; i++) arr[i] *= 3;
System.out.println(System.currentTimeMillis() - t1 + " ms");

// 2
long t2 = System.currentTimeMillis();
for (int i = 0; i < arr.length; i += 2) arr[i] *= 3;
System.out.println(System.currentTimeMillis() - t2 + " ms");


// 3
long t3 = System.currentTimeMillis();
for (int i = 0; i < arr.length; i += 32) arr[i] *= 3;
System.out.println(System.currentTimeMillis() - t3 + " ms");

1 与 2 Block transfer 次数相同，时间不会差太多

3 相比于 1 和 2 Block transfer 少了一倍，时间与其相差略小于一倍

冒泡排序

外层循环次数为集合元素数 - 1 (两两比较)

内层循环每次 -1 (每次循环确定最末尾数)

1
2
3
4
5
6
7
8
9
10
11

public static void bubbleSort(int[] arr) {
    for (int i = 0; i < arr.length - 1; i++) {
        for (int idx = 0; idx < arr.length - 1 - i; idx++) {
            if (arr[idx] > arr[idx + 1]) {
                int temp = arr[idx + 1];
                arr[idx + 1] = arr[idx];
                arr[idx] = temp;
            }
        }
    }
}

选择排序

默认首位数为最小，遍历后续元素，确定最小索引，交换数据

1
2
3
4
5
6
7
8
9
10
11
12
13

public static void selectSort(int[] arr) {
    for (int i = 0; i < arr.length; i++) {
        int minIdx = i;
        for (int j = i + 1; j < arr.length; j++) {
            if (arr[j] < arr[minIdx]) {
                minIdx = j;
            }
        }
        int tmp = arr[i];
        arr[i] = arr[minIdx];
        arr[minIdx] = tmp;
    }
}

插入排序

默认从二号元素开始，左侧元素为有序列

遍历时若较左侧小的数，进行移动(类冒泡)，否则直接进入下次外循环 (较左侧最近数大，则较有序列所有数大)

1
2
3
4
5
6
7
8
9
10
11
12
13
14

public static void insertionSort(int[] a) {
    int cur = 0;
    int len = a.length;
    while (++cur < len) {
        if (a[cur] < a[cur - 1]) {
            int val = a[cur];
            int idx = cur;
            while (--idx >= 0 && val < a[idx]) {
                a[idx + 1] = a[idx];
            }
            a[idx + 1] = val;
        }
    }
}

希尔排序

一种改进的插入排序

最外层循环为步长

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

public static void shellSort(int[] arr) {
    for (int step = arr.length >>> 1; step > 0; step >>>= 1) {
        for (int j = step; j < arr.length; j++) {
            for (int idx = j; idx > 0 && idx - step >= 0; idx -= step) {
                if (arr[idx] < arr[idx - step]) {
                    int temp = arr[idx - step];
                    arr[idx - step] = arr[idx];
                    arr[idx] = temp;
                } else {
                    break;
                }
            }
        }
    }
}

快速排序

首先确定一个基数，将大于/小于他的数置于其两侧，再对左右两侧集合进行递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

public static void quickSort(int[] arr, int start, int end) {
    if (start + 1 > end) {
        return;
    }
    boolean isStartWithEnd = true;
    int left = start;
    int right = end;
    int meanVal = arr[start];
    while (true) {
        if (isStartWithEnd) {
            if (arr[end] >= meanVal) {
                end--;
            } else if (arr[end] < meanVal) {
                arr[start] = arr[end];
                start++;
                isStartWithEnd = false;
            }
        } else /* if (!isStartWithHigh) */ {
            if (arr[start] <= meanVal) {
                start++;
            } else if (arr[start] > meanVal) {
                arr[end] = arr[start];
                end--;
                isStartWithEnd = true;
            }
        }
        if (start == end) {
            arr[start] = meanVal;
            break;
        }
    }
    quickSort(arr, left, start - 1);
    quickSort(arr, start + 1, right);
}

归并排序

先进行递归，将列表进行拆分，首先从最小的切分集合进行排序，之后进行合并排序，最终合并排序为一个有序表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

public static void mergeSort(int[] arr, int start, int end) {
    if (end <= start) {
        return;
    }
    int mid = (start + end) >>> 1;
    mergeSort(arr, start, mid);
    mergeSort(arr, mid + 1, end);
    int left = start;
    int right = mid + 1;
    int idx = 0;
    int[] resArr = new int[end - start + 1];
    while (left <= mid && right <= end) {
        if (arr[left] <= arr[right]) {
            resArr[idx] = arr[left];
            left++;
        } else /* arr[left] > arr[right] */ {
            resArr[idx] = arr[right];
            right++;
        }
        idx++;
    }
    while (left <= mid || right <= end) {
        if (left <= mid) {
            resArr[idx] = arr[left];
            left++;
        } else /* right <= end */ {
            resArr[idx] = arr[right];
            right++;
        }
        idx++;
    }
    if (end - start + 1 >= 0) {
        System.arraycopy(resArr, 0, arr, start, end - start + 1);
    }
}

堆排序

构建堆 (此处是升序排序，所以选择大顶堆)

1. 从第一个非叶子结点从下至上，从右至左调整，将大数置于根节点 (根节点 > 子节点)
2. 调整堆结构，持续交换堆顶元素与末尾元素，从尾部向头部逐渐递归出一个有序表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

class HeapSort {
    public static void sort(int[] arr) {
        for (int i = arr.length >>> 1; i >= 0; i--) {
            adjustHeap(arr, i, arr.length);
        }
        for (int j = arr.length - 1; j > 0; j--) {
            int tmp = arr[0];
            arr[0] = arr[j];
            arr[j] = tmp;
            adjustHeap(arr, 0, j);
        }
    }

    private static void adjustHeap(int[] arr, int cur, int len) {
        int tmp = arr[cur];
        // 若调整根节点，子节点需再调整 (idx = idx * 2 + 1)
        for (int idx = cur * 2 + 1; idx < len; idx = idx * 2 + 1) {
            // 判断 左/右子节点 中的最大子节点
            if (idx + 1 < len && arr[idx + 1] > arr[idx]) {
                idx++;
            }
            if (arr[idx] > tmp) {
                arr[cur] = arr[idx];
                cur = idx;
            } else {
                break;
            }
        }
        arr[cur] = tmp;
    }
}

基数排序

此处是最低位优先 (Least Significant Digit first，LSD) 法，从个位开始，对数组进行排序

1. 将对应位元素出现的次数存储在 buckets 中

2. buckets[i] += buckets[i - 1] 将 bucket 的值变为对应最后一个元素的索引 (此时buckets 为一个有序索引桶)，每确定一个索引的元素将对应 bucket 的值 -1，将 bucket 存储的索引移动到对应的下一个索引

   (实际上是索引 + 1，因为默认没有元素的 bucket 的值为 0，之后从 bucket 中取得索引需要 -1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

public static void radixSort(int[] arr) {
    int max = arr[0];
    int exp;
    for (int num : arr) {
        if (num > max) {
            max = num;
        }
    }
    for (exp = 1; max / exp > 0; exp *= 10) {
        int[] tmpArr = new int[arr.length];
        int[] buckets = new int[10]; // 0 ~ 9
        for (int value : arr) {
            buckets[(value / exp) % 10]++;
        }
        for (int i = 1; i < 10; i++) {
            buckets[i] += buckets[i - 1];
        }
        for (int i = arr.length - 1; i >= 0; i--) {
            tmpArr[buckets[(arr[i] / exp) % 10] - 1] = arr[i];
            buckets[(arr[i] / exp) % 10]--;
        }
        System.arraycopy(tmpArr, 0, arr, 0, arr.length);
    }
}