UCB CS61B sp25 学习笔记一：Lec1 ~ Lec10 Java语法与面向对象基础

 发表于 2026年06月10日  |  37 分钟  |  9049 个字  |  Hentilix Rivery

目录

Lecture 1 - Intro to 61B

整体而言是对CS61B这门课的一个介绍，提及了部分Java的基础语法，个人感觉这部分和C++类似。区别是Java是一门完全以类为核心的语言，不存在独立于类之外的全局函数。

注：本文任何代码块若出现缺少外部类包裹的裸方法，都是因为我太懒了，不想把已经实现完的代码再抄一遍导致的。

Lecture 2 - Defining and Using Classes, Lists and Maps

一、介绍了Java中的类和函数（方法）：

  1. Java 里所有的函数（方法）都必须属于某个类；

  2. 静态方法：可以访问静态成员变量，不能直接访问实例成员；

    非静态方法：依赖于类的对象实例，无法对类本身调用；

  3. static静态成员变量：归属于整个类，如果实例化一个类的成员A，那么A内部是没有独占的静态成员变量的；

  4. 创建对象时，记得使用new分配内存，Java不同于C++的是通常无需通过RAII管理对象的内存生命周期，因为Java拥有垃圾回收机制（GC），能够自动回收不再使用的对象。

二、介绍了Java中的几种基本数据结构：

  1. List列表：
import java.util.List;
//List本身是不能被实例化的，只能实例化实现了该接口的类，如下面两个：
import java.util.ArrayList;
import java.util.LinkedList;

public class ListDemo {
    public static void main(String[] args) {
        List<String> L = new ArrayList<>();
        //链表：List<String> L = new LinkedList<>();
        //如果只是List L = ...的话，也可以实现混合类型的列表，但不推荐这样做
        L.add("a");
        L.add("b");
        L.add("c");
        System.out.println(L);	//输出：[a, b, c]
        String s = L.get(0);	//访问列表中相应下标的元素
    }
}
  1. Array数组：
public class ArrayDemo {
    public static void main(String[] args) {
        String[] x = new String[5];
        x[0] = "a";
        x[1] = "b";
        System.out.println(x[0]);
    }
}
  1. Map映射
import java.util.Map;
import java.util.TreeMap;	//Map和TreeMap的关系同List和LinkedList的关系

public class MapDemo {
    public static void main(String[] args) {
        Map<String, String> L = new TreeMap<>();
        L.put("dog", "woof");
        L.put("cat", "meow"); 	//创建键值对
        String sound = L.get("cat");
    }
}

三、语言优劣之争

CS61B是61系列在61A之后的第二门课程，因此UCB里修习这门课程的学生大多数都已经学过了61A。因此，教授Josh Hug在课程中提到Java相比Python（也就是61A所使用的语言）更加的“性能取向”，而Python追求简单、优雅的代码风格。这时有一个学生说道：他认为Java不如C++优雅。对于这个问题，我想在这里发表一下我的看法。

我始终认为，讨论哪种语言更加优越完全是一种十分愚蠢的行为，不同的语言在诞生之初就已经对自身的使用场景和设计目标有了一定的预设，很难脱离具体情景去谈绝对优劣。说C语言没有Python优雅好写，或者Python的性能没有Java好，本质上都是十分狭隘的看法。身为一名编程学习者/相关行业从业者，无论是工程还是竞赛，无论是考试还是科研，你要做的事情其实就是解决你遇到的问题，或者完成你被要求的任务，不择手段，不分语言，而不是对“什么语言是世界上最好的语言”这种辩论发表高谈阔论。html不能写后端，Java没有指针，C++学习难度大……难道谁能因为这样的理由就说这些语言都很烂？说到底，随便一个程序员，即使他是大专毕业（没有瞧不起大专的意思），也绝对掌握了不止一门编程语言，我们需要的是对这些语言和知识进行应用，而不是对着一个毫无意义的问题争来争去。当然，我也知道，有些时候这些话只是一种玩笑，但我认为这样的讨论实际上有害无益。

Lecture 3 - References, Recursion, IntLists

一、介绍了Java中的值传递和对象引用

  1. 八种基本数据类型：byte、short、int、long、float、double、boolean、char。这些基本类型在进行赋值的时候都是值传递，比如：
int x = 3;
int y = x;
x = 5;

