介绍

先来个Helloword：

public class Helloworld {
    public static void main(String[] args) {
        System.out.println("Hello world");
    }
}

Java 的特点：

所有代码都必须在类里面
语句组用大括号，语句末用分号
变量使用前先声明
变量类型是确定的，且不可变（静态语言）
注意public，private等
函数参数需要声明类型，返回值也是
所有 Java 中的函数都是方法

确定变量类型的优点：

运行速度快
可读性强
减少类型错误

缺点：

代码复杂

类 class 的使用

假如有这样一个类：

public class Dog {
    public int weight;

    public Dog(int startingweight) {
        weight = startingweight;
    }

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

    public void makeNoise_non_static() {
        if (weight < 10)
            System.out.println("bark");
        else
            System.out.println("woof");
    }
}

使用如下：

public class Doglauncher {
    public static void main(String[] args) {
        Dog smallDog; // 声明一个 Dog 变量
        new Dog(20); // 实例化对象
        smallDog = new Dog(5); // 同时 实例化对象 并 赋值
        Dog hugeDog = new Dog(150); // 同时 声明 实例化 并 赋值
    }
}

static 静态

static 方法用类名调用，如 Dog.makeNoise_static()
non-static 方法用实例化名称调用，如 smalldog.makeNoise_static()
static 方法不能访问实例化变量，如 makeNoise_non_static 中不能使用变量 weight

为什么要使用 static 方法？

对于Math类来说，往往不需要实例化，如使用 x=Math.round(5.6) 比 Math m = new Math(); x = m.round(x); 更自然

可以同时拥有 static method 和 non-static method：

public static Dog maxDog(Dog d1, Dog d2) {
    if (d1.weight > d2.weight) {
        return d1;
    }
    return d2;
}

public Dog maxDog(Dog d2) {
    if (weight > d2.weight) {
        return this;
    }
    return d2;
}

静态变量：public static String name = "dog";

测试 Test

可以使用junit：

public class Test {
    public static String stringMax(String a, String b) {
        if (a.compareTo(b) < 0)
            return b;
        return a;
    }

    public static void testStringMax() {
        String[] input = { "a", "b" };
        String expected = "a";

        String actual = stringMax(input[0], input[1]);
        org.junit.Assert.assertEquals(expected, actual);
    }

    public static void main(String[] args) {
        testStringMax();
    }
}

引用 Reference

public static void main(String[] args) {
    Dog a = new Dog(5);
    Dog b = a;
    b.weight = 10;
    System.out.println(a.weight);
    System.out.println(b.weight);
}

输出均为 10，表示 b 只是 a 的一个引用，并不是复制了一份

SLList 单链表、嵌套类、哨兵 Sentinel 节点

public class SLList {
    // sentinel.next是链表的第一个元素
    private IntNode sentinel;
    private int size;

    private static class IntNode {
        int item;
        IntNode next;

        IntNode(int i, IntNode n) {
            item = i;
            next = n;
        }
    }

    public SLList() {
        sentinel = new IntNode(-1, null);
        size = 0;
    }

    public SLList(int x) {
        sentinel = new IntNode(-1, null);
        sentinel.next = new IntNode(x, null);
        size = 1;
    }

    public void addFirst(int x) {
        sentinel.next = new IntNode(x, sentinel.next);
        size += 1;
    }

    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 += 1;
    }

    public int size() {
        return size;
    }
}

其中的不变量 invariants 有：

sentinel 总是指向一个 sentinel 节点
第一个节点永远是 sentinel
size 变量永远是元素总数

DLLists 双向链表、Array 数组、Generic 泛型

双向链表 DLLists

解决特殊情况的方法：

在链表末端也加入一个哨兵；
使用循环链表

泛型 Generic

在类名称后面添加 <Type_name>，在把相应的类型名改为 Type_name，但注意在声明时要指定类型名，如 SLList<String> L = new SLList<String>("hello");

声明或实例化时，使用引用类型： int→Integer、double→Double、char→Character、boolean→Boolean、long→Long

数组 Array

有以下几种实例化方法：

x = new int[3];
y = new int[]{1,2,3,4,5};
int []z = {7,8,9};

和类一样，x=y 表示 x 更改为 y 的引用，数组复制为：

System.arraycopy(b, 0, x, 3, 2)从 b[0] 开始复制 2 个元素到 x[3] 及其后面

多维数组：int[][] matrix = new int[4][4];

AList

Alist 是用数组重设大小实现的快速访问其中某个元素的动态数组

