# 第一章 接口
> 原文：[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`？