此时x = 5，y = 3，对x的重新赋值不会对y造成影响。

  1. 其余对象变量：对对象的引用，值可以是null。赋值时复制的本质是复制对象地址，注意不要当成引用对象本身，因为Java的复制永远是值传递。
public class Walrus {
    public double weight;
    public double tuskSize;
    
    public Walrus(double w, double ts) {
        weight = w;
        tuskSize = ts;
    }

    public static void main(String[] arg) {
        Walrus a = new Walrus(1000, 8.3);
        Walrus b = a;
        b.weight = 5;
    }
}

此时a和b的weight值都是5，因为a和b引用同一个Walrus对象，所以对b的改变也会体现在a上。

二、利用递归实现列表（IntList）

public class IntList {
    public int first;
    public IntList rest;
    
    public IntList(int f, IntList r) {
        first = f;
        rest = r;
    }
    
    //返回列表元素数量（递归）
    public int recursionSize() {
        if (rest == null) {
            return 1;
        }
        return 1 + rest.recursionSize();
    }
    
    //返回列表元素数量（循环）
    public int iterationSize() {
        int totalSize = 0;
        IntList p = this;
        while (p != null) {
            totalSize ++ ;
            p = p.rest;
        }
        return totalSize;
    }
    
    //获取列表第i个元素（我的解答）
    public int myGet(int i) {
        if (i < 0 || i >= this.recursionSize()) {
            throw new IllegalArgumentException("Index out of bounds!");
        } else {
            if (i == 0) {
                return first;
            } else {
                return rest.myGet(i - 1);
            }
        }
    }
    
    //获取列表第i个元素（Josh给出的答案）：
    public int get(int i) {
        if (i == 0) {
            return this.first;
        }
        return this.rest.get(i - 1);
    }
    
    
    public static void main(String[] args) {
        //正向构造
        IntList L = new IntList(5, null);
        L.rest = new IntList(10, null);
        L.rest.rest = new IntList(15, null);
        
        /*反向构造
        IntList L = new IntList(15, null);
        L = new IntList(10, L);
        L = new IntList(5, L);
        */
        
        System.out.println(L.recursionSize());
        System.out.println(L.iterationSize());
        
        System.out.println(L.get(1));
    }
}

个人感觉上面的代码和CS61A中实现列表的操作是很类似的。

Lecture 4 - Lists II SLLists

本次Lecture的工作基本就是实现一个比上节课更加实用的链表。

public class SLList {
    private class IntNode {
        public int item;		//此处嵌套类IntNode中的public完全可以删除，因为类本身是private的
        public IntNode next;
    
        public IntNode(int i, IntNode n) {
            item = i;
            next = n;
        }
    } 
    
    private IntNode sentinel;	//哨兵节点
    private int size;
    
    //初始化非空列表
    public SLList(int x) {
        sentinel = new IntNode(676767, null);
        sentinel.next = new IntNode(x, null);
        size = 1;
    }
    
    //初始化空列表
    public SLList() {
        sentinel = new IntNode(676767, null);	//刘夫妻小子正在和刘琦先生闹矛盾
        size = 0;
    }
    
    //在头节点前插入数据
    public void addFirst(int x) {
        sentinel.next = new IntNode(x, sentinel.next);
        size ++ ;
    }
    
    //获取头节点
    public int getFirst() {
        return sentinel.next.item;
    }
    
    //在尾节点后插入数据
    public void addLast(int x) {
        IntNode p = sentinel;
        
        while (p.next != null) {
            p = p.next;
        }
        
        p.next = new IntNode(x, null);
        
        size ++ ;
       
    }
    
    //时间复杂度为O(n)的方法，用于获取列表长度
    //返回从节点p开始的裸递归列表长度
    //private int size(IntNode p) {
    //    if (p == null) {
    //        return 0;
    //    } else {
    //        return 1 + size(p.next);
    //    }
    //}
    //获取列表长度
    //public int size() {
    //    return size(sentinel.next);
    //}
        
    //时间复杂度为O(1)的方法，用于获取列表长度
    public int size() {
        return size;
    }
}

public class SLListUser {
    public static void main(String[] args) {
        SLList L = new SLList();
        L.addFirst(15);
        L.addFirst(10);
        L.addFirst(5);
        L.addLast(20);
        
        System.out.println(L.getFirst());
        
        System.out.println(L.size());
    }
}