public class AList<Item_type> {
    private Item_type[] items;
    private int size;

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

    private void resize(int capacity) {
        Item_type[] a = (Item_type[]) new Object[capacity];// 不允许泛型数组，只能先创造一个对象，再强制转化为Item_type
        System.arraycopy(items, 0, a, 0, size);
        items = a;
    }

    public void addLast(Item_type x) {
        if (size == items.length)
            resize(size * 2);// 当数组存满时倍增大小
        items[size] = x;
        size += 1;
    }

    public Item_type removeLast() {
        Item_type x = getLast();
        size -= 1;
        return x;
    }

    public Item_type deleteLast() {
        Item_type returnItem = getLast();
        items[size - 1] = null; // 当一个对象失去最后一个引用时，会被当作垃圾收集并释放内存
        size -= 1;
        return returnItem;
    }

    public Item_type getLast() {
        return items[size - 1];
    }

    public Item_type get(int i) {
        return items[i];
    }

    public int size() {
        return size;
    }
}

继承 Inheritance

签名 signature指函数名和参数等

覆盖 overriding是说子类和父类有一样签名的方法

重载 overloading是说有相同名字但不同签名的方法

public interface Animal {
    public void makenoise();
}
public class Pig implements Animal {

    // 这是覆盖 overriding
    @Override //可加可不加，但加了有利于查错
    public void makenoise() {
        System.out.println("onik");
    }

    // 这是重载 overloading
    public void makenoise(Pig a) {
        System.out.println("oniks");
    }
}

接口继承 Interface Inheritance 和实现继承 Implement Inheritance

public interface List<Item_type> {

    /* 以下这些是接口继承 Interface Inheritance： */
    public void addLast(Item_type x);

    public int size();

    public Item_type getFirst();

    public Item_type get(int i);

