CS61b part5

8.1 The Desire for Generality

今天我们将会讨论一个全新的主题，称为继承。为了铺垫，让我们考虑在过去几节课中构建的`SList`类和`AList`类。我们看到它们实际上具有完全相同的操作，它们都允许我们添加元素、获取元素、移除元素以及获取大小，如果你完成了网站上提供的讨论工作表，或者如果你在伯克利上课，那么我们还添加了这个插入方法，可以在任意位置插入元素。好了，鉴于这些类，我们现在想要尝试实际使用它们来做点事情，那么我们可能想做什么呢？让我们制造一个小小的假想问题，那就是我们想要构建一个库来帮助其他人处理单词列表，也许我们想要编写一个方法，它接受一个单词列表，找到最长的单词并返回它。

Suppose we're writing a library to manipulate lists of words. Might want to write a function that finds the longest word from a list of

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);
}

Note: This code is very inefficient! 

现在这段代码实际上并不重要，它说了什么不用担心阅读这里的实现，只要相信它能工作就行。当我们查看这段代码并尝试运行它时，这是一个示例，测试了这个库的功能，所以我创建了一个`SList`，放入了单词“elk”、“are”、“watching”，然后我请求最长的单词，点击运行，或者“deer”、“tilts”，然后我得到了“watching”，因为它是最长的单词。下面是WordUtils.java

public class WordUtils {
    /** Returns the length of the longest word. */
    public static String longest(SLList<String> list){//这里的SLList改成AList
        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);
    }

    public static void main(String[] args){
        SLList<String> someList = new SLList<>();
      //AList <String> someList = new AList<>()
        someList.addLast("elk");
        someList.addLast("are");
        someList.addLast("watching");
        System.out.println(longest(someList);//如果是AList就会error
        //someList.print();
    }
}

现在这里有一个小问题，那就是可能有人那里有一个单词列表，他们没有读入`SList`，而是使用了`AList`，所以让我们模拟这个过程，如果我们这样做并查看从`SList`改为`AList`后会发生什么，当然我们得到了一个错误，错误是说我们不能将`AList`传递给这个方法。所以这是一个相当短的小问题，我不希望你考虑我们需要做什么使`AList`工作，我们能对这段代码做些什么改变呢？

在这种情况下，我们不需要做太多改变，特别地，我们只需将`SL`改为`A`，换句话说，我这样做后，现在一切都会正常工作。所以同样的道理，在这种情况下一切都很好。当然，如果有人试图使用我们的库，却不得不不断编辑`AList`和`SList`，这会让人感到厌烦，所以另一个解决方案实际上是直接复制这个方法，让这个版本基于`AList`，这个版本基于`SList`，在这种情况下，即使这两个方法同名也没关系，这段代码仍然可以顺利编译和运行，因为这是你在Java中可以做的事情。所以这个拥有多同名但参数不同或签名不同的方法的想法是可以的，Java会在编译时自动确定调用哪个方法，它会知道运行哪个方法，所以这只是一个重载的概念。现在虽然技术上可行，但这并不是一个好的解决方案，虽然它可以让我们在任一情况下运行代码，但我认为这很糟糕，所以希望你能思考一下为什么它不好，也许列出一个简短的清单，我会用我的清单来剧透一下，所以我讨厌的一些事情是，首先我们的源代码文件当然没有必要那么长，你查看它们时，会发现很多额外的东西，这可能不是什么大事，但它会显得杂乱。另一个是，重复自己在美学上非常糟糕，不仅仅是代码很长，而且非常相似，没有人愿意这样做，这感觉不对。另一个是，有更多的代码需要维护。这是一个有趣的观点，代码不像汽车那样需要维护，它不会生锈，也不需要我们回来修理，因为不知怎么的它发生了变化，这并不是我们在计算机上面临的问题，谢天谢地，但如果有什么发生变化，如果我们意识到“哦，这效率不高”，有人对其中一个进行了更改，那么你也需要对另一个进行更改，或者进行其他数量的小更改，所以你对一个所做的任何更改也必须对另一个进行，这不仅是为了效率原因，还涉及到任何bug修复，所以在大型项目中常见的错误是，某人编写了一个带有某种bug的方法，还有一个非常相似的方法，他们只追踪并修复了其中一个方法中的bug，而另一个方法继续存在，这是一个当你有像这样的重复代码时可能发生非常危险的事情。最后一个我想提到的是，假设我们决定不喜欢`AList`，而是喜欢`DList`，在这种情况下，我们实际上需要在未来某个时候再来写另一个`DList`函数。所以这节课将会关于我们如何优雅地处理这个问题，并利用由此带来的好处。