这节课在实现addLast()这个函数的时候会遇到一个问题，就是当链表为空时，头指针本身就是null，无法通过它访问next字段，进而使addLast()函数报错，而Josh在实现了一种针对此特殊情况的解决方案后，提出了这样一个观点：与其写完函数发现有特殊情况不得不写特判来解决，不如打从一开始就不让特殊情况出现。于是我们开始了对真·解决方案的实现：让空列表和非空列表的结构相同。我们在列表初始化时就创建一个哨兵节点（sentinel）作为头/尾节点即可，而真正的第一个节点是sentinel.next。

Lecture 5 - Lists III DLLists And Arrays

一、继续改进链表

在Lecture 4里，我们手动实现了一个单向链表，但是很容易发现该数据结构的一个缺点：虽然addFirst()的时间复杂度为\(O(1)\)，但addLast()需要遍历整个链表，因此时间复杂度为\(O(n)\)。我们可以通过额外维护一个尾指针来使addLast()达到\(O(1)\)，但removeLast()仍然需要寻找尾节点的前驱节点，因此时间复杂度仍为\(O(n)\)。

为了解决这一问题，我们让链表中的每一个节点同时记录前驱节点和后继节点，即增加一个prev指针，从而构成双向链表。这样便可以在\(O(1)\)时间内访问某个节点的前驱节点，从而高效地完成尾部操作。

但此时又会出现新的问题：链表首节点的prev和尾节点的next均为null，需要额外处理许多边界情况。为此，Josh采用了循环哨兵列表的结构：引入一个sentinel节点，并让链表首尾都与sentinel相连，形成一个环。这样无论链表为空还是非空，sentinel始终存在，链表中不再出现null指针作为边界标记，从而大幅减少特殊情况的处理。

注：此处对双向链表的代码实现和原课程保持一致，已使用泛型，不使用泛型的实现方案将不再写出。

public class DLList<Lappland> {
    private class LapplandNode {
        public Lappland item;
        public LapplandNode next;
        public LapplandNode prev;

        public LapplandNode(
                Lappland i,
                LapplandNode n,
                LapplandNode p) {

            item = i;
            next = n;
            prev = p;
        }
    }

    private LapplandNode sentinel;
    private int size;

    // 空链表
    public DLList() {
        sentinel = new LapplandNode(null, null, null);

        sentinel.next = sentinel;
        sentinel.prev = sentinel;

        size = 0;
    }

    // 非空链表
    public DLList(Lappland x) {
        this();

        LapplandNode first =
                new LapplandNode(x, sentinel, sentinel);

        sentinel.next = first;
        sentinel.prev = first;

        size = 1;
    }

    // 头插
    public void addFirst(Lappland x) {

        LapplandNode first =
                new LapplandNode(
                        x,
                        sentinel.next,
                        sentinel);

        sentinel.next.prev = first;
        sentinel.next = first;

        size ++ ;
    }

    // 尾插
    public void addLast(Lappland x) {

        LapplandNode last =
                new LapplandNode(
                        x,
                        sentinel,
                        sentinel.prev);

        sentinel.prev.next = last;
        sentinel.prev = last;

        size ++ ;
    }

    // 获取首元素
    public Lappland getFirst() {
        return sentinel.next.item;
    }

    // 获取尾元素
    public Lappland getLast() {
        return sentinel.prev.item;
    }

    public int size() {
        return size;
    }
}

public class DLListUser {

    public static void main(String[] args) {

        DLList<String> L = new DLList<>();

        L.addFirst("Exusiai");
        L.addFirst("Texas");
        L.addFirst("Mostima");

        L.addLast("Sora");
        L.addLast("Croissant");

        System.out.println(L.getFirst());
        System.out.println(L.getLast());
        System.out.println(L.size());
    }
}

二、泛型（Generics）

Java 泛型不能直接使用八种基本数据类型，这是因为 Java 的泛型通过类型擦除（Type Erasure）实现（这一点是GPT告诉我的），编译后T会被替换为Object，而int等基本类型不是Object的子类，因此必须使用包装类。所以上述代码中的<>内可以写Integer而不能写int，Lappland同理，这只是我给泛型起的一个名字。

三、数组（Array）

固定长度，缺少增删等便利方法，本质是连续的一串内存，存储相同类型的数据，支持\(O(1)\)的随机访问和\(O(n)\)的中间插入和删除。

Lecture 6 - Testing

