Java

测试 如何知道自己的程序是否真的在工作？在现实世界中，程序员相信他们的代码，因为代码通过了他们自己编写的测试。常用的测试有 Ad Hoc Testing， Unit test 和 Integration Testing。 Ad Hoc Testing，是指没有计划和记录的软件测试，除非发现缺陷，不然一般只运行一次。 Unit test 程序可分解为单元（或程序中可测试的最小部分），Unit test 严格测试代码的每个单元，最终确保项目正确运行。 Unit test 好处： Unit test 保证良好的代码结构（每个 method “只打一份工”），帮助我们较好地解析任务， 允许我们考虑每个方法的所有边界情况，并单独测试它们。 让我们每次只专注于一个单元，进行测试，debug，对准确度有信心后，再进行下一个单元的开发。相比于一次性写完所有代码，再测试debug，Unit test 减少了 debugging 时间。 坏处： 测试也要花时间 测试本身也是有可能出错的，测试可能不全面，不规范，或者有bug 有些单元是依赖于其他单元的 Unit testing 无法保证各个模块的交互，无法保证整个系统作为一个整体是否正常工作。 JUnit JUnit是一个给Java做测试的框架，由Erich Gamma（Design Patterns）和Kent Beck（eXtreme Programming）编写。 JUnit使用Java的 reflection 功能（Java程序可以检查自己的代码）和注释。 JUnit允许我们： 定义并执行测试和测试套件 使用测试作为规范的有效手段 使用测试来支持重构 将修改的代码集成到构建中 JUnit可用于多个IDE，例如BlueJ，JBuilder和Eclipse在一定程度上具有JUnit集成。 import org.junit.Test; import static org.junit.Assert.*; @Test public void testMethod() { assertEquals(<expected>, <actual>); } assertEquals测试一个变量的实际值是否等于它的期望值。 JUnit test 各个测试方法，必须是非静态的（JUnit的设计人员设计规定的）。 ...

Java 提供了 ArrayList, ArrayDeque 和 LinkedList 几个API. 队列 queue, 通俗的含义, 就是不能插队, 只能在末尾插入. 双端队列 Double Ended Queue (Deque) 是具有动态大小的序列容器，可以在两端（前端或后端）扩展或收缩 –http://www.cplusplus.com/reference/deque/deque/ CS61b的project 1a需要实现两种双端队列（array based 和 linkedklist based）. 不同的API, 在考虑什么时候应该用哪个时, 我们需要考虑它们的性能差异: 搜索/定位：与LinkedList相比，ArrayList搜索更快。 ArrayList的get(int index)性能是O(1)的，而LinkedList的性能是O(n)。因为ArrayList基于array数据结构，可以直接用 array index 定位元素。 删除/插入：LinkedList 操作性能是O(1)，而ArrayList的性能从O(n)（删除/插入第一个元素）到O(n)（最后一个元素）都有可能。因为LinkedList的每个元素都包含两个指向其相邻前后元素的指针（地址），因此仅需要改变，被删节点的prev和next指针位置。而在ArrayList中，需要移动剩余元素，来重新填充array空间。 内存开销：LinkedList的每个元素都有更多的内存开销(额外的指针), 而ArrayLists没有这个开销。但是，ArrayLists需要占用初始容量。一般ArrayList的默认初始容量非常小（Java 1.4 - 1.8使用10）。但是，往ArrayLists添加元素时， 它可能会适当地增大容量，所以如果添加了很多元素，则必须不断调整数组的大小，那样也可能会导致元素频繁挪动位置。 综上所述： 如果在应用中需要频繁插入和删除，那么选择LinkedList。 假如一开始，就知道后面要添加大量元素，那就使用较高的初始容量来构造ArrayList。 大部分用例中, 相比LinkedList, 人们更偏爱ArrayList以及ArrayDeque。如果你不确定应该选哪个, 那么就直接考虑ArrayList吧(参考 https://stackoverflow.com/questions/322715/when-to-use-linkedlist-over-arraylist).

