第 4 章继承与接口¶

原作：Josh Hug，UC Berkeley CS61B Spring 2021 配套读本。
中文翻译版，仅供非商业学习；采用 CC BY-NC-SA 4.0 许可。
原始网站：https://joshhug.gitbooks.io/hug61b/content/

4.1 导论与接口¶

问题¶

回忆上周创建的两个列表类：SLList 和 AList。查看它们的文档会发现，两者非常相似。事实上，它们提供的辅助方法完全一样。

假设要编写一个 WordUtils 类，其中包含可以对单词列表执行的函数，例如计算一个 SLList 中最长字符串的方法。

练习 4.1.1： 尝试自己编写该方法。它应接收一个字符串 SLList，并返回列表中最长的字符串。

视频讲解

我们得到的方法如下：

public static String longest(SLList<String> list) {
    int maxDex = 0;
    for (int i = 0; i < list.size(); i += 1) {
        String longestString = list.get(maxDex);
        String thisString = list.get(i);
        if (thisString.length() > longestString.length()) {
            maxDex = i;
        }
    }
    return list.get(maxDex);
}

怎样让它也适用于 AList？

实际上，只需修改方法签名中的参数。把：

SLList<String> list

改成：

AList<String> list

这样，WordUtils 中就有两个名称完全相同的方法：

public static String longest(SLList<String> list)

以及：

public static String longest(AList<String> list)

Java 允许这样做，这称为_方法重载_。调用 WordUtils.longest 时，Java 会根据你传入的参数类型决定运行哪个方法。传入 AList 就调用 AList 版本；传入 SLList 就调用 SLList 版本。

Java 能够处理名称相同、参数类型不同的方法确实很方便，但重载有几个缺点：

非常重复而且难看，因为现在有两段几乎完全相同的代码。
需要维护更多代码。若要对 longest 做一个小修改，例如修复错误，必须在每种列表类型对应的方法中都修改一次。
如果以后增加更多列表类型，每创建一个新列表类就必须再复制一份方法。

上位词、下位词与接口继承¶

视频讲解

无论在英语中还是现实生活中，词语与对象之间都存在逻辑层级。

“狗”是贵宾犬、阿拉斯加犬、哈士奇等的_上位词_；反过来，贵宾犬、阿拉斯加犬和哈士奇都是“狗”的_下位词_。

这些词构成一组“是一个（is-a）”关系：

贵宾犬是一种狗。
狗是一种犬科动物。
犬科动物是一种食肉动物。
食肉动物是一种动物。

层级关系

视频讲解

SLList 和 AList 也有相同层级：两者都是更一般的“列表”的下位类型。

我们将在 Java 中正式表示这种关系。如果 SLList 是 List61B 的下位类型，那么 SLList 类是 List61B 的子类，List61B 则是 SLList 的超类。

图 4.1.1

子类关系

要在 Java 中_表达_这种层级关系，需要完成两步：

第 1 步：为一般意义上的列表上位类型定义一种类型，命名为 List61B。
第 2 步：声明 SLList 和 AList 是该类型的下位类型。

新的 List61B 在 Java 中称为接口。接口本质上是一份契约，规定一个列表必须能做什么，但不提供这些行为的具体实现。你能想到为什么吗？

下面是 List61B 接口。此时已经完成建立层级关系的第一步，也就是创建上位类型。

public interface List61B<Item> {
    public void addFirst(Item x);
    public void add Last(Item y);
    public Item getFirst();
    public Item getLast();
    public Item removeLast();
    public Item get(int i);
    public void insert(Item x, int position);
    public int size();
}

接着完成第 2 步：声明 AList 与 SLList 是 List61B 的下位类型。在 Java 中，这种关系写在类定义中。

原本的：

public class AList<Item> {...}

加入表示关系的关键字 implements 后变为：

public class AList<Item> implements List61B<Item> {...}

implements List61B<Item> 本质上是一项承诺。AList 在说：“我保证拥有并定义 List61B 接口中规定的全部属性和行为。”

现在可以修改 WordUtils 中的 longest，让它接收 List61B，因为 AList 与 SLList 都和 List61B 具有“是一个”关系。

重写¶

视频讲解

我们已经承诺在 AList 与 SLList 中实现 List61B 规定的方法，下面就来履行承诺。

在子类中实现要求的方法时，最好在方法签名正上方加入 @Override 标签；在 CS61B 中，这实际上是强制要求。下面只为其中一个方法添加了该标签：

@Override
public void addFirst(Item x) {
    insert(x, 0);
}

需要注意，即使没有写这个标签，你依然是在重写方法。因此从纯语法角度说并非必须添加。不过，标签会像安全装置一样告诉编译器：“我打算重写这个方法。”这样有什么用？它有点像一位校对员：如果重写过程出了问题，编译器会提醒你。

假设你想重写 addLast，却不小心拼成了 addLsat。如果没有 @Override，可能很久都发现不了错误，调试会更加痛苦；如果写了 @Override，程序运行前编译器就会停止并要求修正。

接口继承¶

视频讲解

接口继承指的是：子类继承超类所规定的全部方法和行为。在“上位词与下位词”部分定义的 List61B 中，接口包含所有方法签名，却没有具体实现；真正的实现由子类提供。

这种继承还可以跨越多代。假设存在图 4.1.1 那样很长的超类/子类链，那么 AList 不仅继承 List61B 的方法，还继承它上方一直到最高超类的所有内容。换句话说，AList 也从 Collection 继承。

等号黄金法则（GRoE）¶