这节课主要教怎么写单元测试，我们要编写选择排序的本体和单元测试。sp25的课程使用Google的truth库。在写单元测试的时候，我们可以用@Test对测试用的代码进行标记。

/* 排序 */
public class Sort {

    public static void sort(String[] x) {
        sort(x, 0);
    }

    private static void sort(String[] x, int s) {

        if (s == x.length) {
            return;
        }

        int smallest = findSmallest(x, s);

        swap(x, s, smallest);

        sort(x, s + 1);
    }

    public static int findSmallest(String[] x, int s) {

        int smallestIndex = s;

        for (int i = s; i < x.length; i ++ ) {

            if (x[i].compareTo(x[smallestIndex]) < 0) {
                smallestIndex = i;
            }
        }

        return smallestIndex;
    }

    public static void swap(String[] x, int a, int b) {

        String temp = x[a];
        x[a] = x[b];
        x[b] = temp;
    }
}

/* 测试 */
import org.junit.jupiter.api.Test;
import static com.google.common.truth.Truth.assertThat;

public class TestSort {
    @Test
    public void testSort() {
        String[] input = {"cat", "bob", "luka", "c++ is ..."};
        String[] expected = {"bob", "c++ is ...", "cat", "luka"};

        Sort.sort(input);

        assertThat(input).isEqualTo(expected);
    }
    
    @Test
    public void testFindSmallest() {
        String[] input = {"cat", "bob", "luka", "c++ is ..."};
        int expected = 1;
        
        int actual = Sort.findSmallest(input, 0);
        assertThat(actual).isEqualTo(expected);
    }
    
    @Test
    public void testSwap() {
        String[] input = {"cat", "bob", "luka", "c++ is ..."};
        String[] expected = {"bob", "cat", "luka", "c++ is ..."};
        
        Sort.swap(input, 0, 1);
        assertThat(input).isEqualTo(expected);
    }
}

个人感觉选择排序的代码自己想也很容易想到（事实上这部分只是个引子，个人感觉Josh根本不在乎学生会不会写排序，因为重点不在于此），这节课的精髓还是在于怎么写单元测试，让单元测试成为工作流不可或缺的一部分，主导修改和补充代码的整个流程，比如先写一个失败的测试，再写代码让它通过，Josh在课上就是这么做的。考虑到文章长度的限制，我在这里没法把原视频中的单元测试、各版本代码和Debug流程全部写出，但建议读者自行练习并掌握。单元测试绝对比你想的重要得多，毕竟真参加工作了可没有AutoGrader帮你找Bug。

题外话：不得不说一边看Josh反复Debug一边听课+记笔记是一件很折磨的事情，我的显示器只有16寸，分屏的时候视频窗口会变得很小，再加上Josh自己在写代码的时候IntelliJ的窗口本来就很小，这就导致复刻PPT上的代码的时候会很难受。

Lecture 7 - ArrayLists

一、数组，以及动态数组的实现。下面是最终版的代码实现：

public class AList {
    private int[] items;
    private int size;

    public AList() {
        items = new int[100];
        size = 0;
    }

    private void resize(int capacity) {
        int[] a = new int[capacity];
        System.arraycopy(items, 0, a, 0, size);
        items = a;
    }

    public void addLast(int x) {
        if (size == items.length) {
            // 另一种扩容的实现方式（内联）：
            // int[] a = new int[items.length * 2];
            // System.arraycopy(items, 0, a, 0, size);
            // items = a;
            resize(items.length * 2);
        }

        items[size] = x;
        size ++ ;
    }

    public int getLast() {
        if (size == 0) {
            throw new IllegalArgumentException("List is empty!");
        }

        return items[size - 1];
    }

    public int get(int i) {
        if (i < 0 || i >= size) {
            throw new IllegalArgumentException("Index out of bounds!");
        }

        return items[i];
    }

    public int removeLast() {
        int itemToReturn = getLast();
        size -- ;
        if (size <= items.length / 4 && items.length >= 16) {
            resize(items.length / 2);
        }
        return itemToReturn;
    }

    public int size() {
        return size;
    }
}

最初的程序实现了一个固定长度版本的ArrayList，可是，如果我们想要一个像C++ std::vector一样可以无限延长的数组，该怎么做呢？答案是在插入数据出现下标越界的时候创建一个扩容的新数组，并且把原数组复制过去。问题是应该把新数组扩容到多大。