8.2 Hypernyms and Hyponyms

实际上，在英语中也会出现类似的情况，所以让我们做一个小小的语法课。
想象一下，你有关于如何清洁卷毛狗的指示，所以第一步可能是洗澡前刷你的卷毛狗，第二步使用温水，第三步用平静的声音和你的卷毛狗交谈，第四步使用卷毛狗专用洗发水，第五步彻底冲洗干净，第六步自然风干，第七步好好奖励你的卷毛狗。现在假设你有一只不同的狗，比如说阿拉斯加雪橇犬（Malamute），我们可能会说，好的，那么洗阿拉斯加雪橇犬的指示是一样的：第一步洗澡前刷你的阿拉斯加雪橇犬，第二步使用温水，第三步用平静的声音和你的阿拉斯加雪橇犬交谈，第四步使用阿拉斯加雪橇犬专用洗发水，第五步彻底冲洗干净，第六步自然风干，第七步好好奖励你的阿拉斯加雪橇犬。
这基本上就是我们在`WordUtils`类的非常粗糙版本中所做的，所以我们祖先也面临着同样的问题，他们必须想出既能涵盖这两种生物的词，因此在英语中，这种词被称为上位词（hypernym）。在这个例子中，“狗”就是“卷毛狗”、“阿拉斯加雪橇犬”、“约克夏”、“腊肠狗”等等的上位词，这只是一个有趣的词汇，我们可能听说过同义词（synonym）。
也许还有下位词（hyponym），这个词表示的是相反类型的关联，所以就像“狗”这个词是“卷毛狗”、“腊肠狗”等的上位词一样，“卷毛狗”是“狗”的下位词。我不会测试你这些，但我认为这是一个很好的概念，因为它实际上也会在Java中发挥作用，所以上位词和下位词组成一个层级结构，可以继续向下延伸。

例如，“狗”是一种“犬科动物”（canine），而“犬科动物”是一种“食肉动物”（carnivore），“食肉动物”是一种“动物”（animal），等等。这些都是所谓的“是一种”（is-a）关系，你实际上可以为英语中的每一个名词构建这样的网络。有一个叫做WordNet的项目，这是一个学术项目，他们已经收集了成千上万的名词，并构建了一个巨大的图表，看起来像这样。

8.3 The interface and implements KeyWords

原来Java有能力以一种正式的方式捕捉类之间的这些关系，就像你和我知道`SList`和`AList`都是某种列表一样，有一种方法可以在Java中实际表达这一点。那么我们怎么做呢？这是一个两步的过程，第一部分是定义一个参考类型来表示我们的上位词，所以在这个例子中，对不起，提醒一下什么是参考类型，记得在Java中有八种原始类型：`short`、`long`、`float`等，而参考类型是除此之外的所有东西，因此我们知道我们可以定义新的类型，比如`Planet`、`Body`、`AList`，现在我们要定义一个叫`List61b`的类型，但我们会看到这与通常的做法稍有不同。第二部分，一旦我们设置好这个东西，我们将指定`SList`和`AList`实际上是`List61b`的下位词。