回忆第 2 章中的等号黄金法则：每当执行赋值 a = b，都会把 b 中的比特复制到 a 中，并要求 b 的类型与 a 兼容。不能写 Dog b = 1 或 Dog b = new Cat()，因为 1 不是 Dog，Cat 也不是 Dog。

把这条规则应用到本章之前的 longest 方法。

public static String longest(List61B<String> list) 接收一个 List61B。我们说它也能接收 AList 和 SLList，但 AList 与 List61B 明明是不同的类，为什么可行？因为 AList 与 List61B 具有“是一个”关系，所以一个 AList 应当能够放入 List61B 类型的盒子中。

练习 4.1.2： 下面的代码会编译吗？如果会，运行时会发生什么？

public static void main(String[] args) {
    List61B<String> someList = new SLList<String>();
    someList.addFirst("elk");
}

可能答案如下：

无法编译。
能够编译，但会在 new 那一行产生错误。
运行后创建一个 SLList，其地址保存在 someList 中；但调用 someList.addFirst() 时崩溃，因为 List 类没有实现 addFirst。
运行后创建一个 SLList，其地址保存在 someList 中；随后字符串 "elk" 被插入 someList 所引用的 SLList。

实现继承¶

视频讲解

之前的 List61B 接口只有方法头，用于规定 List61B 应该做什么。现在将看到，也可以直接在 List61B 中编写已经包含实现的方法。这些方法会规定 List61B 的下位类型应该怎样做。

要做到这一点，必须在方法签名中加入 default 关键字。

例如在 List61B 中定义：

default public void print() {
    for (int i = 0; i < size(); i += 1) {
        System.out.print(get(i) + " ");
    }
    System.out.println();
}

那么所有实现 List61B 的类都能直接使用该方法。

不过这个方法有一个小小的低效之处。你能发现吗？

视频讲解

对于 SLList，每次调用 get 都需要沿列表跳过许多结点。更好的办法是在沿链表前进的同时直接输出。

我们希望 SLList 采用不同于接口默认实现的输出方式，因此需要重写。在 SLList 中实现：

@Override
public void print() {
    for (Node p = sentinel.next; p != null; p = p.next) {
        System.out.print(p.item + " ");
    }
}

此后，在 SLList 上调用 print() 时，会运行这个方法，而不是 List61B 中的默认方法。

视频讲解

你可能会问：Java 怎样知道该调用哪个 print()？这是个好问题。Java 依靠动态方法选择完成这一点。

我们知道，Java 变量具有类型：

List61B<String> lst = new SLList<String>();

在上面的声明与实例化中，变量 lst 的类型是 List61B，这称为它的“静态类型”。

对象本身也具有类型。lst 指向的对象类型是 SLList。这个对象本质上是 SLList，因为通过 SLList 构造方法创建；同时由于前面讨论的“是一个”关系，它也是 List61B。对象实例化时真正使用的类型称为它的“动态类型”。

补充说明：“动态类型”这个名称非常贴切。如果以后把 lst 重新赋值为另一个类型的对象，例如一个 AList，那么 lst 的动态类型就会从 SLList 变成 AList。之所以称为动态，是因为它会随着变量当前引用的对象类型而改变。

Java 运行一个被重写的方法时，会在对象的动态类型中寻找合适的方法签名并执行。

重要：这条规则不适用于重载方法。

视频讲解

假设同一个类中有两个方法：

public static void peek(List61B<String> list) {
    System.out.println(list.getLast());
}
public static void peek(SLList<String> list) {
    System.out.println(list.getFirst());
}

并运行：

SLList<String> SP = new SLList<String>();
List61B<String> LP = SP;
SP.addLast("elk");
SP.addLast("are");
SP.addLast("cool");
peek(SP);
peek(LP);

第一次调用 peek() 会使用第二个、参数为 SLList 的版本。第二次调用会使用第一个、参数为 List61B 的版本。原因是两个重载方法之间的区别只在参数类型。Java 判断调用哪个重载方法时，查看的是参数变量的静态类型，并选择具有相同参数类型的方法。

视频讲解

接口继承与实现继承¶

怎样区分“接口继承”和“实现继承”？可以使用下面这个简单标准：

接口继承（做什么）：只说明子类应当具备哪些能力。
例如：所有列表都应能够输出自己，但具体怎样输出由各自决定。
实现继承（怎么做）：直接告诉子类应当怎样表现。
例如：列表必须按照这种特定方式输出——按顺序取得每个元素，再逐个输出。

创建这些层级时，请记住子类与超类之间应当是“是一个”关系。Cat 只有在猫是一种动物的意义上才应实现 Animal。不要使用“有一个”关系建立继承。猫有一只爪子，但 Cat 显然不应实现 Claw。

最后，实现继承虽然听起来很方便，也存在一些缺点：

人会犯错，也无法记住一切；你可能重写过某个方法，却忘记自己这样做过。
如果两个接口提供互相冲突的默认方法，冲突可能很难解决。
它容易鼓励过度复杂的代码。

接下来做什么

讨论课 4：继承

4.2 `extends`、类型转换与高阶函数¶

`extends`¶

前面我们已经看到，怎样使用 implements 关键字与接口建立层次关系。那么，如果我们希望在两个类之间建立层次关系，该怎么做呢？

假设我们想构建一个 RotatingSLList。它拥有 SLList 的所有功能，例如 addFirst、size 等，同时还增加一个 rotateRight 操作：把最后一个元素移到列表最前面。