    /* 这是实现继承 Implement Inheritance： */
    default public void print() {
        for (int i = 0; i < size(); i++) {
            System.out.print(get(i) + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        List<Integer> L1 = new SLList<Integer>();// 可以用子类的实例化
        L1.addLast(10);
        L1.addLast(11);
        L1.addLast(12);
        L1.print();

        List<Integer> L2 = new AList<Integer>();
        L2.addLast(10);
        L2.addLast(11);
        L2.addLast(12);
        L2.print(); // Alist中没有print()，却能使用
    }
}

public class SLList<Item_type> implements List<Item_type> {

    /*此处省略大量代码*/

    // 因为SLList的特殊性，使用List中的print()方法效率低下，所以重载
    @Override
    public void print() {
        IntNode p = sentinel.next;
        while (p != null) {
            System.out.print(p.item + " ");
            p = p.next;
        }
        System.out.println();
    }
}

实现继承破坏了封装 Encapsulation

静态类型 Static Type 和动态类型 Dynamic Type

静态类型 Static Type：变量声明时的类型，永不改变；

动态类型 Dynamic Type：运行时的类型，由实例化时和=赋值时决定

代码在编译时使用静态类型，在运行时使用动态类型

public interface Animal {
    default void greet (Animal a) {
        print("hello animal");
    }
    default void sniff (Animal a) {
        print("sniff animal");
    }
    default void praise (Animal a) {
        print("cool animal");
    }
}
public class Dog implements Animal {
    @Override
    void sniff(Animal a) {
        print("dog sniff animal");
    }
    void praise(Dog a) {
        print("cool dog");
    }
}

Animal a = new Dog();
Dog d = new Dog();

代码	编译的接口	运行
`a.greet(d);`	`greet(Animal a)`	`"hello animal"`
`a.sniff(d);`	`sniff(Animal a)`	`"dog sniff animal"`
`d.praise(d);`	`praise(Dog a)`	`"cool dog"`
`a.praise(d);`	`praise(Animal a)`	`"cool animal"`

Java 中已经有了list，ArrayList、LinkedList等都是其一种实现形式

java.util.List<Integer> L = new java.util.ArrayList<>();
L.add(5);
L.add(6);
L.add(7);
System.out.print(L);

延伸 Extend

public class RotatingSLList<Item_type> extends SLList<Item_type> {
    public void rotate() {
        Item_type oldBack = removeLast();
        addFirst(oldBack);
    }

    public static void main(String[] args) {
        RotatingSLList<Integer> L = new RotatingSLList<>();
        L.addLast(10);
        L.addLast(11);
        L.addLast(12);
        L.rotate();
        L.print();
    }
}

其中RotatingSLList拥有父类SLList的所有成员，并增加了rotate

public class VengefulSLList<Item_type> extends SLList<Item_type> {
    private SLList<Item_type> deletedItems;

    public VengefulSLList() {
        // super();可加可不加，若不加，默认先执行超类的constructor
        deletedItems = new SLList<Item_type>();
    }

    @Override
    public Item_type removeLast() {
        Item_type oldBack = super.removeLast(); // 使用超类的removeLast()
        deletedItems.addLast(oldBack);
        return oldBack;
    }
}

Java 中每一个类型都是 Object 的子孙 descendant，都有equal()、toString()等成员函数

高阶函数 Higher Order Function

可以使用一个类来实现：

public interface IntUnaryFunction {
    int apply(int x);
}
public class TenX implements IntUnaryFunction {

    // 返回10 * x
    public int apply(int x) {
        return 10 * x;
    }
}
public class HigherOrderFunction {
    public static int do_twice(IntUnaryFunction f, int x) {
        return f.apply(f.apply(x));
    }

    public static void main(String[] args) {
        IntUnaryFunction tenX = new TenX();
        System.out.print(do_twice(tenX, 2));
    }
}

显性实现：

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

子类型多态 Subtype Polymorphism实现：

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

类似的，在 Java 中，使用一个接口类来实现：

/* 提供一个接口 */
public interface Comparable<T> {
    public int compareTo(T obj);
}

public class Dog implements Comparable<Dog> {
    private String name;
    public int size;

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

    // 重载Dog类型的实现
    public int compareTo(Dog other) {
        return size - other.size;
    }
}

//调用通用手段
public class Maximizer {
    public static Comparable max(Comparable[] items) {
        int maxDex = 0;
        for (int i = 0; i < items.length; i += 1)
            if (items[i].compareTo(items[maxDex]) > 0)
                maxDex = i;
        return items[maxDex];
    }
}

//可以使用
public class DogLauncher {
    public static void main(String[] args) {
        Dog d1 = new Dog("aaa", 16);
        Dog d2 = new Dog("ezsu", 19);
        Dog d3 = new Dog("iu", 6);
        Dog[] dogs = new Dog[] { d1, d2, d3 };
        Dog d = (Dog) Maximizer.max(dogs);
        System.out.println(d.size);
    }
}

也可以使用内置的Comparator：

import java.util.Comparator;

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

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

    public int compareTo(Dog other) {
        return size - other.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();
    }
}

public class DogLauncher {
    public static void main(String[] args) {
        Dog d1 = new Dog("aaa", 16);
        Dog d2 = new Dog("ezsu", 19);

        Comparator<Dog> nc = Dog.getNameComparator();
        if (nc.compare(d1, d2) > 0)
            System.out.println(d1.name);
        else
            System.out.println(d2.name);
    }
}

异常 Exceptions、迭代器 Iterators 和特殊对象方法

Set<Integer> javaset = new HashSet<>();
javaset.add(256);
javaset.add(42);
javaset.add(378);

for (int i : javaset)
    System.out.println(i);
// 实质为迭代器
Iterator<Integer> seer = javaset.iterator();
while (seer.hasNext())
    System.out.println(seer.next());


// import java.util.ArrayList;
import java.util.Iterator;
// import java.util.List;

public class ArraySet<T> implements Iterable<T> { // 注意要引入接口Iterable
    private T[] items;
    private int size;

    public ArraySet() {
        items = (T[]) new Object[100];
        size = 0;
    }

    public static <T> ArraySet<T> of(T... stuff) { // ...表示任意数量的元素
        ArraySet<T> returnSet = new ArraySet<>();
        for (T x : stuff)
            returnSet.add(x);
        return returnSet;
    }

    public boolean contains(T x) {
        for (int i = 0; i < size; i += 1)
            if (x.equals(items[i]))
                return true;
        return false;
    }

    public void add(T x) {
        if (x == null) {
            throw new IllegalArgumentException("无法添加null到ArraySet中"); // 对输入null的抛出异常
        }
        if (contains(x))
            return;
        items[size] = x;
        size += 1;
    }

    public int size() {
        return size;
    }

