CS61b part6

8.6 Implementation Inheritance and Default Method

让我们谈谈另一种类型的继承，这种继承与之前的关系紧密但精神上却非常不同，这种新的继承类型称为实现继承。我们之前看到的是接口继承，在这种方法中，子类获得了方法的签名，但没有任何实际的代码。所以，如果我们查看`List61b`接口，我们有签名但没有代码，那里有一个分号。现在，Java允许你做一种叫做实现继承的事情，你可以在接口中提供代码，这些子类将继承这些代码。我们展示这一点的方式是，我将向你展示如何为`List61b`编写一个打印方法，这将允许你打印任何列表，我们使用的关键字叫做`default`，我们需要使用它来在接口中添加代码。

Interface inheritance:

Subclass inherits signatures, but NOT implementation.

For better or worse, Java also allows implementation inheritance.

Subclasses can inherit signatures AND implementation.

Use the default keyword to specify a method that subclasses should inherit from an interface.

Example: Let's add a default print() method to List61B.java

为了举例说明为什么我们需要`default`关键字，首先假设我们试图像你天真地那样定义一个`print`方法，好吧，我要说打印出整个列表，然后我们尝试编写一些代码，但如果你仔细看，这里会提示“接口方法不能有主体”，如果没有`default`关键字的话，我不能这样做。所以现在我们可以编写一个`print`方法，尽管这可能看起来有点奇怪，比如`List61b`，我们不知道这是一个`ArrayList`还是一个链表，事实上我们没有任何实例变量，所以编写一个打印方法似乎有点棘手，但是我们有所有这些方法可以利用，因为任何实现这个接口的类也必须实现这些方法，这是必需的。在这种情况下，我们可以简单地使用例如我们的`size`和`get`方法，我们可以这样做：对于`i = 0; i < size(); i++`，这里的`size`是指实现类中编写的方法，现在我们可以通过`get(i)`打印出项目，为了美观原因，我会添加一个空格，最后为了美观原因，我们还会添加一个换行符，现在如果我们进入演示并运行它，我们会得到列表的打印输出，即使`SList`类本身没有指定打印方法，所以如果我按Ctrl+F搜索`print`，这里没有定义的打印方法，就是这样，这是我们将在下一个视频中要做的事情，所以这个打印方法，为了说服你真的是`List61b`类在执行打印，如果我们使用调试器并运行到这一行，然后单步执行，我们会看到我们现在正在运行接口内部的代码，这对Java来说其实是一个相当新的特性，在Java 8发布之前是不可能的，Java 8发布于大约2015年或2016年，所以这是一个相对新的Java特性，有点争议，但要知道它存在，虽然我可能会时不时抱怨实现继承的问题，这里是刚刚编写的方法，主要的区别是所有这些其他方法你只继承它们的签名，这是接口继承，而这是实现继承，因为我们得到了实现。

事实上包含这几个文件

SLList.java
DMSDemo.java
List61B.java
IsADemo.java
AList.java
WordUtils.java

我有一个谜题给你，以激励我们的下一个视频，那就是你认为`print`方法对`ArrayList`和`SList`都高效吗？还是只对其中一个高效，或者实际上对两者都不高效？乍一看，这段代码看起来效率很高，它只是遍历每个项目并打印出来，但仔细想想`size`和`get`方法在`ArrayList`和`SList`中会是什么样的，我会在这里停顿一下，让你思考一下。结果证明，虽然`size`方法对这两个类来说都非常快，但从`SList`的中间获取项目会很慢，所以我们预计它对`ArrayList`是高效的，而对`SList`则是低效的，仅仅是因为`ArrayList`的`get`方法非常快，只需从数组中获取第八个元素，而`SList`实际上必须遍历整个列表才能到达索引`i`，所以我们将以一种非常低效的方式像常数一样扫描整个列表，如果我们查看`SList`，比如查看`get`方法，我们可以看到实际上涉及到循环遍历数组，如果我们必须一遍又一遍地循环遍历数组，这将会非常慢，所以在某种程度上，这实际上是一个双重嵌套的`for`循环。那么我们如何处理这个问题呢？我们将在下一个视频中讨论这个问题。

8.7 Overriding Default Methods