一种做法是复制并粘贴 SLList 的所有方法，然后再写一个 rotateRight。但这样就没有利用继承的力量。继承允许子类复用已经定义好的类中的代码。因此，我们让 RotatingSLList 继承 SLList。

我们可以在类声明中使用 extends 关键字建立这种继承关系：

public class RotatingSLList<Item> extends SLList<Item>

就像 AList 与 List61B 之间存在“是一种（is-a）”关系一样，RotatingSLList 也是一种 SLList。extends 让我们保留 SLList 原有的功能，同时还可以修改它并添加新的能力。

现在既然 RotatingSLList 已经继承了 SLList，就来赋予它独有的旋转能力。

练习 4.2.1。 定义 rotateRight 方法。它应当把现有列表中的每个元素向右移动一位，并把最后一个元素移到最前面。

例如，对 [5, 9, 15, 22] 调用 rotateRight 后，应得到 [22, 5, 9, 15]。

提示：是否有某些继承而来的方法可以帮助你完成它？

视频讲解

一种实现如下：

public void rotateRight() {
    Item x = removeLast();
    addFirst(x);
}

你可能已经注意到，我们能够直接使用在 RotatingSLList 之外定义的方法，因为 extends 使它从 SLList 继承了这些方法。这也引出了一个问题：子类究竟继承了什么？

使用 extends 后，子类会继承父类的所有成员。成员包括：

所有实例变量和静态变量；
所有方法；
所有嵌套类。

但要注意：构造方法不会被继承，而且子类不能直接访问父类的私有成员。

`VengefulSLList`¶

当有人对 SLList 调用 removeLast 时，被移除的值会被直接丢弃，再也看不到了。但假如这些被放逐的元素离开之后，开始策划一场针对我们的巨大叛乱呢？这种情况下，我们就需要记住所有被 removeLast 移除的元素，以便以后找到并处理它们。

于是，我们创建一个新类 VengefulSLList，用于记住所有被 removeLast 放逐的元素。

和前面一样，我们在类声明中写明 VengefulSLList 继承自 SLList：

public class VengefulSLList<Item> extends SLList<Item>

接下来，为 VengefulSLList 添加一个 printLostItems() 方法，用于打印所有被 removeLast 移除的元素。我们可以增加一个实例变量，保存所有已删除的元素。如果使用一个 SLList 来记录它们，就可以直接调用 print() 输出全部元素。

目前的代码如下：

public class VengefulSLList<Item> extends SLList<Item> {
    SLList<Item> deletedItems;

    public void printLostItems() {
        deletedItems.print();
    }
}

VengefulSLList 的 removeLast 应当完成和 SLList.removeLast 完全相同的工作，但还要多做一步：把刚刚移除的元素加入 deletedItems。为了复用代码，我们可以重写 removeLast，并通过 super 关键字调用父类 SLList 中定义的 removeLast。

练习 4.2.2。 重写 removeLast：移除最后一个元素，把它加入 deletedItems，最后再返回该元素。

视频讲解

完整实现如下：

public class VengefulSLList<Item> extends SLList<Item> {
    SLList<Item> deletedItems;

    public VengefulSLList() {
        deletedItems = new SLList<Item>();
    }

    @Override
    public Item removeLast() {
        Item x = super.removeLast();
        deletedItems.addLast(x);
        return x;
    }

    /** Prints deleted items. */
    public void printLostItems() {
        deletedItems.print();
    }
}

构造方法不会被继承¶

如前所述，子类会继承父类的所有成员，包括实例变量、静态变量、方法和嵌套类，但不会继承构造方法。

虽然构造方法不会被继承，但 Java 要求：每个子类构造方法都必须先调用某个超类构造方法。

为什么会这样？回忆一下，extends 定义的是子类与父类之间的“是一种”关系。如果 VengefulSLList 是一种 SLList，那么每个 VengefulSLList 首先都必须按照 SLList 的规则完成初始化。

再看一个更直观的例子。假设有两个类：

public class Human {...}

public class TA extends Human {...}

让 TA 继承 Human 是合理的，因为所有助教都是人。我们希望 TA 继承人的属性和行为。

如果运行：

TA christine = new TA();

那么首先必须构造一个 Human 部分，然后才能在此基础上赋予它 TA 的特征。跳过人的构造过程，直接构造助教，在逻辑上是不完整的。

因此，我们可以使用 super 显式调用超类构造方法：

public VengefulSLList() {
    super();
    deletedItems = new SLList<Item>();
}

如果我们没有显式书写，Java 会自动调用超类的无参数构造方法。

在这个例子中，写出 super() 与省略它没有区别；它只是把 Java 原本隐式完成的操作明确写出来。但如果我们为 VengefulSLList 定义另一个构造方法，Java 自动调用的无参构造方法就可能不是我们真正需要的。

假设有一个接收初始元素的单参数构造方法。如果仍依赖 Java 隐式调用 super()，传入的元素就不会被放入父类结构中。因此，必须把该元素显式传给正确的超类构造方法：

public VengefulSLList(Item x) {
    super(x);
    deletedItems = new SLList<Item>();
}

`Object` 类¶

Java 中的每个类都是 Object 类的后代，也就是说，每个类都会继承 Object。即使类声明中没有显式写出 extends Object，它也会隐式继承 Object。

例如：

VengefulSLList 在类声明中显式 extends SLList；
SLList 隐式 extends Object。

所以，SLList 会继承 Object 的全部成员，而 VengefulSLList 又会传递性地继承 SLList 和 Object 的成员。