首先考虑扩容至\(size + 1\)：当数组已满之后，每次addLast()操作都要重新扩容，那么对于\(n\)次addLast()，每一次（记为第\(i\)次）要复制一次数组（\(i\)个元素）并扩容，大约一共复制了\(\frac{n(n + 1)}{2}\)个元素，最终时间复杂度会退化至\(O(n^2)\)，这个时间复杂度太高了，因此我们需要考虑其他的扩容大小。

接下来我们考虑使用更大的常数，比如\(size + 1000\)，但是我们会发现这个数字的大小会是一个很尴尬的问题：当\(size\)太小的时候，这个常数可能会很大，但是随着\(size\)越来越大，这个常数很可能完全不够看，而且这一扩容方式在时间复杂度上和\(size + 1\)没区别。因此，我们想到了直接对\(size\)本身进行操作。

考虑C++中std::vector的实现方式：倍增。我们每次扩容都将新数组的大小扩充至\(size * 2\)，这样以来，假设最后数组容量增长到了\(n\)，那么复制次数为：\(1 + 2 + 4 + 8 + \cdots + \frac{n}{2} = n - 1\)次（忽略\(n\)是否为\(2\)的倍数），外加\(n\)次赋值，均摊到\(n\)次插入，平均每次插入的时间成本是\(\frac{O(n)}{n} = O(1)\)的，这样就大大降低了扩容成本，因此，我们最后选用\(size * 2\)的扩容方式。

现在，我们已经对插入新数据，尤其是大量新数据的情形，实现了相应的扩容和插入操作，下面我们就需要对删除数据的操作进行优化了。假设一种很极端的情况：我们插入了10亿组数据，然后又一口气删除了其中的9.9亿组，这无疑会导致浪费相当多的空间，所以，我们必须优化下面这种原有的删除思路：

public int removeLast() {
    int itemToReturn = getLast();
    size -- ;
    return itemToReturn;
}

依旧考虑一种类似倍增的思路：当已使用空间不足总容量的\(\frac{1}{4}\)时，将数组的大小减半，和上面的扩容思路类似。为什么这个数字不是\(\frac{1}{2}\)？很简单，假设这样一种情景：数组中恰好有\(\frac{1}{2}\)的元素不为空，那么数组大小减半会导致新数组直接为满，这样一来又会重新扩容，导致陷入一种类似死循环的情况中，所以我们将临界大小设置为整个数组的\(\frac{1}{4}\)。

二、Java中的“隐蔽主义”

“隐蔽主义”这个词是Josh自己编的一个概念，大体就是说用户不应该知道程序的具体实现细节，比如用户不应该知道我们是靠倍增来实现数组扩容的。这个概念在软件工程中对应“信息隐藏（Information Hiding）”，感兴趣的读者可以自行了解。对一个好的程序员来说，“隐蔽主义”也是在说应该在合适的地方使用private，应该构建合适的抽象屏障来把程序设计中不同的层级分开，比如我们事实上最后的实现是addLast()里面套resize()而不是直接在addLast()里面扩容。

Lecture 8 - Interface and Implementation Inheritance

考虑之前实现的SLList和AList，我们会发现这两个类有很多方法是相同的，比如addLast()、size()等等。我们是怎么在多个不同的类里实现名称相同的方法的呢？第一种，也是最直接的办法是为每种数据结构分别编写对应版本的longest()方法。如果这些方法恰好使用相同的方法名，那么它们会构成方法重载（Overloading）。例如，假设我们编写一个工具类，其中包含两个同名的longest()方法，一个接受 AList<String>作为参数，另一个接受SLList<String>作为参数，那么这两个方法就构成了重载。

方法重载的问题很明显：1.代码实现几乎相同，重复的代码写好几遍既不美观，也不省力；2.已编写的方法不适用于未来用到相同方法的新类，假设我们又搞出一个新的数据结构QLList，那么已有的longest()方法并不能用于QLList，我们又得写一遍，这太麻烦了。有没有能避免这一切的解决方案呢？

好吧，这没什么可卖关子的，第二种方法就是写一个公共接口。从语言学的角度来看，SLList和AList都是一种List，所以我们写一个接口 List61B来规定所有List应具备的行为，然后编写一个接受 List61B<String>作为参数的 longest()方法。这样无论是SLList、AList，还是未来新增的其他List实现，都能够直接使用这一方法。

