cs61b系列day5——回顾1

前言

又一个月过去了，现在学到哈希表，感觉是时候写一点东西了。本来准备直接写做Proj2的心路历程的，又觉得还是先做一个回顾好一些。

以前一直用vscode写文章，每次都要部署后才能看得到效果，有些浪费时间。今天试了一下Typora，感觉十分不错！但还是写了一下午，时间是真的不够啊。

cs61b的前1/3讲了主要讲了三个内容：Java语法、Java面向对象以及最基础的数据结构（链表、队列）、算法（插入排序等）。说实话，很多内容都记不清了。

我一直不是很清楚讲语法的文章应该怎么写，因为有权威——各种书（例如《Java编程思想》）、Java官方文档已经讲得很好了，资料也很容易找到，另外网上写这些的多如牛毛。最后决定只写给自己看，但也会尽量保持文章严谨、清晰，只为留下思维的痕迹。

这里的回顾只涉及cs61b中讲授的Java基础内容，若有不足之处请原谅。

Java的基础语法

与C重合的部分
写代码->编译->运行，从形式上来看，编写Java程序与C程序的流程相同。
主函数int main(int argc, char* args[])变为public static void main(String args[])，但作用基本一致。
对于程序的三种基本控制结构：顺序、选择和循环，Java只比C多了foreach语法。
操作符也是熟悉的样子，&&没有变成and，||没有变成or，短路求值的原则也不变。
函数（方法）参数的传递依旧为传值，C中传指针变成了传引用，但The golden rule of equal没有变——比如x = y的含义是copy bits from y to x。Java也支持递归，用起来与C没什么不同。
不同
Java是强类型语言，偏向于不容忍隐式类型转换。如int i = 6.8;就不能通过编译。
Java没有sizeof，因为数据类型对应的储存空间与平台无关。

Java与C天差地别，这里列举的异同只是个人的第一感受。

Java面向对象

接下来的内容仅包含我用到的面向对象特性中的核心部分，也仅仅是我的部分简单理解。

接口继承(Interface Inheritance)
1. 接口最大的特点：方法可以没有方法体、不能被实例化。
2. 接口继承：要求最终有一个类重写了接口中定义的所有方法
3. 标记接口
  标记接口没有任何方法，其中一个用途便是标记。例如在接下来的Proj 2中用到的Java序列化中的Serializable接口，仅仅用于标识继承该接口的类是可序列化的，方便序列化前的检查工作。
实现继承(Implement Inheritance)
几乎继承父类的所有东西，可以通过重写继承下来的方法，或是增加自己的成员变量、方法来进行拓展。
无论是哪种继承都可以用super关键字访问父类成员。
关于继承的条条框框还挺多的，可以在RUNOOB中阅读。

重载(Overload)

在Java中，可以有同名不同参数的方法，我们称这种方法被重载了。一般来说编译器都能跟据使用时的参数选择特定方法，但也有例外。请看下面的例子：

import org.junit.Test;
import static org.junit.Assert.*;

public class TestA {
    static <T> T returnT(T i) {
        return i;
    }
    @Test
    public void TestOverload() {
        assertEquals(9, returnT(9));
    }
}

编译会报错：

对assertEquals的引用不明确，org.junit.Assert 中的方法 assertEquals(long,long) 和 org.junit.Assert 中的方法 assertEquals(java.lang.Object,java.lang.Object) 都匹配。

原因在于Java支持自动拆/装箱，而这导致了二义性。如果将9装箱，匹配的是参数为(long, long)的方法；如果将returnT(9)的返回值(类型为Integer)拆箱，匹配的是参数为(Object, Object)的方法。因此你必须明确告诉编译器应该怎么做。可以将第10行修正以避免错误：

1	assertEquals((Integer) 9, returnT(9));

重写(Override)
重载发生在同一个类中，而重写发生在有继承关系的类之间。重写时，方法的返回值、参数都不能变（返回值可以是父类返回值的派生类）。
为了避免非法的重写（如名称不同导致根本没有重写），我们可以在重写的方法上方加上@Override，让编译器替我们检查。
更多关于重写重载的细节，可以在RUNOOB中阅读。