根据 Object 类文档，Object 提供了每个对象都应具备的操作，例如 .equals(Object obj)、.hashCode() 和 toString()。

“是一种”与“拥有一个”¶

重要提醒： extends 关键字定义的是“是一种（is-a）”关系，也就是上下位关系。一个常见错误，是把它用于“拥有一个（has-a）”关系，也就是整体与部分的关系。

决定是否继承一个类时，最好先问自己：“是一种”这个说法是否成立。

Shower（淋浴器）是一种 Bathroom（浴室）吗？不是。
VengefulSLList 是一种 SLList 吗？是。

封装¶

封装是面向对象编程的基本原则之一，也是程序员抵抗最大敌人——复杂性——的重要手段。编写大型程序时，管理复杂性是我们必须面对的主要挑战之一。

我们可以使用很多工具对抗复杂性，例如分层抽象（也就是建立抽象屏障）以及“为变化而设计”。后者强调：程序应当由模块化、可替换的组件构成，从而可以替换某一部分而不破坏整个系统。此外，隐藏其他人不需要知道的信息，也是管理大型系统的基本方法。

封装的根本思想，就是把内部信息隐藏起来。可以把它类比成人体细胞：细胞内部可能极其复杂，包含染色体、线粒体、核糖体等结构，但这些复杂性被完整地封装在一个模块中，对外呈现为一个整体。

在计算机科学中，模块可以理解为一组协同工作的、共同完成某项任务或一组相关任务的方法。例如，一个表示列表的类就是一个模块。如果模块的实现细节被隐藏在内部，而外界只能通过有文档说明的接口与它交互，我们就说这个模块是封装良好的。

以 ArrayDeque 类为例。外部代码可以通过 addLast、removeLast 等公开方法使用它，但无需理解该数据结构内部复杂的实现细节。

抽象屏障¶

理想情况下，用户不应观察到所使用的数据结构的内部工作方式。幸运的是，Java 很容易强制建立抽象屏障。通过 private 关键字，我们几乎可以阻止外部代码查看对象内部，从而避免底层复杂性暴露给外界。

继承怎样破坏封装¶

假设 Dog 类中有下面两个方法。一种实现是：

public void bark() {
    System.out.println("bark");
}

public void barkMany(int N) {
    for (int i = 0; i < N; i += 1) {
        bark();
    }
}

另一种实现是：

public void bark() {
    barkMany(1);
}

public void barkMany(int N) {
    for (int i = 0; i < N; i += 1) {
        System.out.println("bark");
    }
}

从普通用户的角度看，这两种实现提供的功能完全相同。然而，假设我们定义一个 Dog 的子类 VerboseDog，并重写它的 barkMany：

@Override
public void barkMany(int N) {
    System.out.println("As a dog, I say: ");
    for (int i = 0; i < N; i += 1) {
        bark();
    }
}

练习 4.2.3。 对一个 VerboseDog vd，在第一种 Dog 实现下，vd.barkMany(3) 会输出什么？在第二种实现下又会怎样？

A：As a dog, I say: bark bark bark
B：bark bark bark
C：其他结果

在第一种实现中，输出是 A；而在第二种实现中，程序会陷入无限递归。barkMany 调用 bark()，bark() 又调用 barkMany(1)，后者再次调用 bark()，如此无限重复。

这说明：继承会让子类的重写行为影响父类内部的方法调用，从而使父类实现细节不再完全隐藏。看似等价的两种父类实现，在存在子类重写时可能产生截然不同的结果。

类型检查与类型转换¶

在讨论类型与转换之前，先回顾动态方法选择。动态方法查找指的是：程序运行时，根据对象的动态类型决定实际执行哪个方法。具体来说，如果 VengefulSLList 重写了 SLList 中的某个方法，那么运行时调用哪一个版本，取决于变量所引用对象的运行时类型，也就是动态类型。

练习 4.2.4。 对下面代码中的每一行，判断：

该行是否导致编译错误？
哪些方法调用使用了动态方法选择？

逐行分析这个程序：

VengefulSLList<Integer> vsl = new VengefulSLList<Integer>(9);
SLList<Integer> sl = vsl;

这两行都可以正常编译。由于 VengefulSLList 是一种 SLList，所以可以把 VengefulSLList 实例放进静态类型为 SLList 的变量中。

sl.addLast(50);
sl.removeLast();

这两行也能编译。VengefulSLList 没有重写 addLast，所以调用的是 SLList 中的方法。removeLast 则被 VengefulSLList 重写了；sl 的动态类型是 VengefulSLList，因此动态方法选择会调用 VengefulSLList 中的重写版本。

sl.printLostItems();

这一行会产生编译错误。编译器根据对象的静态类型判断某个操作是否合法。sl 的静态类型是 SLList，而 SLList 中没有定义 printLostItems，所以即使 sl 在运行时确实指向一个 VengefulSLList，编译器也不允许调用该方法。

VengefulSLList<Integer> vsl2 = sl;

这一行同样会产生编译错误。编译器只看到 sl 的静态类型是 SLList，而并非每一个 SLList 都一定是 VengefulSLList，因此不能直接把它装进静态类型为 VengefulSLList 的变量。

表达式的静态类型¶

和变量一样，使用 new 得到的表达式也有编译期类型。

SLList<Integer> sl = new VengefulSLList<Integer>();

右侧表达式的编译期类型是 VengefulSLList。编译器检查到 VengefulSLList 是一种 SLList，因此允许赋值。