Java的继承和C++略有区别，我们使用关键字interface来规定一组行为规范，实现该接口的类必须提供这些行为，并使用关键字implements声明该类实现这一接口。下面的longest()一次性实现了所有List61B子类的longest()方法。如果子类A继承自接口B，那么A必须实现B内部已声明的所有方法，否则编译器不会编译。

public interface List61B<Item> {
    public void insert(Item x, int position);
    public void addFirst(Item x);
    public void addLast(Item x);
    public Item getFirst();
    public Item getLast();
    public Item get(int i);
    public int size();
    public Item removeLast();
    default public void print() {
        for (int i = 0; i < size(); i ++ ) {
            System.out.print(get(i) + " ");
        }
        System.out.println();
    }
}

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

public class SLList<Item> implements List61B<Item> {
    ... //具体的代码实现
    
    //因为接口中对print()的实现对SLList而言十分低效，所以我们在SLList内重写这一方法
    @Override
    public void print() {
        // Node 为泛型版本的内部节点类，相当于之前 IntNode 的泛型化
        Node p = sentinel.next;
        while (p != null) {
            System.out.print(p.item + " ");
            p = p.next;
        }
    }
}

在通过接口完成对通用方法的编写后，我们也可以在子类内部重写（Override）该方法。我们可以通过@Override标签标注“正在进行重写”，如果编译器检查发现并没有重写该方法，则会报错。

default关键字用于修饰接口类（interface），被这一关键字修饰的方法可以直接在接口类中编写方法体。default方法的引入（Java 8）使得在不破坏已有实现的前提下为接口添加新方法成为可能，否则每加一个方法，所有实现类都得跟着改。

总结：接口（Interface）或抽象类的意义在于定义行为而非实现。我们通过一组操作来描述抽象数据类型（ADT），而不关心其具体实现方式。因此，只要遵循相同的行为规范，无论底层采用链表还是数组，都可以被统一地使用。接口的核心价值不在于减少代码重复，而在于让程序依赖抽象而非具体实现，从而实现解耦。

Lecture 9 - Subtype Polymorphism, Function Passing, Generic Functions

一、多态

Wikipedia对“多态（Polymorphism）”这个词的解释是“为不同数据类型的实体提供统一的接口，或使用一个单一的符号来表示多个不同的类型”。比如下面这个例子就是Python中多态的体现：

class Dog:
    def __init__(self, name, size):
        self.name = name
        self.size = size
    
    def __gt__(self, other):
        return self.size > other.size
    
def name_len(dog):
    return len(dog.name)

def get_the_max(x):
    max_value = x[0]
    for item in x:
        if item > max_value:	#多态
            max_value = item
    return max_value

在这段代码里，大于号>就是这个统一的接口，它为我们提供了比较相同数据类型大小的途径，而我们通过__gt__()函数对Dog这一数据类型实现了对>的支持，这其实就是运算符重载，当然，运算符重载的本质还是多态。

Java同样大量依赖多态，但它不允许开发者像Python那样为自定义类型重载运算符。因此，为了实现通用的比较逻辑，我们需要借助接口（Interface）和子类型多态(Subtype Polymorphism)来完成。现在，让我们试着用Java复刻上面那段代码。

首先写一下主函数：

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class CollectionsDogDemo {
    public static void main(String[] args) {
        List<Dog> dogs = new ArrayList<>();
        dogs.add(new Dog("Grigometh", 200));
        dogs.add(new Dog("Pesula", 5));
        dogs.add(new Dog("Clifford", 9000));
        
        Dog maxDog = Collections.max(dogs);
    }
}

此时我们会遇到第一个问题：在我们实现比较逻辑之前，怎么让编译器知道Dog这个类是可比较的？答案是利用Java中的Comparable接口。补充一下对Dog类的实现：

public class Dog implements Comparable<Dog> {
    String name;
    int size;
    
    public Dog(String n, int s) {
        name = n;
        size = s;
    }
    
    @Override
    public int compareTo(Dog other) {
        if (size < other.size) {
            return -1;
        } else if (size > other.size) {
            return 1;
        }
        return 0;
    }
    
    /*优化版：
    public int compareTo(Dog other) {
        return size - other.size;	//忽略潜在的溢出问题
    }
    */
}

二、函数传递

然而，Comparable存在一个问题：它只能为一个类定义一种默认比较方式。在上面的例子中，我们按照size进行比较，但如果我们希望按照名字的字典序（name）来比较两只狗，该怎么办？