存在于`List61B`中的`print`方法意味着我们不需要为`SList`单独编写这个方法，但我们可以看到这种方法相当低效。那么我们能做些什么呢？一种方法是覆盖“老板”的决定。当然，作为子类，我们已经讨论过覆写是可能的，事实证明在这种情况下，我们实际上可以在`SList`中编写一个`print`方法，即使它已经在`List61B`中实现了。在这种情况下，我们真的在覆盖“老板”的设定，忽略“老板”的做法，按照我们自己的方式来做，因为我们信任自己。所以我要在这里加上`@Override`注解，然后说`public void print`，现在我要想一想如何以更高效的方式打印，而不是一遍又一遍地获取项目。实际上，更有意义的做法是逐个遍历列表项并打印。所以我们可以这样做，比如说`for (Node p = sentinel.next; p != null; p = p.next)`，这里的思路是我会一直遍历到指针碰到`null`，每次循环结束时向前移动一个节点，然后我会写`System.out.print(p.item + " ")`，这里有一个小小的错误，我们实际上不想打印哨兵节点的项，而是从`sentinel.next`开始，但这段代码应该可以工作。所以如果我进入演示，我将通过说“老板不知道他在做什么”来证明它在工作，这样我们就能知道这实际上是在运行。然后当我进入演示并再次运行这段代码时，老板不知道他在做什么，鹿陷入存在危机。所以在这种情况下，我们实际上使用了这个`print`方法，我们知道它更高效，因为它只会使用每个节点一次，而不是反复迭代。

展示SLList.java的修改的末尾部分

.........
.........public void insert(Blorp item, int position){if (sentinel.next = null | position = 0){addFirst(item);return;}Node currentNode = sentinel.next.next;while (position > 1 && currentNode. next ！= null){position -= 1；currentNode = currentNode. next;}Node newNode = new Node(item, currentNode.next);currentNode. next = newNode;}
/** TODO: Add a print method that overrides List61B's inefficient print method. */
//@Override
public void print() {System.out.println("The boss doesn't know what he's doing!");for (Node p = sentinel.next; p ！= null; p = p.next){System.out.print(p.item +"")；}
}

关于覆写的一个问题是，它非常方便。让我们想象一下，如果没有加上`@Override`注解，而是误打了`prnt`，这段代码仍然会编译，因为拥有一个`print`方法是没问题的，没有人会说不行。但现在当我们调用演示并运行代码时，实际上会使用`List61B`中的`print`方法。这里的错误是我们没有加`i`，如果我们加上了`@Override`标签，我们会得到一个提示，说“呃，这不是一个覆写”，我们会意识到“哦，我明白了，拼错了单词”。所以这是一个很好的功能。这是我们新的更好的`print`方法，如果你希望事情按你的意图工作，你总是可以覆写它。这里有一个我想让你简短思考的问题，回忆一下，如果X是Y的超类，那么一个X变量可以保存一个Y的引用。换句话说，以英语为例，如果你有一个`List61B`变量，它可以保存一个`SList`的地址。在我们一直在运行的示例中，我们设置`SList`等于`new SList()`，

现在的问题是，如果我们把这个改为`List61B`，这会工作吗？我们知道它会编译，因为之前已经知道了，但问题是，你认为它会调用哪个`print`方法？所以请思考一下你的想法。事实证明，它实际上会使用你希望的那个，即`SList`中的`print`方法。事实上，让我们试一试，我们运行它，我们得到“老板不知道他在做什么，鹿陷入存在危机”，这很好，这是合乎逻辑的选择，问题是它是如何工作的。所以这是一个稍微复杂的话题，我会在下一个视频中继续讲解，但它实际上比你想象的要简单得多。通常人们在第一次接触Java时会感到困惑，不知道什么时候会调用哪个方法，但我们会详细解释这一点。

8.8Dynamic Method Solution

理解这一点是如何工作的非常重要，不幸的是，这是一件很容易学会一套过于复杂的拜占庭式规则的事情，但实际上有一种简单的方式来思考它。所以，思考这个问题的方式是，Java中的每一个变量在声明时都有一个编译时类型，我有时也称其为静态类型，这个类型永远不会改变。例如，当我声明`LivingThing lt1`时，我得到了一个内存盒，这个内存盒是64位的，它只能指向一个`LivingThing`。

每个变量还有一个动态类型，有时称为运行时类型，这是在实例化时指定的类型，也就是说，当你使用`new`关键字时，它等于被指向的对象的类型，这就是我们所说的运行时类型。所以在这一点上，我还没有实例化任何东西，所以动态类型将只是标注为`null`。

接下来是这一行代码，我们创建了一个新的狐狸对象，并说`lt1`等于这个新狐狸对象，所以一个新的狐狸对象被创建了，我们复制了它的地址，`lt1`指向了这个生物，现在我们有了一个动态类型，它是狐狸，即被指向的对象的类型。