VengefulSLList<Integer> vsl = new SLList<Integer>();

右侧表达式的编译期类型是 SLList。编译器检查 SLList 是否一定是一种 VengefulSLList，答案是否定的，因此产生编译错误。

方法调用表达式的编译期类型，等于该方法声明的返回类型。假设有：

public static Dog maxDog(Dog d1, Dog d2) { ... }

由于 maxDog 的返回类型声明为 Dog，所以任何对 maxDog 的调用表达式，其编译期类型都是 Dog。

Poodle frank = new Poodle("Frank", 5);
Poodle frankJr = new Poodle("Frank Jr.", 15);

Dog largerDog = maxDog(frank, frankJr);
Poodle largerPoodle = maxDog(frank, frankJr); // 无法编译：右侧编译期类型是 Dog

把 Dog 类型的表达式赋给 Poodle 变量会产生编译错误。Poodle 是一种 Dog，但一般的 Dog 不一定是 Poodle。即使我们作为读者清楚地知道 frank 与 frankJr 都是 Poodle，编译器仍然只按照方法签名判断。

强制类型转换¶

Java 提供了一种特殊语法，让程序员告诉编译器：应把某个表达式视为特定的编译期类型。这称为类型转换（casting），通常也叫强制类型转换。

回到前面的失败代码。因为我们知道 frank 和 frankJr 都是 Poodle，可以写：

Poodle largerPoodle = (Poodle) maxDog(frank, frankJr);

转换后，右侧表达式的编译期类型变为 Poodle，因此代码可以通过编译。

警告： 强制类型转换功能强大，但也很危险。它本质上是在告诉编译器：“暂时不要履行完整的类型检查职责，请相信我。”例如：

Poodle frank = new Poodle("Frank", 5);
Malamute frankSr = new Malamute("Frank Sr.", 100);

Poodle largerPoodle = (Poodle) maxDog(frank, frankSr); // 运行时异常

这里比较的是一只 Poodle 和一只 Malamute。如果没有强制转换，编译器不会允许把返回类型为 Dog 的表达式直接赋给 Poodle。强制转换让代码通过编译，但如果 maxDog 在运行时返回的是 Malamute，程序就会尝试把 Malamute 当成 Poodle，最终抛出 ClassCastException。

高阶函数¶

下面稍微偏离主线，介绍高阶函数。高阶函数是把其他函数当作数据处理的函数。例如，下面的 Python 程序中，do_twice 接收另一个函数作为输入，并把它连续应用到 x 两次：

def tenX(x):
    return 10*x

def do_twice(f, x):
    return f(f(x))

调用 print(do_twice(tenX, 2)) 时，程序先把 tenX 应用于 2，得到 20；再把 tenX 应用于 20，最终得到 200。那么，在 Java 中怎样实现类似行为呢？

在旧版 Java（Java 7 及更早版本）中，变量不能直接保存函数指针。也就是说，我们不能简单声明一个“函数类型”的变量，因为语言中没有直接对应的函数类型。

为了解决这个问题，可以利用接口继承。先定义一个接口，表示所有“接收一个整数并返回一个整数”的函数，称为 IntUnaryFunction：

public interface IntUnaryFunction {
    int apply(int x);
}

然后编写一个实现该接口的类，表示具体函数。下面的函数把输入整数乘以 10：

public class TenX implements IntUnaryFunction {
    /* Returns ten times the argument. */
    public int apply(int x) {
        return 10 * x;
    }
}

到这里，我们已经用 Java 表示出了 Python 中的 tenX。接着实现 do_twice：

public static int do_twice(IntUnaryFunction f, int x) {
    return f.apply(f.apply(x));
}

Java 中对应的调用写作：

System.out.println(do_twice(new TenX(), 2));

继承速查表¶

VengefulSLList extends SLList 表示：VengefulSLList 是一种 SLList，并继承 SLList 的成员：

变量；
方法；
嵌套类；
不包括构造方法。

子类构造方法必须先调用超类构造方法。super 关键字可以用于调用超类构造方法，也可以调用被子类重写的超类方法。

重写方法的调用遵循两条核心规则：

编译器采取保守策略，只根据表达式的静态类型允许操作；
对于被重写的方法（不是重载方法），运行时实际调用哪个版本，由调用表达式所引用对象的动态类型决定；
可以通过强制类型转换覆盖编译器的静态类型判断，但错误的转换可能导致运行时异常。

4.3 子类型多态与高阶函数¶

子类型多态¶

我们已经看到，继承使我们能够复用超类中的现有代码，同时通过重写超类方法或在子类中编写新方法，实现少量修改。继承还使我们能够利用多态设计通用的数据结构和方法。

“多态”的字面含义是“多种形态”。在 Java 中，多态指一个对象可以具有多种身份或类型。在面向对象编程中，一个对象既可以被看作自身类的实例，也可以被看作其超类、超类的超类等类型的实例。

假设变量 deque 的静态类型是 Deque。调用 deque.addFirst() 时，真正执行的方法会在运行时确定，取决于调用时 deque 所引用对象的运行时类型，也就是动态类型。上一节已经介绍过，Java 使用动态方法选择决定调用哪个被重写的方法。

假设我们想写一个 Python 程序，输出两个对象中较大者的字符串表示。可以采用两种方式。

显式高阶函数方式：

def print_larger(x, y, compare, stringify):
    if compare(x, y):
        return stringify(x)
    return stringify(y)

子类型多态方式：

def print_larger(x, y):
    if x.largerThan(y):
        return x.str()
    return y.str()

