前言
第二章 算法分析

数据结构思维

第一章 接口

原文：Chapter 1 Interfaces

译者：飞龙

协议：CC BY-NC-SA 4.0

自豪地采用谷歌翻译

本书展示了三个话题：

  • 数据结构：从 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：

public interface Comparable<T> {
    public int compareTo(T o);
}

这个interface的定义使用类型参数T，这使得Comparable是个泛型类型。为了实现这个interface，一个类必须：

  • 规定类型T，以及，
  • 提供一个名为compareTo的方法，接受一个对象作为参数，并返回int。

例如，以下是java.lang.Integer的源代码：

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>的文档，不必要这么复杂，直接返回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的其它任何对象。

这是一个人为的示例，展示了这一点：

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？

书籍推荐