    // 用与之前NameCompare相似的方法实现
    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;
        }
    }

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

    @Override
    public String toString() {
        // 对于字符串s，s += 某个字符串 的速度很慢（实质为复制和重建），所以改用StringBuilder
        StringBuilder returnString = new StringBuilder("{");
        for (int i = 0; i < size - 1; i += 1) {
            returnString.append(items[i].toString());
            returnString.append(", ");
        }
        returnString.append(items[size - 1].toString());
        returnString.append("}");
        return returnString.toString();

        /*
         * 还有一种类似于Python中join函数的简便方法
         * List<String> listOfItems = new ArrayList<>();
         * for (T x : this)
         * listOfItems.add(x.toString());
         * return String.join(", ", listOfItems);
         */
    }

    @Override
    public boolean equals(Object other) { // 注意接口是 Object other
        if (other == null)
            return false;
        if (this == other) // 对自身相等的优化
            return true;
        if (other.getClass() != getClass())
            return false;
        ArraySet<T> o = (ArraySet<T>) other;
        if (o.size != size) // 对于大小不同的集合的优化
            return false;
        for (T item : this)
            if (!o.contains(item))
                return false;
        return true;
    }

    public static void main(String[] args) {
        ArraySet<Integer> s = new ArraySet<>();
        s.add(256);
        s.add(42);
        s.add(378);

        ArraySet<Integer> s2 = ArraySet.of(378, 42, 256);
        s2.add(256);
        s2.add(42);
        s2.add(378);

        for (int i : s) // 可以使用缩写了
            System.out.println(i);

        System.out.println(s);// 自动调用toString()方法

        System.out.println(s.equals(1));
        System.out.println(s.equals(s2));
    }
}

Project 2: Gitlet

这是我写过的最长的代码，总共 1153 行；这也是我看过的最长的英语文档，光是说明就有 14181 个词；这也是我收获最大的项目，在 CS61A 中，我所做的工作不过是在已经基本完成的项目代码上添加一些东西，而且这些东西的具体实现方法都已经有了详细的说明，那时，我就一直想知道自己什么时候才能独立完成像那样的项目，而在 CS61B 的这个 project 中，我做到了。

从对整个问题的一脸茫然，到摸索其中的基本原理，再到写设计文档时的混乱思绪，再到写代码时一行行地改进、一遍遍地调试，再到反复阅读要求考虑特殊情况和算法效率，最后完成对代码的优化。这一个 project 带给我的好处远远不止于此。

先附上成就感满满的满分截图：

![满分！][1]

类与数据结构

Main

程序的切入点，接收命令行的参数并相应地调用 Repository 中的函数，并检查参数是否能正确调用函数，该类仅仅起到检查参数并调用对应函数的效果
Repository

程序的主要部分，实现了命令行要求的功能、维护持久化、添加错误信息等

该类将所有对文件的具体逻辑阻隔到 Blob 中
- public static final File CWD = new File(System.getProperty("user.dir")); 当前工作目录，对于其它的文件对象很有用
- public static final File GITLET_DIR = join(CWD, ".gitlet"); 隐藏的 .gitlet 目录，当前所有对文件的维护都是在此目录中进行的
- public static final File LOCAL_GITLET_DIR = join(CWD, ".gitlet"); 与前面的类似，但是在处理远程操作时，需要使用这个作为本地的工作目录
- private static final Stage STAGE = new Stage(); 暂存区的实例，用于维护其中的文件
这些域都是静态的，因为我不需要实例化 Repository 类，该类仅仅适用于存放函数
Blob

该类代表储存在文件中的每个 blob，因为每个 blob 都有一个独特的 sha1，就使用它来当作对象序列化的文件名称
- static final File BLOBS_FOLDER = join(Repository.GITLET_DIR, "blobs");序列化后的 blob 储存的位置，因为所有 blob 都存在同一个地方，所以是static的
- private final byte[] contentsblob 储存的内容
- private final String blobIdblob 的 id，这些 id 是独特的
Commit

此类代表储存在文件中的每个 commit 信息，因为每个 commit 都有一个独特的 sha1，用其当作序列化的文件名称
- static final File COMMIT_FOLDER = join(Repository.GITLET_DIR, "commits");序列化后的 commit 储存的位置，因为所有 commit 都存在同一个地方，所以是static的
- private final String message commit 信息
- private final Date timestamp commit 的时间
- private final String commitId commit 的 id，这些 id 是独特的
- private final String firstParentId commit 的第一个父亲的 id
- private final String secondParentId commit 第二个父亲的 id，只有 merge 后的 commit 有
- private HashMap<String, String> blobs commit 中储存的 blob 名字映射到 blobId，便于查找文件名对应的文件
Stage

用于维护 add 和 rm 等操作的暂存区
- protected TreeMap<String, String> stagedFiles; 暂存的文件列表
- protected TreeSet<String> removedFiles; 被移除的文件的文件名
- public static final File STAGING_AREA = join(GITLET_DIR, "staging area"); 暂存文件所在文件夹
- public static final File STAGE_FILE = join(GITLET_DIR, "stage"); 存放暂存文件信息的文件路径
Branch