多态(Polymorphism)、转型(Cast)和动态方法选择(Dynamic Method Selection)

先理解两个概念：

静态类型(static type)和动态类型(dynamic type)
静态类型是编译时期(compile-time)的类型，动态类型是运行时期(run-time)的类型。
一个实例的静态类型在编译时（声明时）就确定了，但动态类型不是。由于继承是一种is-a的关系（写出来就是子类is-a父类），一个实例的动态类型可以是本身，也可以是众多子类中的一个，在编译期无法确定。这种情况被称为多态。

再来看转型：我们假设Cat extends Animal且Dog extends Animal

向上转型(Cast up)
1
Animal a = new Cat();
这时发生的就是向上转型(Cast up)，可以说，因为有了向上转型才有了多态。注意，转型后的a不能调用Cat类中的方法。
向下转型(Cast down)
你很清楚Dog和Dog生不出Cat，因为你对遗传学了如指掌，然后你把两个Dog作为参数放入了一个万能的繁殖函数中（它的注释表明它能为一切Animal配种）。但它的返回值是Animal，而你想用一个静态类型为Dog的引用指向返回值。尽管你知道这个Animal的动态类型一定是Dog，但编译器就是报错。于是向下转型就派上了用场：
1
Dog d = (Dog) born(d1, d2); // d1, d2's dynamic types are also Dog.
然而，向下转型是危险的，因为错误不会在编译时期被检测到。如果born方法返回的实例的动态类型是Cat，那只会在运行时期发生错误，因为编译器坚信你的生物高分不是白来的。

最后的概念与重写有关:

动态方法选择(Dynamic Method Selection)
有时候，父类和子类都有相同的方法，换句话说，子类重写了父类的方法。在方法调用时，可能会产生歧义，动态方法选择解决了这个问题。Reading 4.1中是这样描述它的：

The rule is, if we have a static type X, and a dynamic type Y, then if Y overrides the method from X, then on runtime, we use the method in Y instead.

这些概念有时确实非常令人费解，你可以试一试Discussion中的第一题：

Suppose we have the Dog and Corgi classes which are a defined below with a few methods but no implementation shown. (modified from Spring ’16, MT1)

public class Dog {
 public void bark(Dog d) { /* Method A */ }
}
public class Corgi extends Dog {
 public void bark(Corgi c) { /* Method B */ }
 @Override
 public void bark(Dog d) { /* Method C */ }
 public void play(Dog d) { /* Method D */ }
 public void play(Corgi c) { /* Method E */ }
}

For the following main method, at each call to play or bark, tell us what happens at runtime by selecting which method is run or if there is a compiler error or runtime error.

public static void main(String[] args) {
 Dog d = new Corgi();
 Corgi c = new Corgi();

 d.play(d); Compile-Error Runtime-Error A B C D E
 d.play(c); Compile-Error Runtime-Error A B C D E
 c.play(d); Compile-Error Runtime-Error A B C D E
 c.play(c); Compile-Error Runtime-Error A B C D E

 c.bark(d); Compile-Error Runtime-Error A B C D E
 c.bark(c); Compile-Error Runtime-Error A B C D E
 d.bark(d); Compile-Error Runtime-Error A B C D E
 d.bark(c); Compile-Error Runtime-Error A B C D E
}

这里是Solution。思考的过程才是最重要的。

注释、Javadoc和注解

包含在注释中的Javadoc文档注释，如@return、@param等，能帮助我们更好的理解程序。而@Deprecated @SuppressWarnings @Override等在方法上方的注解有时能提供更人性化的注释，或者替我们检查出一些错误。

IDE——IntelliJ

Debuger、代码检查、代码补全、git插件、cs61b插件（用于代码样式检查）、Java visualizer插件、TODO标签。。。大概用到了这些功能。

单元测试

主要使用JUnit的Assert模块中的各种方法。
在测试方法前加上@Test可以简化测试流程，还可以在后面加上”(timeout)”限制测试时间。

泛型(Generic)

老实说，目前我对泛型的了解较少。

泛型类
为了使一个类能拥有任何类型（参数化类型），可以使用以下的语法：
1
public class ArrayMap<K, V> {...}
实例化时传入“真实的”类型。