显然，我们不能同时编写多个 compareTo()方法来表示不同的排序规则。因此，Java提供了 Comparator接口，用于将“比较规则”从对象本身中分离出来，从而实现更加灵活的比较逻辑。现在让我们实现新的比较逻辑：

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

三、泛型函数

上面的代码已经解决了比较问题，但是新的问题是：目前的比较规则只适用于Dog类。假如我们想让已有的比较规则适用于新的类，我们就只能重复编写类似的方法。所以我们需要用到泛型来解决这个问题：

public static <T> T max(T[] items)

这个<T>表示这个方法为泛型函数，而此处的T是一个类型变量，调用时编译器会自动推断T的类型。此时最后的问题是：假如T没有compareTo方法怎么办？因此我们需要：

public static <T extends Comparable<T>>
T max(T[] items)

意思是T必须实现Comparable接口。

总结：Lecture 9本质上整节课只讲了一件事，即如何让同一段代码适用于多种不同的数据类型。Josh给出了三种不同的解决方案：

  1. 子类型多态：通过继承和接口复用代码；

  2. 函数传递：通过传递行为复用代码；

  3. 泛型函数：通过类型参数复用代码。

三者都在解决同一个问题：不要为每一种数据类型都重新写一遍代码。

Lecture 10 - Iterators, Object Methods

一、实现一个集合（ArraySet）

让我们从一份已有的代码实现开始。下面的代码已经实现了三个功能：

  1. contains()：判断集合中是否存在某元素；

  2. add()：向集合中添加某元素；

  3. size：返回集合大小。

public class ArraySet<T> {
    private T[] items;
    private int size;
    
    public ArraySet() {
        items = (T[]) new Object[100];
        size = 0;
    }
    
    public boolean contains(T x) {
        for (int i = 0; i < size; i ++ ) {
            if (items[i].equals(x)) {
                return true;
            }
        }
        return false;
    }
    
    public void add(T x) {
        if (x == null) {
            throw new IllegalArgumentException("Can't add null!");
        }
        if (contains(x)) {
            return;
        }
        items[size] = x;
        size ++ ;
    }
    
    public int size() {
        return size;
    }
    
    public static void main(String[] args) {
        ArraySet<Integer> aset = new ArraySet<>();
        aset.add(5);
        aset.add(23);
        aset.add(42);
    }
}

而Java本身提供了Set<>这一集合接口，它支持这样的操作：

Set<Integer> javaset = new HashSet<>();
javaset.add(5);
javaset.add(23);
javaset.add(42);
for (int i : javaset) {
    System.out.println(i);
}

我们首先要实现的功能是让ArraySet这个集合成为一个和原Set一样可以迭代的数据类型，并且可以通过迭代打印其内部的元素，但在此之前，我们先来分析一下for (int i : javaset) {...}这段代码的工作方式。它在本质上等于下面这种写法：

Iterator<Integer> seer = javaset.iterator();

while (seer.hasNext()) {
    int x = seer.next();
    System.out.println(x);
}

前者事实上是一种Java语法糖，编译器会自动将其转换为基于 Iterator 的迭代过程，更简单，也更优美，但是在此处我们选用后者作为对ArraySet迭代操作的实现，因为它更接近底层也更易于理解。实现（36~67行）后的总体代码如下：

import java.util.Iterator;

public class ArraySet<T> implements Iterable<T> {
    private T[] items;
    private int size;
    
    public ArraySet() {
        items = (T[]) new Object[100];
        size = 0;
    }
    
    public boolean contains(T x) {
        for (int i = 0; i < size; i ++ ) {
            if (items[i].equals(x)) {
                return true;
            }
        }
        return false;
    }
    
    public void add(T x) {
        if (x == null) {
            throw new IllegalArgumentException("Can't add null!");
        }
        if (contains(x)) {
            return;
        }
        items[size] = x;
        size ++ ;
    }
    
    public int size() {
        return size;
    }
    
    private class ArraySetIterator implements Iterator<T> {
        private int position;

        ArraySetIterator() {
            position = 0;
        }

        @Override
        public boolean hasNext() {
            if (position < size) {
                return true;
            }
            return false;
        }

        @Override
        public T next() {
            T itemToReturn = items[position];
            position ++ ;
            return itemToReturn;
        }
    }

    public Iterator<T> iterator() {
        return new ArraySetIterator();
    }