维护对分支的添加、删除和持久化的类
- protected static File HEADS_FOLDER = join(GITLET_DIR, "heads"); 存放各 branch 的 HEADs 的文件夹
- protected static File CURRENT_BRANCH = join(GITLET_DIR, "current branch"); 存放当前 branch 名称的文件
这些域都是静态的，因为我不需要实例化 Branch 类，该类仅仅适用于存放函数
Remote

维护对远程仓库的添加、删除和持久化的类
- public static final File REMOTE_FOLDER = join(LOCAL_GITLET_DIR, "remote"); 存放远程 gitlet 路径的文件夹
这些域都是静态的，因为我不需要实例化 Remote 类，该类仅仅适用于存放函数
Utils

题目提供的类，包含了有用的序列化操作
- static final int UID_LENGTH = 40 SHA-1 的 16 进制长度，用于检查是否合法
GitletException

通用化 gitlet 中的错误

算法

![merge操作的几种情况汇总][2]

merge 操作是公认的最为困难的操作了，情况非常复杂，分成几个部分

在查找 splitPoint 时，通过维护两个 commit 的所有祖先节点信息（包括 commitId 和同该 commit 的距离），搜索两者的祖先中共同的祖先，且其与两者的距离之和最小，则该祖先为最近公共祖先，即 splitPoint ，此算法满足时间复杂度要求

持久化

目录结构如下：

.gitlet <==== 所有持久化数据都存储在此
- blobs <==== 所有的 blob 都存在这个目录
  - blobId1 <==== 每个单独的 blob 实例
  - blobId2
  - ...
  - blobIdN
- commits <==== 所有的 commit 都存在这个目录
  - commitId1 <==== 每个单独的 commit 实例
  - commitId2
  - ...
  - commitIdN
- heads <==== 所有的头指针都存在这个目录
  - master <==== 每个分支的 head 实例
- staging area <==== 所有 add 操作添加还没有 commit 的 blob 都暂存在这个目录
  - blobId1 <==== 每个单独的 blob 实例
  - blobId2
  - ...
  - blobIdN
- remote <==== 所有的远程仓库的位置都记录在这个目录
  - origin <==== 每个远程仓库的位置

init
- Repository 类将会创建这些文件夹：.gitlet、.commits、.blobs、heads、remote
- Commit 类将会创建第一个节点并序列化写入到名称为 commitId 的文件中
- Branch
  - 创建主分支文件，并将第一个 commit 的 commitId 写入到该文件中
  - 创建当前分支文件，并将主分支名称写入到该分支文件中
add [file name]
- 如果该文件和当前 commit 中的文件相同：
  - 若 staging area 中没有该文件，无事发生
  - 若 staging area 中有该文件，删除该文件
- 若不同，则添加该文件到 staging area 中
commit [message]
- 将 staging area 中的文件移动到 blobs 中
- 创建一个新的 commit
- 将 commitId 写入到当前分支的文件中
rm [file name]
- 如果 staging area 中有该文件，则移除该文件
- 如果该文件存在于当前目录中，则删除该文件
checkout -- [file name] 和 checkout [commit id] -- [file name]

从 commit 处获取文件的 blob，并将该 blob 中的内容复制到指定文件中
checkout [branch name]

类似，但是恢复 commit 中的所有文件
branch [branch name]
- Branch 类中创建该分支文件
- 将当前 commit 的 commitId 写入到该文件中
rm-branch [branch name]

Branch 类中删除该分支文件
reset [commit id]

类似于 checkout [branch name] 的操作，但多了一步向当前分支的文件中写入 commitId
merge [branch name]

情况很复杂，不再赘述
add-remote [remote name] [name of remote directory]/.gitlet

Remote 类创建 remote name 的文件，并将目录写入其中
rm-remote [remote name]

Remote 类删除 remote name 的文件
push [remote name] [remote branch name]
- 将本地 gitlet 的所有 commit 文件都复制到远程仓库所在目录中
- 向远程仓库的当前分支的文件中写入最新的 commitId
fetch [remote name] [remote branch name]
- 将远程 gitlet 的所有 commit 和 blob 文件都复制到本地仓库
- 新建名称为 [remote name]-[remote branch name] 的分支文件
- 向该文件中写入远程仓库的最新的 commitId
pull [remote name] [remote branch name]

同 fetch + merge 操作