在显式高阶函数方案中，我们把比较函数和字符串转换函数明确传入，从而以统一方式输出较大对象。相较之下，在子类型多态方案中，由对象自身决定应该怎样比较和转换。实际调用的 largerThan 实现取决于 x 和 y 究竟是什么对象。

通用 `max` 函数¶

假设我们希望编写一个 max 函数：它接收任意类型的数组，并返回数组中的最大元素。

练习 4.3.1。 判断下面代码中有多少处编译错误。

public static Object max(Object[] items) {
    int maxDex = 0;
    for (int i = 0; i < items.length; i += 1) {
        if (items[i] > items[maxDex]) {
            maxDex = i;
        }
    }
    return items[maxDex];
}

public static void main(String[] args) {
    Dog[] dogs = {new Dog("Elyse", 3), new Dog("Sture", 9), new Dog("Benjamin", 15)};
    Dog maxDog = (Dog) max(dogs);
    maxDog.bark();
}

上面的代码只有一处错误：

if (items[i] > items[maxDex]) {

它会产生编译错误，因为这行代码假设 > 运算符可以用于任意 Object，而事实并非如此。

一种退让方案是在 Dog 类中定义专门的 maxDog，放弃编写一个能够接收任意类型数组的“唯一通用最大值函数”。例如：

public static Dog maxDog(Dog[] dogs) {
    if (dogs == null || dogs.length == 0) {
        return null;
    }
    Dog maxDog = dogs[0];
    for (Dog d : dogs) {
        if (d.size > maxDog.size) {
            maxDog = d;
        }
    }
    return maxDog;
}

这段代码眼下可以工作，但如果我们放弃通用 max，让每个类自行定义最大值方法，以后每增加一种类，就要重复编写 maxCat、maxPenguin、maxWhale 等方法。这会产生大量重复劳动和冗余代码。

根本问题是：Object 之间不能直接使用 > 比较。这很合理，因为 Java 无法知道你究竟想按对象的字符串表示、大小，还是其他指标比较。在 Python 或 C++ 中，可以为不同类型重新定义 > 的含义；Java 不允许直接重载运算符，因此我们要借助接口继承。

可以创建一个接口，保证所有实现类（例如 Dog）都提供一个比较方法，我们称之为 compareTo。

先定义接口：

public interface OurComparable {
    public int compareTo(Object o);
}

规定 compareTo 的行为：

如果 this < o，返回 -1；
如果 this 与 o 相等，返回 0；
如果 this > o，返回 1。

创建 OurComparable 后，我们可以要求 Dog 实现 compareTo。先在 Dog 的类声明中加入 implements OurComparable，再按照上述约定实现方法。

练习 4.3.2。 为 Dog 类实现 compareTo。

下面使用实例变量 size 进行比较：

public class Dog implements OurComparable {
    private String name;
    private int size;

    public Dog(String n, int s) {
        name = n;
        size = s;
    }

    public void bark() {
        System.out.println(name + " says: bark");
    }

    public int compareTo(Object o) {
        Dog uddaDog = (Dog) o;
        if (this.size < uddaDog.size) {
            return -1;
        } else if (this.size == uddaDog.size) {
            return 0;
        }
        return 1;
    }
}

注意：由于 compareTo 接收的是任意 Object o，为了访问 size 实例变量，我们必须先把输入强制转换为 Dog。

现在可以把练习 4.3.1 中的 max 泛化。它不再接收任意 Object 数组，而是接收 OurComparable 数组；我们可以确定，这些对象都实现了 compareTo。

public static OurComparable max(OurComparable[] items) {
    int maxDex = 0;
    for (int i = 0; i < items.length; i += 1) {
        int cmp = items[i].compareTo(items[maxDex]);
        if (cmp > 0) {
            maxDex = i;
        }
    }
    return items[maxDex];
}

很好。现在 max 可以接收任意 OurComparable 类型的对象数组，并返回其中的最大对象。不过，前面的 compareTo 实现略显冗长。可以把约定修改为：

如果 this < o，返回负数；
如果两者相等，返回 0；
如果 this > o，返回正数。

于是可以直接返回大小之差。若当前对象大小为 2，另一个对象大小为 5，compareTo 返回 -3；负数就表示当前对象更小。

public int compareTo(Object o) {
    Dog uddaDog = (Dog) o;
    return this.size - uddaDog.size;
}

借助继承，我们成功泛化了求最大值的函数。这种方案的优点包括：

不必在每个类中重复编写最大值代码，例如无需 Dog.maxDog(Dog[])；
同一段代码可以较为优雅地处理多种类型。

接口小测验¶

练习 4.3.3。 已知 Dog 类、DogLauncher 类、OurComparable 接口和 Maximizer 类。如果从 Dog 中删去 compareTo()，哪个文件无法编译？

public class DogLauncher {
    public static void main(String[] args) {
        ...
        Dog[] dogs = new Dog[]{d1, d2, d3};
        System.out.println(Maximizer.max(dogs));
    }
}

public class Dog implements OurComparable {
    ...
    public int compareTo(Object o) {
        Dog uddaDog = (Dog) o;
        if (this.size < uddaDog.size) {
            return -1;
        } else if (this.size == uddaDog.size) {
            return 0;
        }
        return 1;
    }
    ...
}

public class Maximizer {
    public static OurComparable max(OurComparable[] items) {
        ...
        int cmp = items[i].compareTo(items[maxDex]);
        ...
    }
}

这种情况下，Dog 类会编译失败。声明 implements OurComparable 就等于声称 Dog 是一种 OurComparable。编译器会检查这个承诺是否成立，并发现 Dog 没有实现必需的 compareTo。

如果改为从 Dog 类声明中删去 implements OurComparable，那么编译错误会出现在 DogLauncher 的这一行：

System.out.println(Maximizer.max(dogs));

如果 Dog 没有实现 OurComparable，编译器就不会允许把 Dog[] 传给 Maximizer.max，因为 max 只接受 OurComparable[]。

`Comparable`¶

我们刚刚设计的 OurComparable 可以工作，但并不完美：

在 Object 与具体类型之间强制转换很别扭；
这是我们自己发明的接口：
现有类（例如 String）不会实现它；
现有库也不会使用它，例如没有内置的 max 专门接收 OurComparable。

解决办法是使用 Java 已经提供的 Comparable 接口。Comparable 被 Java 标准库和大量第三方库广泛使用。

Comparable 与 OurComparable 很相似，但有一个关键差异：

Comparable<T> 带有泛型参数。这样可以避免先接收 Object，再把它强制转换为具体类型。我们把 Dog 改为实现 Comparable<Dog>：

public class Dog implements Comparable<Dog> {
    ...
    public int compareTo(Dog uddaDog) {
        return this.size - uddaDog.size;
    }
}

接下来，只需把 Maximizer 中的 OurComparable 全部改为 Comparable。此时，最大的狗就可以发出叫声了。

我们不再使用自创接口，而是使用真正的内置接口 Comparable。这样便可以直接利用所有已经围绕 Comparable 构建好的库。

`Comparator`¶

刚刚介绍的 Comparable 接口，把“与另一只狗比较”的能力嵌入每个 Dog 对象中。接下来介绍一个非常相似的接口：Comparator。

先定义一个术语：

自然顺序（natural order）：某个类的 compareTo 方法所规定的默认排序方式。

在前面的例子中，我们按 size 定义了狗的自然顺序。但如果希望使用其他方式排序，例如按名字的字母顺序，该怎么办？

Java 的做法是使用 Comparator。比较器本身是一个对象。我们可以在 Dog 内部编写一个实现 Comparator 的嵌套类。

Comparator 接口大致如下：

public interface Comparator<T> {
    int compare(T o1, T o2);
}

任何实现 Comparator 的类都必须实现 compare。它的约定与 compareTo 一样：

如果 o1 < o2，返回负数；
如果二者相等，返回 0；
如果 o1 > o2，返回正数。

下面给 Dog 添加一个 NameComparator。可以直接复用 String 已经定义好的 compareTo：

import java.util.Comparator;

public class Dog implements Comparable<Dog> {
    ...
    public int compareTo(Dog uddaDog) {
        return this.size - uddaDog.size;
    }

    private static class NameComparator implements Comparator<Dog> {
        public int compare(Dog a, Dog b) {
            return a.name.compareTo(b.name);
        }
    }

    public static Comparator<Dog> getNameComparator() {
        return new NameComparator();
    }
}

我们把 NameComparator 声明为静态嵌套类，因为获取一个名字比较器并不需要先实例化某只 Dog。

可以这样获得比较器：

Comparator<Dog> nc = Dog.getNameComparator();

最终，Dog 类内部拥有一个私有的 NameComparator 类，并提供一个返回该比较器的方法。调用者可以使用它按名字的字母顺序比较狗。

从继承层次看，Java 内置了 Comparator 接口；我们可以在 Dog 中实现多种自己的比较器，例如 NameComparator、SizeComparator 等。

总结来说，Java 接口使我们能够实现回调。有时，一个函数需要另一个尚未编写的函数提供帮助，例如 max 需要 compareTo。这个辅助函数就是回调函数。在一些语言中，可以直接把函数作为参数传递；在 Java 中，我们可以把所需函数包装在一个接口实现对象中。

Comparable 表达的是：“我能够把自己与另一个同类型对象比较。”它嵌入对象自身，并定义该类型的自然顺序。Comparator 则更像一个独立的第三方机器，负责比较两个对象。一个类只能有一种 compareTo 自然顺序；如果需要多种比较方式，就应使用多个 Comparator。

4.4 Java 库与包¶

抽象数据类型（ADT）¶

虽然此前没有一直明确使用这个名称，但我们实际上已经见过若干抽象数据类型，例如 List61B 和 Deque。这里重点观察 Deque。

Deque

我们有一个 Deque 接口，ArrayDeque 和 LinkedListDeque 都实现了它。Deque 与这些实现类之间是什么关系？Deque 只提供了一组方法，也就是行为：

public void addFirst(T item);
public void addLast(T item);
public boolean isEmpty();
public int size();
public void printDeque();
public T removeFirst();
public T removeLast();
public T get(int index);

这些方法的具体代码由 ArrayDeque 和 LinkedListDeque 提供。

在 Java 语法中，Deque 是一个接口；从概念上说，它是一种抽象数据类型（Abstract Data Type，ADT）。Deque 只规定应具备哪些行为，却没有规定实现这些行为的具体方式，因此它是“抽象”的。

Java 标准库¶

Java 内置了很多可直接使用的抽象数据类型，它们被组织在 Java 标准库中。

java.util 中最重要的三类 ADT 是：

List：有顺序的元素集合；
常用实现是 ArrayList。
Set：无顺序且元素严格唯一的集合，不允许重复；
常用实现是 HashSet。
Map：键值对集合，通过键访问对应的值；
常用实现是 HashMap。

请使用这三种 ADT 完成下面练习。阅读上面链接的 API 文档会非常有帮助。

练习 4.4.1。 编写 getWords，接收 String inputFileName，把输入文件中的每个单词放入一个列表。回忆项目 0 中读取文件单词的方法。提示：使用 In。

练习 4.4.2。 编写 countUniqueWords，接收一个 List<String>，计算文件中有多少个不同的单词。

第一个练习使用列表，第二个练习使用集合：

public static List<String> getWords(String inputFileName) {
    List<String> lst = new ArrayList<String>();
    In in = new In();
    while (!in.isEmpty()) {
        lst.add(in.readString()); // 也可以先定义 cleanString() 清理字符串
    }
    return lst;
}

public static int countUniqueWords(List<String> words) {
    Set<String> ss = new HashSet<>();
    for (String s : words) {
        ss.add(s);
    }
    return ss.size();
}

练习 4.4.3。 编写 collectWordCount，接收 List<String> targets 和 List<String> words，找出每个目标单词在单词列表中出现的次数。

public static Map<String, Integer> collectWordCount(List<String> words) {
    Map<String, Integer> counts = new HashMap<String, Integer>();
    for (String t : target) {
        counts.put(s, 0);
    }
    for (String s : words) {
        if (counts.containsKey(s)) {
            counts.put(word, counts.get(s) + 1);
        }
    }
    return counts;
}

这里使用 Map，因为它能够建立两个对象之间的对应关系。在本例中，我们需要把“单词”与“出现次数”关联起来。

这三种 ADT 都继承自 Collection 接口。Collection 的定义非常宽泛：Java 文档说，集合“表示一组被称为元素的对象”。

集合层次

上图中，白色方框表示接口，蓝色方框表示具体类。

Java 与 Python¶

Java 的语法相当冗长。下面的 Java 代码看起来比对应的 Python 代码笨重得多。

Java 示例

Python 示例

不过，Java 也有自己的优势：它提供了更多选择和工程控制。例如，Python 通常只有一种主要的字典类型，使用 {} 创建；在 Java 中，如果要使用 Map 这种 ADT，可以根据需求选择不同实现，例如 HashMap、TreeMap 等。

CS61B 选择 Java，主要有以下原因。

从整个开发过程看，编写程序可能反而更省时间，原因包括：
静态类型提供类型检查，并引导程序员正确使用代码；
偏向接口继承，使子类型多态更清晰；
访问控制修饰符能建立更牢固的抽象屏障。
代码通常更加高效，原因包括：
程序员可以更精细地控制工程权衡；
数组中的元素类型统一，有利于性能。
基础数据结构更接近底层硬件：
在 Python 中亲手实现 ArrayDeque 会显得奇怪，因为语言已经隐藏了数组扩容；但真实硬件中并不存在可以自动改变长度的数组，这一点会在 CS61C 中进一步学习。

抽象类¶

接口能够完成很多工作，它既支持接口继承，也可以通过 default 方法提供实现继承。先回顾接口的特点：

所有方法都必须是公开的；
所有变量都必须是 public static final；
接口不能被实例化；
除非声明为 default，否则方法默认是抽象的；
一个类可以实现多个接口。

接下来介绍介于接口和具体类之间的结构：抽象类。抽象类具有以下特点：

方法可以是 public 或 private；
可以拥有任意类型的变量；
不能被实例化；
方法默认有具体实现，除非显式声明为 abstract；
一个类只能继承一个抽象类。

从能力上看，抽象类可以完成接口能做的事，并且还能做更多。

但当你拿不准时，优先尝试接口，这样通常更有利于控制复杂性。

包¶

包名为程序中的对象提供规范名称（canonical name）。“规范”意味着某个对象拥有唯一、明确的表示。

为什么需要包名？Java 中可以存在多个同名类，我们必须区分它们。在工业项目里，常用做法是把组织的网站域名反向书写，再接上类所在的层次。例如，一个类的完整名称可能是：

ug.joshh.animal.Dog

但这意味着每次实例化时都要输入完整名称：

ug.joshh.animal.Dog d = new ug.joshh.animal.Dog();

这非常麻烦。可以通过导入包来解决：

import ug.joshh.animal.Dog;

导入后，就可以直接使用简短的类名 Dog。

这里只是对包的简要预览，课程后续还会继续讨论。

第 4 章 继承与接口¶

4.1 导论与接口¶

问题¶

上位词、下位词与接口继承¶

重写¶

接口继承¶

等号黄金法则（GRoE）¶

实现继承¶

接口继承与实现继承¶

4.2 extends、类型转换与高阶函数¶

extends¶

VengefulSLList¶

构造方法不会被继承¶

Object 类¶

“是一种”与“拥有一个”¶

封装¶

抽象屏障¶

继承怎样破坏封装¶

类型检查与类型转换¶

表达式的静态类型¶

强制类型转换¶

高阶函数¶

继承速查表¶

4.3 子类型多态与高阶函数¶

子类型多态¶

通用 max 函数¶

接口小测验¶

Comparable¶

Comparator¶

4.4 Java 库与包¶

抽象数据类型（ADT）¶

Java 标准库¶

Java 与 Python¶

抽象类¶

包¶

第 4 章继承与接口¶

4.2 `extends`、类型转换与高阶函数¶

`extends`¶

`VengefulSLList`¶

`Object` 类¶

通用 `max` 函数¶

`Comparable`¶

`Comparator`¶