双向链表 Doubly Linked List 前面介绍过的单向链表有几个缺点. 第一个就是它的addLast操作非常慢。单向链表只有一个变量保存列表头的地址, 以及每个节点对后面节点的单向引用(链接). 对于很长的列表，addLast方法必须遍历整个列表, 直到找到列表末尾才能执行插入操作. 最直观的优化方案就是加个’车尾’ 这样我们就可以直接通过last.next引用末尾位置. 不过另一个问题并没有解决, 就是删除列表最后一项removeLast这个操作还是很慢。因为在目前的结构设计下, 我们需要先找到倒数第二项，然后将其下一个指针设置为null。而要找到倒数第二节点, 我们就得先找到倒数第三个节点…… 以此类推。也就是说，对于删除末尾的操作，还是要几乎遍历整个列表。 反方向的链接 基于前面单向链表构建双向链表, 一个比较有效的方法是额外为每个节点添加一个指向前面节点的链接 - 指针. public class OneNode { public OneNode prev; //指向前 public int item; public OneNode next; //指向后 } 增加这些额外的指针会导致额外的代码复杂度, 以及额外的内存开销, 这就是追求时间效率的代价. Sentinel 与尾节点 双向链表的一个设计初衷，就是为了解决单向链表针对列表末尾位置的操作效率不高的问题，除了sentinel和反方向的链接还不够，我们还需要一个节点（指针）能够直接帮我们定位到列表末端。可以考虑添加一个的尾节点last 这样的列表就可以支持O(1)复杂度的addLast,getLast 和 removeLast操作了。 循环双端队列 Circular double ended queue 上面的尾节点设计虽然没什么错误，但有点瑕疵：最后一个尾节点指针有时指向前哨节点，有时指向一个真正的节点。更好的方法是使双向链表首尾相连, 构成一个循环，即前后节点共享唯一的一个前哨节点。 这样的设计相对更整洁，更美观(主观上的), sentinel的prev就指向列表最后一个节点, sentinel的next指向列表第一个节点. ...

链表 Linked List 前面有介绍以array为基础搭建的列表，支持自动扩容, 各种插入，删除速度都很快. 这里再介绍另一种方案, 链表, 也可以实现列表自动扩容. 带链接的节点 链表的核心组成是带链接的节点, 每个节点就像火车车厢, 有钩子连接下一节车厢. 以int节点为例: public class IntNode { public int item; public IntNode next; public IntNode(int i, IntNode n) { item = i; next = n; } } next就是这个链接, 每一个节点就是其上一个节点的next. 使用嵌套类 这个节点作为一个相对独立的数据结构, 我们更希望让他单独作为一个类来维护. 再另外创建一个名为LinkedList的class与用户进行交互. 这样还有另一个好处就是提供一个命名为LinkedList的类给用户交互，用户更直观地知道自己是在调用链表。如果直接与node类交互，用户可能会困扰. 但同时考虑到这个node类只有LinkedList会调用，所以我们可以把node类嵌套进LinkedList中。 public class LinkedList<XXX> { private class OneNode { public XXX item; public OneNode next; public OneNode(XXX i, OneNode n) { item = i; next = n; } } private OneNode first; private int size; public LinkedList(XXX x) { first = new OneNode(x, null); size = 1; } //下面是各种方法... } 以上定义使用了泛型。声明OneNode实例first为私有变量, 是为了防止用户错误地摆弄链接指向，private和public的使用参考. ...

列表 List 前面说到Java的数组无法更改长度，那么也就无法实现插入或者删除数组成员。Java提供了功能更丰富的数据结构 - 列表（list）。所谓列表，即有序的集合（序列），用户可以精确地控制每个元素插入到列表中的哪个位置。用户可以通过整数索引（列表中的位置）来访问元素，并搜索列表中的元素（详细可进一步参考oracle官网）。 这里我们尝试以java的array为基础实现一个列表，目标是实现自动扩容 (Java中的ArrayList不仅仅有自动扩容, 也继承了[List]的其他功能)。在探索的过程中, 可以顺带学习很多相关的内容. 使用自上而下的设计思想搭建一个框架: 先写出最基础的部分, 也就是一个构造器，前面学过了整数数组，我们直接拿来用 /** Array based list. */ // index 0 1 2 3 4 5 6 7 // items: [6 9 -1 2 0 0 0 0 ...] // size: 5 public class AList { private int[] items; private int size; /** 构造一个初始容量100的数组，初始有效数据成员为0. */ public AList() { items = new int[100]; size = 0; } /** 下面添加其他方法 */ } 然后思考我们需要什么功能，把功能需求转化为实例方法instance method的形式，先把方法的外壳描绘出来，注释上该方法的功能（目的），输入值，返回值是什么之类的。具体的功能实现可以先空着，之后一步步丰富。 ...

数组（Array） 数组是一种特殊的对象，有一个固定的数组长度参数N，由一连串（N个）连续的带编号的内存块组成，每个都是相同的类型(不像Python可以包含不同类型)，索引从0到N-1编号。A[i]获得数组A的第i个元素。这与普通的类实例不同，类实例有具体变量名命名的内存块。 数组实例化，包含对象的数组 Array Instantiation, Arrays of Objects 要创建最简单的整数数组, 有三种方式: x = new int [3]; //创建一个指定长度的数组，并用默认值（0）填充每个内存块。 y = new int [] {1，2，3，4，5}; //创建一个合适大小的数组，以容纳指定的初始值 int [] z = {9，10，11，12，13}; //省略了new，只能结合变量声明使用。 创建一组实例化对象: public class DogArrayDemo { public static void main(String[] args) { /* Create an array of two dogs. */ Dog[] dogs = new Dog[2]; dogs[0] = new Dog(8); dogs[1] = new Dog(20); /* Yipping will result, since dogs[0] has weight 8. */ dogs[0].makeNoise(); } } 注意到new有两种不同的使用方式：一种是创建一个可以容纳两个Dog对象的数组，另外两个创建各个实际的Dog实例。 ...

数据类型 数据类型是程序设计语言描述事物、对象的方法。Java数据类型分为基本类型（内置类型）和引用类型(扩展类型）两大类。基本类型就是Java语言本身提供的基本数据类型，比如，整型数，浮点数，字符，布尔值等等。而引用类型则是Java语言根据基本类型扩展出的其他类型，Java要求所有的引用扩展类型都必须包括在类定义里面，这就是Java为什么是面向对象编程语言的原因… 上面的定义有点抽象，要理解数据类型，需要先理解一个问题: 神秘的海象问题 尝试预测下面的代码运行时会发生什么。b的变化是否会影响a？提示：类似Python。 Walrus a = new Walrus(1000, 8.3); Walrus b; b = a; b.weight = 5; System.out.println(a); System.out.println(b); 同样尝试预测下面的代码运行时会发生什么。x的改变是否影响y？ int x = 5; int y; y = x; x = 2; System.out.println("x is: " + x); System.out.println("y is: " + y); 答案是b的变化会影响a, 但x的改变不影响y，具体见可视化过程. 这里的差别虽然微妙, 但其背后的原理对于数据结构的效率来说是非常重要的，对这个问题的深入理解也将引导我们写出更安全，更可靠的代码。 基本类型 Primative Types 计算机中的所有信息都以一系列1和0的形式存储在内存中，这些二进制的0和1就是比特位（bits）。比如72和“H”在内存一般以01001000的形式存储，对他们的形式是一样的。一个引申问题就是：Java代码如何解释01001000，怎么知道应该解释为72还是“H”？ 通过类型types，预先定义好类型即可, 以下代码 char x = 'H'; int y = x; System.out.println(x); System.out.println(y); 会分别得到“H”和72. 在这种情况下，x和y变量都包含几乎相同的bits，但是Java解释器在输出时对它们进行了不同的处理。 Java有8种基本类型：byte，short，int，long，float，double，boolean和char。 ...

嵌套类 我们经常需要在某个类A中使用另一个类B，如果设计时我们知道类B只有在类A中有被使用的可能性, 那么我们可以把类B定义在类A中, 作为类A的嵌套类, 类A就称之为外部类. 这样做可以隐藏类名，减少全局的标识符，从而限制用户能否使用该类建立对象。这样可以提高类的抽象能力，并且强调了两个类(外围类和嵌套类)之间的主从关系。 A nested class is any class whose declaration occurs within the body of another class or interface. A top level class is a class that is not a nested class. 嵌套类分为两类：静态和非静态。声明为static的嵌套类简称为静态嵌套类。非静态嵌套类称为内部类(inner class)。 class OuterClass { ... static class StaticNestedClass { ... } class InnerClass { ... } } 作为OuterClass的成员，嵌套类可以声明为private，public，protected或package private。外部类只能声明为public或package private。更多详情参考官网. 内部类 内部类可以直接访问外部类的方法和变量(即使是private的也可以)。如果从外部类程序代码中初始化内部类, 此内部对象会绑在该外部对象上. 一个内部类的实例作为成员存在于所属外部类的实例中。 public class Outer { private int outVar; class Inner { public int inVar; void go() { outVar += inVar; } } Inner myInner = new Inner(); public void do() { myInner.go(); } } public static void main(String[] args) { Outer O = new Outer(); Outer.Inner I = O.new Inner(); } 也可以从外部类之外的程序来初始化外部类的内部实例, 语法比较特殊 ...

Class 类的方法和变量细分为静态的和非静态的. 静态就是可以被类调用，所以静态方法/变量也称之为类方法/变量；非静态只能由实例调用，所以也称之为实例方法/变量。 静态变量 类变量 Class Variables 有static声明(静态变量). 静态变量一般是类本身固有的属性, 被该类所有实例共享。例如，我们可能需要用狗类的另一种生物学的统称“犬科”来作为类的说明， 这个时候可以用public static String binomen = "犬科";，这个变量理论上是由类来访问的。静态方法也类似. 以下代码定义了一个类来模拟狗，包含一个类变量作为这个类的说明，一个类方法用于发出叫声： public class Dog { public static String instruction = "狗类实例"; //类变量, 说明 public static void makeNoise() { System.out.println("汪!"); } } 这里没有定义main(), 在这种情况下如何直接运行这个类(java Dog), 程序是会报错的 错误: 在类 Dog 中找不到 main 方法, 请将 main 方法定义为: public static void main(String[] args) 否则 JavaFX 应用程序类必须扩展javafx.application.Application. 你可以选择在里面添加一个main()方法. 但这次我们选择不定义具体的main(). 具体要如何运行, 我们可以另写一个类定义一个main()方法来调用这个类. ...

Class Java的语法是为了更容易地模拟真实世界而设计的. 比如用程序实现一只狗, 可以用定义一个类class来描述它. 类class里面包括变量Variable，方法method（可以理解为Python的函数function）。变量可以储存数据，方法可以处理数据。变量必须在类中声明(即不能离开类独立存在)，不像Python或Matlab这样的语言可以在运行时添加新的变量。 构造对象的过程: 声明(declaration)引用变量: Dog smalldog; 创建对象：实例化 new Dog(20), 如果没有把它作为值赋给一个类声明变量, 那么这个实例化的值会被垃圾回收. 连接对象和引用：赋值对象给引用Dog smalldog = new Dog(5) 创建对象这一步，调用了Dog(), 不是普通的方法, 而是类的构造函数 Constructors. 构造函数 构造函数在初始化一个对象时执行, 构造函数与类名同名且没有返回类型, 而且可以带参数： /** 注意：构造函数与class类同名 但没有返回类型 */ public Dog(int w) { weight = w; } 然后在DogLauncher里实例化一只狗时, 直接Dog d = new Dog(20);即可. 在以上代码的基础上, 后续当我们想使用new和参数创建一只狗时，可以随时调用public Dog(int w)构造函数。对于熟悉Python的人来说，你可以理解java的构造函数为Python的__init__。 Java可以有与类同名的方法，只是要指明返回类型。 构造函数无法被继承 如果类有一个以上的构造函数，则参数一定要不一样，包括参数顺序和类型 构造函数链 执行new指令会启动构造函数的连锁反应(Constructor Chaining), 首先会执行其父类的构造函数, 依此类推连锁反应到Object类为止. 就算是抽象类, 也会有构造函数, 虽然不能被直接实例化, 但也会被唤醒. 理论上，每个类的构造函数需要先调用其父类的构造函数super()，依次入栈 public class Duck extends Animal { int size; public Duck(int newSize) { super(); // 调用父类构造函数, 且必须是在函数中的第一行 size = newSize; } } 如果明确写了super();, 则必须位于构造函数第一行. 但很多构造函数没有写super();也可以编译通过, 甚至连自身的构造函数public Duck(int newSize)也不一定是必须的。 ...