我们继续，下一行代码是`Animal a1 = lt1`，在这种情况下，我们得到了一个新的内存盒，它保存动物的引用，它的静态类型是动物，而且永远不会改变，事实上，你可以看到它就像刻在盒子上一样，无法去除，它的动态类型是狐狸。我们也可以有静态类型为狐狸的变量，这是完全可以的。所以我创建一个静态类型为狐狸的变量，它也指向一只狐狸，在这种情况下，静态类型和动态类型都是狐狸。

最后，我们决定`lt1`现在将指向一个新的对象，这是一个乌贼对象，所以静态类型当然不会改变，因为它永远不会改变，但动态类型现在变成了乌贼。好的，很棒。

那么，这是规则部分。如果你知道某个对象的动态类型，那么你就知道在调用覆写方法时会发生什么。假设我们使用一个编译时类型为X、运行时类型为Y的变量来调用一个对象的方法，例如，编译时类型为`List`，运行时类型为`SList`，如这里所示，那么如果动态类型覆写了该方法，则将使用动态类型的该方法，这就是所谓的动态方法选择。这个术语有点晦涩，也不是完全标准的，但我们在课程中使用它。所以，在这种情况下，无论何时我们调用某个方法，即使我们使用的是编译时类型为`List`的变量`s1`，由于`SList`类覆写了该方法，我们将使用动态类型的该方法。这就是你看到的现象，即使变量的编译时类型是`List`，实际调用的却是`SList`中的方法。

8.9 Dynamic Method solution and overloaded Solution

正如我在上一个视频中提到的，确定在动态方法选择情况下调用什么方法的规则实际上非常简单。然而，我们的直觉有时会误导我们，我们会寻找模式或假设Java语言会做一些看起来比简单规则更合理的事情。好，我这里有一个例子，它展示了我刚开始学习Java时犯的一个错误，你们也很有可能犯同样的错误。所以，你们的任务是弄清楚这段代码运行的结果是什么。让我来介绍一下这个问题的背景，我们有一个名为`Animal`的接口，它提供了`greet`、`sniff`和`flatter`方法，所有这些都是默认方法。我在这里有点作弊，去掉了`System.out`，因为我想让所有内容都能放在一张幻灯片上，但我认为概念仍然是清晰的。然后，我这里有一个名为`Dog`的类，它实现了`Animal`接口，并提供了`sniff`和`flatterDog`方法。你们的任务是弄清楚当我运行这段代码时会发生什么。

我有两个变量，一个是`Animal a`，另一个是`Dog d`，所以它们的静态类型分别是`Animal`和`Dog`。现在它们都被设置为一个新的`Dog`对象，因此`a`和`d`所指向的对象的动态类型都是`Dog`。然后我们有一系列的方法调用，其中三个使用了静态类型为`Animal`的变量`a`，一个使用了静态类型为`Dog`的变量`d`。现在，请思考一下你认为每行代码会做什么，这是一个非常重要的谜题，所以如果你在家里观看，请务必尝试得出答案并认真思考，然后将你的答案与我的进行比较，希望你会犯我希望你犯的错误，或者更好，根本不犯错误，我们来看看。

首先，我们来看`a.greet(d)`，这里我们有一个类型为`Animal`的变量，所以我们查找是否有可以接受类型为`Dog`的参数的`greet`方法，答案实际上是有的，因为`Dog`是`Animal`的一种，所以它可以放入这个`Animal`类型的参数中，没问题。所以当这行代码运行时，我们得到的是“Hello Animal”。

接下来是`a.sniff(d)`，那么这里会发生什么呢？Java会说有没有可以处理`Dog`的方法，有的，就是`sniff(Animal a)`。因为`Dog`是`Animal`的一种，所以你可以调用这个方法。但由于动态方法选择的魔法，`Dog`也提供了一个`sniff(Animal a)`方法，这是对原始`sniff`方法的覆写，所以我们会得到`Dog`的`sniff`方法，即使这里没有`@Override`注解，这也是可选的，但在61B课程中你应该总是加上`@Override`注解。

现在，我们试着让一条狗恭维另一条狗，`d.flatterDog(d)`会发生什么？Java会说嘿，`Dog`，你有没有可以恭维狗的方法？有的，好的，在这种情况下，`d.flatterDog(d)`会调用这个方法，我们会得到“你真酷，狗”。