    public static void main(String[] args) {
        ArraySet<Integer> aset = new ArraySet<>();
        
        aset.add(5);
        aset.add(23);
        aset.add(42);
        
        Iterator<Integer> aseer = aset.iterator();
        
        while (aseer.hasNext()) {
            int i = aseer.next();
            System.out.println(i);
        }
    }
}

这里解释一下对第三行的额外修改：注意 ArraySet实现的并不是 Iterator接口，而是Iterable接口。Iterable的职责是提供iterator()方法，而Iterator的职责才是完成具体的遍历过程。一个Iterable对象可以不断生成新的Iterator，因此二者代表的含义并不相同。Iterator负责记录“遍历到哪里了”，而容器负责存储数据。

另：Iterator通常被实现为内部类，因为它需要访问容器对象的内部状态。

二、对象方法

这部分可以看作是一些Java内置方法的合集。考虑到Java中的所有引用类型最终都继承自Object，因此我们总是可以写出Object o = ...这样的代码，其中...是任何引用类型的东西。

  1. toString：

返回对象的String表示，用法类似Python中的__repr__。我们可以在ArraySet里面实现一个属于自己的toString()方法：

public String toString() {
    String stringToReturn = "{";
    for (T x : this) {
        stringToReturn += x;
        stringToReturn += ", ";
    }
    stringToReturn += "}";
    return stringToReturn;
}

注：在真正的工程中，循环内拼接字符串应使用StringBuilder，因为String是不可变的，每次+=都会创建新对象，时间复杂度为\(O(n^2)\)。此处的+=也可以用append()，不过视频里Josh最后还是用了+=，所以我也就没改。

  1. == vs. equals()：

对于八种基础数据类型没区别；对于对象而言，==判断的是二者是否引用同一个对象，而equals()判断的是两个对象是否逻辑相等，而具体什么叫“相等”取决于该类对 equals()的实现。依旧自己实现一遍equals()：

public boolean equals(Object o) {
    if (o instanceof ArraySet otherSet) {
        if (this.size != otherSet.size) {
            return false;
        }
        for (T x : this) {
            if (!otherSet.contains(x)) {
                return false;
            }
        }
        return true;
    }
    return false;
}

另外必须要注意的是，在Java中，如果你重写了equals()，一般也必须同时重写hashCode()，否则该类的对象在HashSet或HashMap中可能会出现行为异常。Josh在后续课程中会专门讲这一问题。

  1. this：

写构造函数的时候，如果形参名称和类变量名相同，那就得用this，否则可以不用。例如this.size = size或size = s可以运行而size = size不行。

个人感想及总结

至此，CS61B中关于Java语法与面向对象基础的部分也算正式告一段落了。接下来，课程将真正进入数据结构与算法的核心内容。

坦白来说，我始终觉得语法的学习是繁琐而痛苦的。它往往充满了各种细节、规则和约束，需要花费大量时间去熟悉和适应。不过幸运的是，我（以及所有学习CS61B这门课的人）遇见了Josh这样一位好老师。他总能把那些原本枯燥的语法知识讲得生动、有趣而又深入浅出，让人不至于在学习的过程中失去耐心。

对于这一部分内容，我最大的体会其实只有一句话：不要过分关注那些无意义的细节。

这句话的含义很多。对于编程本身而言，我们更应该关注抽象的设计与实现，而不是沉迷于具体代码的细枝末节；对于计算机课程的学习而言，也应该更多地关注课程真正想传达的思想，而不是把精力全部消耗在某门语言究竟有哪些语法特性上。

现在回头看自己学习CS61A的过程，我无疑犯过这样的错误：花费了太多时间研究Python语法，却忽略了课程本身真正想讲述的内容。所幸如今我已经意识到了这一点，希望今后的自己不会再重蹈覆辙吧。

起初我曾考虑把Lab、Homework以及Project的实现也一并放在这篇文章的末尾，不过后来发现这样会让整篇博客过于冗长，于是最终还是作罢。多少算是留下了一点遗憾吧，笑。

接下来的一段时间里，我大概会暂时放下CS61B。毕竟学校的课程也到了需要认真准备期末考试的时候，尤其是高等数学和大学物理这两门课。

希望等到暑假的时候，我还能重新把这门课程捡起来，继续沿着这条路走下去。

感言就先写到这里。至于更多的话，还是留到真正完成CS61B的那一天再说吧。

技术  CS61B 

也可以看看