那么，让我们开始讨论如何设置一个上位词。我们要做的是使用一个新的关键字，我们以前没有用过的，叫做`interface`，这将代替`class`。换句话说，之前我们总是说`public class Lists61b`，现在我们只需要说`interface`代替`class`。为什么是`interface`呢？它会有一些与你应该在`class`中做的事情略有不同的地方，我们稍后会看到这些不同。主要的想法是，接口是一个列表可以做什么的规范，而不是如何去做。那么列表可以做什么呢？例如，我知道它应该能够做到，我可以去看一个列表，我可以看第一个，我不知道，也许我会去顶部，我知道每个列表都应该能够做到最后一个，好的，所以可以做`public void addLast(Item x)`，现在，与其实际写出这个方法的代码，我实际上只是放一个分号，这样就可以了。不过这里其实有一个小问题，你会注意到这里有一个“无法解析符号‘Item’”的错误，因为我忘记在这里导入相应的类型了，好的，所以打字的时候出了个小差错。

到了这个时候，我基本上是在说`List61b`应该能够添加元素，所以它不会通过这个`AList`类手动查找所有这些并复制过来，但我实际上要做些别的事情，我要把所有的东西都复制过来，以便更好地说明我的观点。当你复制所有的东西过来时，注意这里的一点，这些是私有变量，它们说你应该如何存储信息，不是每个列表都应该有一个数组，对吧？所以这不是成为列表的一部分，有些列表根本没有数组，我不需要构造函数，我的意思是，这不是一个明显的事实，但我不要求调整大小，这是我要保留的东西吗？不，有些列表不会调整大小，比如`DList`或`SLess`，没有调整大小的概念，所以我完全删除它，事实上，这个是私有的，你甚至会注意到，如果我高亮这个私有，这里不允许有私有的，私有本质上是一个秘密的实现细节，所以把它作为列表接口的一部分是没有意义的，没有人会用到它，那么`addLast`呢？好的，我们已经有了，听起来不错，列表应该有`getLast`吗？好的，现在我感觉不错，对，好的，看起来像是一个正常的列表操作，注意我在这里保留的是公共的方法，这里是`removeLast`，这里是`insert`，看起来不错，还有`getFirst`，所以如果我查看所有这些，你会注意到一件有趣的事情，我已经指定了`List61b`是什么，而不是如何实现，所以如果我们考虑我创造的这个宇宙，这就是`List61b`可以做的一切，你可以几乎像一个警察应该能够做的事情的规范一样思考这个问题，

We will use the new keyword interface instead of class to define a List61B.
>Idea: Interface is a specification of what a List is able to do, not how to do it. 
这是List61B.java


public interface List61B<Item>{
    public void addFirst(Itemx); 
    public void addLast(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();
} 

比如说，一个警察应该能够做什么，取指纹、打电话、开车等，所有一个警察应该能够做的事情，这就是列表，如果有人说我是警察，你可以假设是的，他们知道如何开车，那么接下来的事情是什么呢？下一步是我们将指定某物实际上是一个`List61b`。在这种情况下，我们将使用新的`implements`关键字来指定这种关系，就像之前我们有了`interface`作为新东西，现在我们将有`implements`，它看起来有点像这样。

所以让我们进入我们的`AList`类，然后说`implements List61b`，现在我实际上犯了一个错误，除非是`61p Item`，我当时在想我的手机响了，让我分心了。

所以我们`implement List61b`和`Item`，就是这样，现在我们要对`SList`做同样的事情，`implements List61b`，就是这样，所以一旦我做了这些，这就是我们生活的宇宙。所以这也应该匹配早期的那个工作，Josh，你应该问我，那么现在怎么样了？好的，所以记得我们的`Longest`类，我们不喜欢有多个`Longest`方法，有些针对`SList`，有些针对`AList`，所以现在我们定义了这个接口，我们实际上可以做`List61b`，这样应该没问题，所以如果我们运行这段代码，你看我们得到“watching”，即使我们在测试驱动中将`AList`改为`SList`，再次运行，它就像之前一样，如果我们有了解释如何洗狗的指示，我们现在建造了一台可以清洗任何种类的狗的机器，不仅是阿拉斯加雪橇犬，不仅是卷毛狗，而是任何狗。

WordUtils.java

public class WordUtils {
    /** Returns the length of the longest word. */
    public static String longest(List61B<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);
    }