最后，我们来看`a.flatter(d)`，在这种情况下，Java会说`Animal`，你有没有一个可以处理狗的`flatter`方法？有的，好的，这里有。有些人可能会想，好吧，`Dog`有一个更好的方法，所以应该是“你真酷，狗”，因为这个方法更具体。但实际上正确答案是“你真酷，动物”。所以，对于那些犯了这个特定错误的人，即使是最近我和我的助教讨论类似的问题时，他们也会问“什么？” 这是一个非常容易犯的错误，除非你仔细思考，这看起来可能有些吓人，但答案其实很简单。

答案是，如果我们查看`flatter(Animal)`和`flatter(Dog)`，它们的签名并不相同。我们定义覆写的方法是必须具有完全相同的签名，而这些签名并不相同，`Animal`和`Dog`不是同一个类型。所以这是一个重载的例子，而不是覆写。

另一种思考这个问题的方法是所谓的“方法选择算法”。这只是我思考的一个方法，我也发现这种方法有助于向学生解释这个问题。这听起来可能有点术语化，但我们会把它与刚才的问题联系起来。

Consider the function call foo. bar(x1), where foo has static type TPrime, and x1 has static type T1.
At compi le time, the compiler verifies that TPrime has a method that can handle T1. It then records the signature of this method.

Note: If there are multiple methods that can handle T1, the compiler records the "most specific" one. For example, if T1=Dog, and TPrime has bar(Dog) and bar(Animal), it wil record bar(Dog).

At runtime, if foo's dynamic type overrides the recorded signature, use the overridden method. Otherwise, use TPrime's version of the method.
TO NOTE : We did not see this in our lecture puzzle, but see study guide for more!

让我们考虑一个函数调用，形式如下：`foo.bar(x1)`，其中`foo`是调用变量或表达式，`bar`是方法名，我们传入一个变量`x1`。假设`foo`的静态类型是`T'`，`x1`的静态类型是`T1`。那么在编译时，编译器需要确保一切正常，编译器会验证`T'`是否有一个可以处理`T1`的方法，就像我们问`Animal`是否有可以处理`Dog`的方法一样。找到匹配的方法后，编译器会记录该方法的签名，并将其写在一个地方，比如说是“我们需要调用的方法是一个`Animal`类型的方法，其签名是`flatter(Animal)`”，它会记录下这个签名`flatter(Animal)`。

一个小的侧注，如果实际上有多个方法可以处理`T1`，编译器会选择最具体的一个。在我们的小例子中没有这种情况，但练习指南中有类似的问题。例如，如果类型是`Dog`，而`T'`在这种情况下是`Animal`，并且既有`flatter(Dog)`也有`flatter(Animal)`方法，它会选择`Dog`版本，因为这是更具体的一个。但在这个例子中我们没有这样的方法。

所以，到了运行时，如果`foo`的动态类型（也就是`a`的动态类型，这里是`Dog`）覆写了那个记录的签名（这里是`flatter(Animal)`），那么我们会使用覆写的方法。在这里，`Dog`并没有覆写`flatter(Animal)`，所以结果是，我们最终使用的是`T'`版本的方法。这就是从算法角度来看这个问题的方法。如果你不喜欢这个简短的解释，这里有一个更长的版本，但它们实际上是等价的。

最后，让我们再从视觉上看一次，每当这段代码被编译时，编译器会说：“有没有一个`Animal`类型的方法可以处理`Dog`对象？” 有的，对吧？那么，这个方法叫什么名字？它叫`flatter(Animal)`，所以它会把这个签名记录下来。然后，当代码实际运行时，它必须使用具有该确切签名的方法，因为这就是覆写的意义所在。

希望这对你有所帮助，一定要查看练习指南，学生一开始会觉得这个问题令人沮丧，但一旦你做了正确的练习并培养了正确的直觉，规则实际上是非常简单的。基本上，这归结为：方法选择基于编译时类型，但实际调用的方法取决于运行时类型。

8.10 Is a vs Has a, Interface vs Implementation

为了总结这次讲座，让我们比较一下本讲中看到的继承类型。第一种是接口继承，我喜欢它，它是个伟大的想法，它告诉你可以从子类中期待什么，所以超类或接口会说所有的列表都必须做这些事情，它允许你以一种强大而简单的方式泛化你的代码。如果我们看看`longest`方法的例子，

