# 第一章 接口
> 原文：[Chapter 1 Interfaces](http://greenteapress.com/thinkdast/html/thinkdast002.html)
> 译者：[飞龙](https://github.com/wizardforcel)
> 协议：[CC BY-NC-SA 4.0](http://creativecommons.org/licenses/by-nc-sa/4.0/)
> 自豪地采用[谷歌翻译](https://translate.google.cn/)
本书展示了三个话题：
+ 数据结构：从 Java 集合框架（JCF）中的结构开始，你将学习如何使用列表和映射等数据结构，你将看到它们的工作原理。
+ 算法分析：我提供了技术，来分析代码以及预测运行速度和需要多少空间（内存）。
+ 信息检索：为了激发前两个主题，并使练习更加有趣，我们将使用数据结构和算法构建简单的 Web 搜索引擎。
以下是话题顺序的大纲：
+ 我们将从`List`接口开始，你将编写实现这个接口的两种不同的方式。然后我们将你的实现与 Java `ArrayList`和`LinkedList`类进行比较。
+ 接下来，我将介绍树形数据结构，你将处理第一个应用程序：一个程序，从维基百科页面读取页面，解析内容，并遍历生成的树来查找链接和其他特性。我们将使用这些工具来测试“到达哲学”的猜想（你可以通过阅读 <http://thinkdast.com/getphil> 来了解）。
+ 我们将了解 Java 的`Map`接口和`HashMap`实现。然后，你将使用哈希表和二叉搜索树来编写实现此接口的类。
+ 最后，你将使用这些（以及其他一些我之前介绍的）类来实现一个 Web 搜索引擎，其中包括：一个查找和读取页面的爬虫程序，一个存储网页内容的索引器，以便有效地搜索，以及一个从用户那里接受查询并返回相关结果的检索器。
让我们开始吧。
## 1.1 为什么有两种`List`？
当人们开始使用 Java 集合框架时，有时候会混淆`ArrayList`和`LinkedList`。为什么 Java 提供两个`List interface`的实现呢？你应该如何选择使用哪一个？我们将在接下来的几章回答这些问题。
我将以回顾`interface`和实现它们的类开始，我将介绍“面向接口编程”的概念。
在最初的几个练习中，你将实现类似于`ArrayList`和`LinkedList`的类，这样你就会知道他们如何工作，我们会看到，他们每个类都有优点和缺点。对于`ArrayList`，一些操作更快或占用更少的空间；但对于`LinkedList`其他操作更快或空间更少。哪一个更适合于特定的应用程序，取决于它最常执行的操作。
## 1.2 Java 中的接口
Java `interface`规定了一组方法；任何实现这个`interface`的类都必须提供这些方法。例如，这里是`Comparable`的源代码，它是定义在`java.lang`包中的`interface`：
```java
public interface Comparable<T> {
public int compareTo(T o);
}
```
这个`interface`的定义使用类型参数`T`，这使得`Comparable`是个泛型类型。为了实现这个`interface`，一个类必须：
+ 规定类型`T`，以及，
+ 提供一个名为`compareTo`的方法，接受一个对象作为参数，并返回`int`。
例如，以下是`java.lang.Integer`的源代码：
```java
public final class Integer extends Number implements Comparable<Integer> {
public int compareTo(Integer anotherInteger) {
int thisVal = this.value;
int anotherVal = anotherInteger.value;
return (thisVal<anotherVal ? -1 : (thisVal==anotherVal ? 0 : 1));
}
// other methods omitted
}
```
> 译者注：根据[`Comparable<T>`的文档](http://docs.oracle.com/javase/7/docs/api/java/lang/Comparable.html#compareTo%28T%29)，不必要这么复杂，直接返回`this.value - that.value`就足够了。
这个类扩展了`Number`，所以它继承了`Number`的方法和实例变量；它实现`Comparable<Integer>`，所以它提供了一个名为`compareTo`的方法，接受`Integer`并返回一个`int`。
当一个类声明它实现一个`interface`，编译器会检查，它提供了所有`interface`定义的方法。
除此之外，这个`compareTo`的实现使用“三元运算符”，有时写作`?:`。如果你不熟悉，可以阅读 <http://thinkdast.com/ternary>。
## 1.3 `List`接口
Java集合框架（JCF）定义了一个`interface`，称为 `List`，并提供了两个实现方式，`ArrayList`和`LinkedList`。
这个`interface`定义了`List`是什么意思；实现它的任何类`interface`必须提供一组特定的方法，包括`add`，`get`， `remove`，以及其它大约 20 个。
`ArrayList`并`LinkedList`提供这些方法，因此可以互换使用。用于`List`也可用于`ArrayList`，`LinkedList`，或实现`List`的其它任何对象。
这是一个人为的示例，展示了这一点：
```java
public class ListClientExample {
private List list;
public ListClientExample() {
list = new LinkedList();
}
private List getList() {
return list;
}
public static void main(String[] args) {
ListClientExample lce = new ListClientExample();
List list = lce.getList();
System.out.println(list);
}
}
```
`ListClientExample`没有任何有用的东西，但它封装了`List`，并具有一个类的基本要素。也就是说，它包含一个`List`实例变量。我会使用这个类来表达这个要点，然后你将在第一个练习中使用它。
通过实例化（也就是创建）新的`LinkedList`，这个`ListClientExample`构造函数初始化`list`；读取器方法叫做`getList`，返回内部`List`对象的引用；并且`main`包含几行代码来测试这些方法。
这个例子的要点是，它尽可能地使用`List`，避免指定`LinkedList`，`ArrayList`，除非有必要。例如，实例变量被声明为`List`，并且`getList`返回`List`，但都不指定哪种类型的列表。
如果你改变主意并决定使用`ArrayList`，你只需要改变构造函数; 你不必进行任何其他更改。
这种风格被称为基于接口的编程，或者更随意，“面向接口编程”（见 <http://thinkdast.com/interbaseprog>）。这里我们谈论接口的一般思想，而不是 Java 接口。
当你使用库时，你的代码只依赖于类似“列表”的接口。它不应该依赖于一个特定的实现，像`ArrayList`。这样，如果将来的实现发生变化，使用它的代码仍然可以工作。
另一方面，如果接口改变，依赖于它的代码也必须改变。 这就是为什么库的开发人员避免更改接口，除非绝对有必要。
## 1.4 练习 1
因为这是第一个练习，我们会保持简单。你将从上一节获取代码并交换实现；也就是说，你会将`LinkedList`替换为`ArrayList`。因为面向接口编写程序，你将能够通过更改一行并添加一个`import`语句来交换实现。
以建立你的开发环境来开始。对于所有的练习，你需要能够编译和运行 Java 代码。我使用 JDK7 来开发示例。如果你使用的是更新的版本，则所有内容都应该仍然可以正常工作。如果你使用的是旧版本，可能会发现某些东西不兼容。
我建议使用交互式开发环境（IDE）来获取语法检查，自动完成和源代码重构。这些功能可帮助你避免错误或快速找到它们。但是，如果你正在准备技术面试，请记住，在面试期间你不会拥有这些工具，因此你也可以在没有他们的情况下练习编写代码。
如果你尚未下载本书的代码，请参阅 0.1 节中的指南。
在名为`code`的目录中，你应该找到这些文件和目录：
+ `build.xml`是一个 Ant 文件，可以更容易地编译和运行代码。
+ `lib`包含你需要的库（对于这个练习，只是 JUnit）。
+ `src`包含源代码。
如果你浏览`src/com/allendowney/thinkdast`，你将找到此练习的源代码：
+ `ListClientExample.java`包含上一节的代码。
+ `ListClientExampleTest.java`包含一个 JUnit 测试`ListClientExample`。
查看`ListClientExample`并确保你了解它的作用。然后编译并运行它。如果你使用 Ant，你可以访问代码目录并运行`ant ListClientExample`。
你可能会得到一个警告。
```
List is a raw type. References to generic type List<E>
should be parameterized.
```
为了使这个例子保持简单，我没有留意在列表中指定元素的类型。如果此警告让你烦恼，你可以通过将`List`或`LinkedList`替换为`List<Integer>`或`LinkedList<Integer>`来修复。
回顾`ListClientExampleTest`。它运行一个测试，创建一个`ListClientExample`，调用`getList`，然后检查结果是否是一个`ArrayList`。最初，这个测试会失败，因为结果是一个`LinkedList`，而不是一个`ArrayList`。运行这个测试并确认它失败。
注意：这个测试对于这个练习是有意义的，但它不是测试的一个很好的例子。良好的测试应该检查被测类是否满足接口的要求；他们不应该依赖于实现的细节。
在`ListClientExample`中，将`LinkedList`替换为`ArrayList`。你可能需要添加一个`import`语句。编译并运行`ListClientExample`。然后再次运行测试。修改了这个之后，测试现在应该通过了。
为了这个此测试通过，你只需要在构造函数中更改`LinkedList`；你不必更改任何`List`出现的地方。如果你这样做会发生什么？来吧，将一个或者多个`List`替换为`ArrayList`。程序仍然可以正常工作，但现在是“过度指定”了。如果你将来改变主意，并希望再次交换接口，则必须更改代码。
在`ListClientExample`构造函数中，如果将`ArrayList`替换为`List`，会发生什么？为什么不能实例化`List`？