泛型方法

定义一个传入泛型参数的方法：

1	public static <Chow, Der> Chow get(ArrayMap<Chow, Der)> am, Chow key){...}

有时要限制传入类的类型，如下：

public static <K extends Comparable, V> K maxKey(ArrayMap<K, V> am) {
...
if (k.compareTo(largest) > 0) {
   ...
}

异常(Exception)

目前用异常也用得较少，基本上只有简单的throw。以下内容大都来源于lecture，加入了大量个人理解。

抛出异常
程序会出现很多错误。一方面，有时候默认的错误提示会让人摸不着头脑，另一方面，我们要为自定义的类添加错误提示。我们可以利用throw关键字，在运行时抛出异常(Exception)，并终止程序运行。
1
2
3
if (params == null) {
throw new IllegalArgumentException("params must not be null!");
}
- 异常是一种类，有构造函数、有成员，具体的继承关系如下图
捕获异常
有时候，我们并不希望程序就这样终止掉，而是希望异常被捕获(Catch)，并在之后的流程中被处理。
1
2
3
4
5
try {
doSomthing();
} catch (Exception e) {
fixIt();
}
如上图的代码，如果执行doSomething()时内部抛出了任何尚未被捕获的异常，catch接受该异常的实例，并执行fixIt()。

捕获异常的哲学

然而你可能会说，if-else同样可以处理错误，为什么还要有try-catch。当可能的错误越来越多时，程序逻辑越来越复杂，需要考虑的情况也就越来越多，if-else会显得很繁杂。可以从下面的读取文件的伪代码看出孰优孰劣：

func readFile: {
   try {
         open the file;
         determine its size;
         allocate that much memory;
      read the file into memory;
      close the file;
   } catch (fileOpenFailed) {
         doSomething;
   } catch (sizeDeterminationFailed) {
         doSomething;
   } catch (memoryAllocationFailed) {
      doSomething;
   } catch (readFailed) {
      doSomething;
   } catch (fileCloseFailed) {
         doSomething;
   }
}

func readFile: {
   open the file;
   if (theFileIsOpen) {
      determine its size;
      if (gotTheFileLength) {
         allocate that much memory;
      } else {
               return error("fileLengthError");
         }
         if (gotEnoughMemory) {
      read the file into memory;
            if (readFailed) {
            return error("readError");
      }
            ...
      } else {
         return error("memoryError");
      }
   } else {
      return error("fileOpenError")
   } 
}

未捕获异常(Uncaught Exception)
有时候我们会看见这样的错误提示：

java.lang.RuntimeException in thread “main”:
at ArrayRingBuffer.peek:63
at GuitarString.sample:48
at GuitarHeroLite.java:110

这揭示了未捕获异常的行为：向上冒泡，直到被捕获或者到调用栈的最底部。上面的信息就是所谓的栈轨迹(Stack Trace)。栈轨迹能帮助我们定位错误。
必须检查的vs不必须检查的异常
编译器要求所有必须检查的异常(Checked Exception)必须被捕获或者specify。
- Specify这个词描述的行为如下：
  利用throws关键字，告诉编译器可能会有某种异常，并且它会向上冒泡，告诉程序员这个方法可能会抛出异常，你必须在更高的层面处理。使用方法如下：
  1
  2
  3
  public static void gulgate() throws IOException {
  ... throw new IOException("hi"); ...
  }
下面的图展示了分类：
- 为什么Java不把所有的异常设计为必须检查的异常?
  原因在于，那些不必须检查的异常(Unchecked Exception)，通常无法提前预知（比如发生了bug），而必须检查的异常大多数时候都可以有补救措施。

迭代器(Iterator)

上文提到了Java相比于C语言多的一种循环方式：foreach循环。

而一个类要支持foreach的迭代方式，必须继承Iterable接口，同时重写接口中的Iterator方法。下面是部分Iterable接口：

1
2
3

public interface Iterable<T> {
   Iterator<T> iterator();
}

Iterator方法会返回一个Iterator接口，而Iterator接口中有抽象方法hasnext()和next()，用于实现遍历。

public interface Iterator<T> {
   boolean hasNext();
   T next();
}

了解上面的三点后，我们的方法可以细分为两种：

建立继承Iterator的私有内部类，其中重写了hasnext()和next()方法。在Iterator中返回该类的一个实例

private class ArraySetIterator implements Iterator<T> {
      private int wizPos;

      public ArraySetIterator() {
            wizPos = 0;
      }

      public boolean hasNext() {
            return wizPos < size;
      }

      public T next() {
            T returnItem = items[wizPos];
            wizPos += 1;
            return returnItem;
      }
}

在Iterator中返回现成的Iterator
比如java.util包中，Collection接口继承了Iterable接口，那所有继承Collection接口的类（比如HashSet等）都有Iterator方法。

注意：迭代器中的误区
使用迭代器时会创建原对象的复制，因此不能直接修改原对象。

包(Package)

包是一个组织接口和类的命名空间(Namespace)。可用于避免同名类的问题。

比如在ug/josh/animal/Dog.java文件的最顶部加上：

1	package ug.joshh.animal

注意然后在其它.java文件中，你就可以：

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

然而这样做可能十分繁琐，我们需要import关键字：

1 2	import ug.joshh.animal.Dog; import ug.joshh.animal.*;

之后你就能抛弃长长的ug.joshh.Dog.animal.Dog，只用Dog。（需要注意的是，后一种方法可能会污染命名空间）

访问权限控制(Access Control)

用一张图便可以说清楚大部分内容：

举个例子，图中的黑框框代表包内私有(Package Private)，从图中可以看出，同一个类、同一个包内有它的访问权，而子类和其它范围没有它的访问权。
访问权限控制还有一些细节，这里就不赘述了。

Object

所有的对象都继承自Object类（就算没有显式表明），因此我们有必要了解Object。cs61b中只介绍了Object中的以下几个方法：

String toString();
boolean equals(Object obj);
Class<?> getClass();
int hashCode();

toString()
一般的作用是将对象用字符串表现出来。println方法会自动调用对象中的toString方法。

equals(Object obj)

==比较两个对象的地址，而一般来说，equals方法比较对象的内容（Object类中使用==，因此你自定义类时，最好重写equals方法）。

然而重写equals方法并不像想象中那么简单，下面的范例重写了Date类中equals方法：

public boolean equals(Object x) {
   if (this == x) return true; // A little trick.
   if (x == null) return false;
   if (this.getClass() != x.getClass()) {
         return false;
   }
   Date that = (Date) x;
   return this.day == that.day && this.month == that.month
      && this.year == that.year;
}

很有趣的一点是，equals方法和数学上的判断是等价的。equals方法必须满足以下性质

自反性(Reflexive)
传递性(Symmetric)
对称性(Transitive)。

除此之外还有一些要求：
1.　接受Object类型参数（因为是重写嘛）
2.　应该有持续性：只要两方都不改变，结果就不变
3.　x.equals(null)总返回false

getClass()
返回该对象的动态类型，不需要重写。（《Java编程思想》中有更详细的描述）
hashCode()
很重要的一个方法，几乎所有类都会重写这个方法。下面的内容与哈希(hash)相关。
Object类中hashCode的默认实现返回的是该对象的地址，然而这样做通常效率不高，因此几乎所有的类都会重写这个方法。
还有一点：equals方法与hashCode方法必须同时重写。因为Java内置的在hashSet类中，containsKey方法会先调用hashCode方法，再调用equals方法。

前言

Java的基础语法

Java面向对象

接口继承(Interface Inheritance)

实现继承(Implement Inheritance)

重载(Overload)

重写(Override)

多态(Polymorphism)、转型(Cast)和动态方法选择(Dynamic Method Selection)

注释、Javadoc和注解

IDE——IntelliJ

单元测试

泛型(Generic)

泛型类

泛型方法

异常(Exception)

抛出异常

捕获异常

捕获异常的哲学

未捕获异常(Uncaught Exception)

必须检查的vs不必须检查的异常

迭代器(Iterator)

包(Package)

访问权限控制(Access Control)

Object

toString()

equals(Object obj)

getClass()

hashCode()