public static String longest(List61B<String>list){

它适用于任何列表，而不仅仅是现有的列表，而是将来任何时候编写的列表。所以，如果一千年后有人挖出我的代码，像我的骨架躺在某个地方握着一个U盘，他们找到了这个东西，他们会说：“是的，这很好。” 而且他们说：“嗯，我们没有列表实现，除了这个奇怪的队列列表之外，只要它遵守`List61B`接口，不管它是怎么做的，它仍然会工作。” 这很好。

还有另一种实现继承，它告诉你子类应该如何行为，在这种情况下，“老板”告诉下属们具体如何完成他们的工作。这很好，因为“老板”可以提供一个通用的工作`print`方法，任何人都可以使用。所以，如果你创建了一个新的列表叫做队列列表，你不确定如何打印，至少你有这个方法可用。虽然它可能不是最有效的方式，但它在那里，所以它给了你额外的控制层，你可以决定是否覆写它，这可以很好。

在这两种情况下，我想指出一个常见的陷阱，你可能会掉进这个陷阱：无论你使用哪种继承，都应该指定一个“is-a”关系，而不是“has-a”关系。

我是什么意思呢？一个好的“is-a”关系的例子是：狗是一种动物，没错，每只狗都是动物；同样，每个`SList`都是一个`List61B`，这很好，我们通过这种方式指定这些关系。相比之下，如果你读作“has-a”，那就不好了，你不应该在这种情况下使用继承。所以，例如，如果我创建一个名为猫的类，并实现爪子，确实猫有爪子，但猫不是爪子。你可能会说这听起来很奇怪，我为什么要这么做，但这里有一个更好的例子，或许你能明白为什么你可能会被诱惑走向黑暗面。如果我说集合实现了`SList`，我实际上试图使用`SList`来实现一个集合，集合是一个不允许重复元素的对象集合。例如，如果我调用`AB.first("potato")`三次，集合中只会有一个土豆。你可以想象尝试覆写`SList`的方法来捕捉这种行为，不管它是什么，实际上我们会把`SList`扭曲成一个集合，但这不会按你想要的方式工作，最终会变得非常复杂。

所以，使用接口或实现继承来捕捉“has-a”关系的诱惑，请避免这样做。顺便说一句，实际上我还想多谈一点我对实现继承的一些怀疑，以及为什么它可能会给你带来麻烦的原因。

The Dangers of Implementation Inheritance
Particular Dangers of Implementation Inheritance

Makes it harder to keep track of where something was actually implemented(though a good IDE makes this better).
Rules for resolving conflicts can be arcane. Won't cover in 61B.
Example: What if two interfaces both give conflicting default methods?
Encourages overly complex code(especially with novices).
Common mistake: Has-a vs. Is-a!
Breaks encapsulation!
What is encapsulation? See next week.

一个有时适用的问题是，它可能很难跟踪某件事情实际在哪里实现。想象你有一个深达六七层的实现堆栈，比如我有一个动物接口，然后我有食肉动物，然后是哺乳动物，然后是狗等等。潜在地很难跟踪哪些地方被覆写了，哪些地方被定义了等等。一个好的IDE使这几乎不成问题，但也意味着一些额外的复杂性。有时候你可能会遇到奇怪的冲突，想象你有一个服务和服务助手，它们都说有一个助手接口和一个动物接口，然后你想制作一个服务犬类，实现这两个超类或接口中的某些东西。在这种情况下，如果这两个接口之间有冲突，也许它们都有相同的一个默认方法，有一些复杂的规则来解决这些冲突，在Java中通常不是什么大问题，但这是实现继承的一个不太好看的地方。

另一个问题是，它鼓励过于复杂的代码，因为我们有了一把锤子，一切都看起来像钉子。所以，你知道，关于继承的一切，特别是当你刚接触它时，你可能会想要过度使用它。人们最大的错误之一就是“has-a”与“is-a”的问题。实际上，很久以前在我第一次实习时，我也遇到过类似的情况，我当时刚刚学到了某种编译器写作工具，可能是词法分析器之类的东西，你可能从未用过它们，但我有一个任务，我管理得很糟糕，忘记了，好像是为了生成某个程序的随机参数，回想起来这段代码，我是如何用我刚刚学到的工具以一种过于复杂的拜占庭式方式解决问题的。继承，尤其是实现继承，通常导致这种糟糕的行为。但最糟糕的是，它破坏了封装性。我现在不会告诉你这具体是什么，我们会在接下来的几节课中讨论，所以暂时理解我对实现继承有一些哲学上的例外。

我不是说实现继承不好，我的意思是它是一个极好的工具，在某些情况下，它可以节省大量的时间，而且可以非常美好。但与对我来说是明显win的接口继承不同，实现继承可能有点不稳定。好了，这就是这次讲座的内容，下次见。