    public static void main(String[] args){
        AList<String> someList = new AList<>();
        someList.addLast(x"elk");
        someList.addLast(x"are");
        someList.addLast("watching");
        System.out.println(longest(someList);
        //someList.print();
    }
}

AList.java部分需修改

AList
/** Array based list.
*@author Josh Hug
*/
/* The next item ALWAYS goes in the size position */
public class AList<Item> implements List61B<Item> {
    /* the stored integers */
    private Item[] items;
    private int size;

    private static int RFACTOR = 2；
    /** Creates an empty list. */
    public AList(){
        size = 0；
        items = (Item[]) new Object[100];
    }

    /** Resize our backing array so that it is
        *of the given capacity.*/
    private void resize(int capacity){
        Item[] a = (Item[]) new Object[capacity];
        System.arraycopy(items, srcPos:0, a, destPos:0,size);
        items = a;
    }

    /** Inserts X into the back of the list. */
    public void addLast(Item x) {
        if (size == items.length){
.................

SLList.java部分需修改

//SLListNode
/* Represent a list of stuff, where all the "list" work is delegated
to a naked recursive data structure.*/

public class SLList<Blorp> implements List61B<Blorp>{
    public class Node {
        public Blorp item;    /*Equivalent of first*/
        public Node next;     /* Equivalent of rest */
    
        public Node(Blorp i, Node h) {
            item = i;
            next = h;
        }
    }

    private Node sentinel;
    private int size;

    /** Creates an empty list. */
    public SLList(){
        size = 0；
        sentinel = new Node(null,null);
    }
    public SLList(Blorp x){
        size = 1；
        sentinel = new Node(null,null);
        sentinel.next = new Node(x,null);
    }
    /** Adds an item of the front. */
................................

8.4 overriding and overloading

让我们介绍一个重要的术语，即我们刚才所做的，叫做覆写（Overriding），我将对比之前我们看到的过载（Overloading）。那么什么是覆写呢？其实这是一个相当简单的想法，如果我们有一个子类，比如`List`，它有一个方法叫做`addLast(Item)`，这个方法的签名与超类中的完全相同，那么在这种情况下，我们说`AList`类中的`addLast(Item)`覆写了超类`List61B`中的`addLast`，或者简而言之，我们可以说`AList`覆写了`addLast`。覆写其实是一个相当直观的概念，所以让我们与之前看到的过载进行比较。

这里我有一个不同的覆写的例子，其中我们有一个叫做`Animal`的接口，它有一个`makeNoise`方法，而`Pig`也有一个`makeNoise`方法，其签名完全相同，所以`Pig`覆写了`makeNoise`。那么什么是过载呢？当有多个方法名称相同但签名不同时，我们就称之为过载。所以，例如，如果我们有一个公共类`Dog`实现了`Animal`接口，并且它有一个接受`Dog`类型参数的`makeNoise`方法，这样你对其他狗做出的反应与自言自语时不同，那么我们说`makeNoise`是过载的。与之前我们说的“A覆写了B”不同，对于过载，我们只是说该方法整体上是过载的，不是某个人过载了另一个人，而是整个方法过载了。我用来记忆这一点的方法是想象太多人在同一时间使用电力，导致电路断路器跳闸，这种情况下，电路断路器过载了，不是某人过载了另一人，而是整个系统过载了。这只是我有时使用的一个助记方法，但事实上也是如此。

顺便说一句，这个过载的概念同样适用于完全没有继承关系的情况。例如，在`Math`类中，有两个叫做`abs`的方法，一个是用于整数的绝对值计算，另一个是用于双精度浮点数的，这种情况下我们也说`abs`是过载的。

覆写是仅适用于继承关系的情况，并且只有当方法签名完全相同时才发生；而过载则发生在各种场合，任何时候你有两个名称相同但签名不同的方法时就会发生过载。

既然我们现在理解了什么是覆写，我将向你们介绍另一个稍微有些奇怪的语法，即在61B课程中，任何时候我们有一个覆写的方法，我们都会使用`@Override`注解。所以，如果我们查看代码，可以看到，`AList`类中任何覆写`List`接口中的方法的地方，我们都会添加一个`@Override`标签。所以这不覆写，那是构造器，那是个私有方法，但这个覆写了，所有ID覆写，我在这里加上`@Override`，在这里加上`@Override`，还有这个，我认为完成了，`@Override`，首先是`addLast`，然后是`getFirst`。所以我在所有这些地方都添加了`@Override`标签。

那么我为什么要这么做呢？这个标签唯一的功能是，如果我实际上没有覆写，那么代码就不会编译。例如，假设我们来到这里，尝试说`resize`是覆写的，我们会看到错误，它会告诉我实际上并没有覆写。所以这可能看起来有点愚蠢，像是一个无用的标签，但我们在这里使用它实际上是有用的。尽管除了控制是否编译之外它没有任何其他效果，但我认为它有几个有用的原因。首先，它可以防止打字错误，例如，假设我认为我写的是`addFirst`，但由于打字错误我写成了`adFirst`，当我加上`@Override`标签时，它会告诉我“实际上你没有覆写，因为没有`adFirst`方法”，我检查了一下`List61B`，确实没有`adFirst`方法。所以这是一个捕获打字错误的方法。另一个原因是，程序员能够看到`@Override`标签，并想到“哦，我现在记起来了，这个方法是从上面来的”，这对于思考程序的工作方式可能是有用的。

If a subclass has a method with the exact same signature as in the superclass, we say the subclass overrides the method.

• Even if you don't write @Override, subclass still overrides the method.
• @Override is just an optional reminder that you're overriding.

Why use @Override?

Main reason: Protects against typos.

1.If you say @Override, but it the method isn't actually overriding anything, you'll get a compile error.
2.e.g. public void addLats(Item x)

Reminds programmer that method definition came from somewhere higher up in the inheritance hierarchy.

重要的是要记住，即使你不使用`@Override`标签，你仍然是在覆写。这个标签不是启用覆写的东西，它只是一个标记，提醒你自己已经做了覆写。所以这就是关于这些术语的内容，我知道这堂课有点术语密集，但有时候就是这样的。

8.5 interface inherutance

实际上，指定上下位关系的方法有很多种，目前为止在本讲中我们所做的是称为接口继承（Interface Inheritance）的一种关系指定方式。我个人非常喜欢这种方式，在下一个视频中，我们将讨论另一种方法。首先，我来解释一下什么是接口继承，所以基本上，每当我们在子类中使用`implements`关键字来指定能力时，这被称为接口继承。为了分解这个术语，接口在这里指的是所有方法签名的列表，所以如果我们查看`List61b`，这些都是列表可以做的所有事情，我们使用继承这个词是因为我们说子类，也就是在顶部声明`implements`的那个类，继承了那个接口。这有点像锁（Lock）的例子，如果你去亚马逊搜索锁，所有的锁都有某些共同之处，它们可以被锁定也可以被解锁，至于它是怎么工作的则没有规定，有些用钥匙，有些用密码组合，不管怎样，关键在于它们能锁能开，这就是接口，而每种不同的锁（列表、SList、挂锁、密码锁）都有不同的实现方式，所以它只是说明了类能做什么，而不是具体怎么做。

在Java中，至少子类实际上需要覆写所有那些方法，正如我猜在亚马逊上如果你想出售一个不能锁也不能开的锁，它很可能很快就会被从货架上撤下来。在Java中，如果我们有一个`AList`不能做一些它应该做的事情，那么它就不会编译。所以换句话说，假设我们去修改`List61b`的规范，增加一个名为`true`的新方法，这是列表需要能够做的一件新事情，现在如果我们回到`AList`，此时我们会发现它不再编译，实际上`SList`也是同样的情况，它们都无法通过编译，因此如果改变规范，它们就不会编译，所以非常重要的是，子类需要覆写所有这些方法。

实际上，接口继承在现实世界中可以变得更复杂，我们可以有多代的接口继承，每个列表也是一个集合，这种情况实际上可以进一步发展，我们将在后续讲座中讨论这一点，但我在这里提一下，接下来四节课中我会经常使用这样的图示，接口始终用白色表示，类用绿色表示，但必要时我可能会偶尔使用不同的实色。

接口继承的概念是一个极其强大的工具，它使你能够泛化代码，因为我们能够编写像`WordUtils`中的`longest`方法这样的代码，这样我们就可以找到`SList`、`AList`或甚至是尚未发明的数据结构中的最长项。这就是接口继承。关于接口继承有趣的一点是，虽然它很强大，但似乎与我们之前讨论的一些概念有所矛盾。早在第3讲中，我们谈到了等号的黄金法则或海象之谜，几年前一位学生向我提出了这个问题。这位学生说：“嘿，Josh，你说当你写`x = y`或者传递参数时，你只是复制byte，其次你说内存盒只能保存适当类型的地址，例如你不能说`String x = new Dog()`，然而这里我们有一个`longest`方法，它应该接收列表对象，但当我们用`a1`调用这个函数时，`a1`包含的是一个持有`AList`地址的64位内存盒，不知何故我们能够复制这些比特，尽管它们并不是完全相同的类型。”这里的语言技巧在于，无论何时你指定一个继承关系，我们都可以简单地说，对于涉及内存盒检查的所有目的来说，`AList`就是一个列表，这是可以的。更准确的说法可能是，如果X是Y的超类，那么X的内存盒可以容纳Y。如果我们想要指定一些有意义的替代，我们可以说，如果狗是贵宾犬的超类，那么狗屋可以容纳贵宾犬。因此，如果我们有一个列表变量，它可以保存列表的地址。

Question: http://shoutkey.com/leash

Will the code below compile? If so, what happens when it runs?

a. Will not compile.
b. Will compile, but will cause an error at runtime on the new line.
c. When it runs, an SLList is created and its address is stored in the someList variable, but it crashes on someList.addFirst() since the List class doesn't implement addFirst.
d. When it runs, an SLList is created and its address is stored in the someList variable. Then the string "elk" is inserted into the SLList. referred to by addFirst.

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

这里有个问题来看看这一切是否说得通，并结合我们迄今为止讨论的所有继承相关的内容。假设我们有这样的代码段：`List61B someList = new SList();` 然后我们说 `someList.addFirst(elk);` 这里四个场景中的哪一个会发生？一是代码无法编译，二是代码编译但在这行运行时出错，三是这行运行良好但在执行`addFirst`时崩溃，因为列表不知道如何实现`addFirst`，四是所有事情都运行正常。请思考这个问题，然后我会揭晓答案，或许你可以暂停视频稍等片刻。揭晓答案：一切正常，代码编译没有问题，而且运行时也没有错误。所以正确答案是D，一切都运行得很好。希望这对你理解接口继承有所帮助，在下一节中我们将讨论另一种类型的继承，但在继续之前，请确保你已经理解了这部分内容。

//IsADemo   main()

public class IsADemo{
    public static void main(String[] args){ //args 
        List61B<String> someList new SLList<>();  //someList:SLList@458
        someList.addFirst("elk");                 //以下都是
        someList. addLast("dwell"); 
        someList.addLast("on"); 
        someList. addLast("existential"); 
        someList. addLast("crises");
        somelist.print(); //somelist: SLList@458 
    }
)