# 第十二章 `TreeMap` > 原文：[Chapter 12 TreeMap](http://greenteapress.com/thinkdast/html/thinkdast013.html) > 譯者：[飛龍](https://github.com/wizardforcel) > 協議：[CC BY-NC-SA 4.0](http://creativecommons.org/licenses/by-nc-sa/4.0/) > 自豪地采用[谷歌翻譯](https://translate.google.cn/) 這一章展示了二叉搜索樹，它是個`Map`接口的高效實現。如果我們想讓元素有序，它非常實用。 ## 12.1 哈希哪里不對？ 此時，你應該熟悉 Java 提供的`Map`接口和`HashMap`實現。通過使用哈希表來制作你自己的`Map`，你應該了解`HashMap`的工作原理，以及為什么我們預計其核心方法是常數時間的。 由于這種表現，`HashMap`被廣泛使用，但并不是唯一的`Map`實現。有幾個原因可能需要另一個實現： 哈希可能很慢，所以即使`HashMap`操作是常數時間，“常數”可能很大。 如果哈希函數將鍵均勻分配給子映射，效果很好。但設計良好的散列函數并不容易，如果太多的鍵在相同的子映射上，那么`HashMap`的性能可能會很差。 哈希表中的鍵不以任何特定順序存儲；實際上，當表增長并且鍵被重新排列時，順序可能會改變。對于某些應用程序，必須或至少保持鍵的順序，這很有用。 很難同時解決所有這些問題，但是 Java 提供了一個稱為`TreeMap`的實現： + 它不使用哈希函數，所以它避免了哈希的開銷和選擇哈希函數的困難。 + 在`TreeMap`之中，鍵被存儲在二叉搜索樹中，這使我們可以以線性時間順序遍歷鍵。 + 核心方法的運行時間與`log(n)`成正比，并不像常數時間那樣好，但仍然非常好。 在下一節中，我將解釋二進制搜索樹如何工作，然后你將使用它來實現`Map`。另外，使用樹實現時，我們將分析映射的核心方法的性能。 ## 12.2 二叉搜索樹 二叉搜索樹（BST）是一個樹，其中每個`node`（節點）包含一個鍵，并且每個都具有“BST 屬性”： + 如果`node`有一個左子樹，左子樹中的所有鍵都必須小于`node`的鍵。 + 如果`node`有一個右子樹，右子樹中的所有鍵都必須大于`node`的鍵。  圖 12.1：二叉搜索樹示例 圖 12.1 展示了一個具有此屬性的整數的樹。這個圖片來自二叉搜索樹的維基百科頁面，位于 <http://thinkdast.com/bst>，當你做這個練習時，你會發現它很實用。 根節點中的鍵為`8`，你可以確認根節點左邊的所有鍵小于`8`，右邊的所有鍵都更大。你還可以檢查其他節點是否具有此屬性。 在二叉搜索樹中查找一個鍵是很快的，因為我們不必搜索整個樹。從根節點開始，我們可以使用以下算法： + 將你要查找的鍵`target`，與當前節點的鍵進行比較。如果他們相等，你就完成了。 + 如果`target`小于當前鍵，搜索左子樹。如果沒有，`target`不在樹上。 + 如果`target`大于當前鍵，搜索右子樹。如果沒有，`target`不在樹上。 在樹的每一層，你只需要搜索一個子樹。例如，如果你在上圖中查找`target = 4`，則從根節點開始，它包含鍵`8`。因為`target`小于`8`，你走了左邊。因為`target`大于`3`，你走了右邊。因為`target`小于`6`，你走了左邊。然后你找到你要找的鍵。 在這個例子中，即使樹包含九個鍵，它需要四次比較來找到目標。一般來說，比較的數量與樹的高度成正比，而不是樹中的鍵的數量。 因此，我們可以計算樹的高度`h`和節點個數`n`的關系。從小的數值開始，逐漸增加： 如果`h=1`，樹只包含一個節點，那么`n=1`。 如果`h=2`，我們可以添加兩個節點，總共`n=3`。 如果`h=3`，我們可以添加多達四個節點，總共`n=7`。 如果`h=4`，我們可以添加多達八個節點，總共`n=15`。 現在你可能會看到這個規律。如果我們將樹的層數從`1`數到`n`，第`i`層可以擁有多達`2^(n-1)`個節點。`h`層的樹共有`2^h-1`個節點。如果我們有： ``` n = 2^h - 1 ``` 我們可以對兩邊取以`2`為底的對數： ``` log2(n) ≈ h ``` 意思是樹的高度正比于`logn`，如果它是滿的。也就是說，如果每一層包含最大數量的節點。 所以我們預計，我們可以以正比于`logn`的時間，在二叉搜索樹中查找節點。如果樹是慢的，即使是部分滿的，這是對的。但是并不總是對的，我們將會看到。 時間正比于`logn`的算法是對數時間的，并且屬于`O(logn)`的增長級別。 ## 12.3 練習 10 對于這個練習，你將要使用二叉搜索樹編寫`Map`接口的一個實現。 這里是實現的開頭，叫做`MyTreeMap`： ```java public class MyTreeMap<K, V> implements Map<K, V> { private int size = 0; private Node root = null; ``` 實例變量是`size`，它跟蹤了鍵的數量，以及`root`，它是樹中根節點的引用。樹為空的時候，`root`是`null`，`size`是`0`。 這里是`Node`的定義，它在`MyTreeMap`之中定義。 ```java protected class Node { public K key; public V value; public Node left = null; public Node right = null; public Node(K key, V value) { this.key = key; this.value = value; } } ``` 每個節點包含一個鍵值對，以及兩個子節點的引用，`left`和`right`。任意子節點都可以為`null`。 一些`Map`方法易于實現，比如`size`和`clear`： ```java public int size() { return size; } public void clear() { size = 0; root = null; } ``` `size`顯然是常數時間的。 `clear`也是常數時間的，但是考慮這個：當`root`賦為`null`時，垃圾收集器回收了樹中的節點，這是線性時間的。這個工作是否應該由垃圾收集器的計數來完成呢？我認為是的。 下一節中，你會填充一些其它方法，包括最重要的`get`和`set`。 ## 12.4 實現`TreeMap` 這本書的倉庫中，你將找到這些源文件： + `MyTreeMap.java`包含上一節的代碼，其中包含缺失方法的大綱。 + `MyTreeMapTest.java`包含單元`MyTreeMap`的測試。 運行`ant build`來編譯源文件。然后運行`ant MyTreeMapTest`。幾個測試應該失敗，因為你有一些工作要做！ 我已經提供了`get`和`containsKey`的大綱。他們都使用`findNode`，這是我定義的私有方法；它不是`Map`接口的一部分。以下是它的起始： ```java private Node findNode(Object target) { if (target == null) { throw new IllegalArgumentException(); } @SuppressWarnings("unchecked") Comparable<? super K> k = (Comparable<? super K>) target; // TODO: FILL THIS IN! return null; } ``` 參數`target`是我們要查找的鍵。如果`target`是`null`，`findNode`拋出異常。一些`Map`實現可以將`null`處理為一個鍵，但是在二叉搜索樹中，我們需要能夠比較鍵，所以處理`null`是有問題的。為了保持簡單，這個實現不將`null`視為鍵。 下一行顯示如何將`target`與樹中的鍵進行比較。按照`get`和`containsKey`的簽名（名稱和參數），編譯器認為`target`是一個`Object`。但是，我們需要能夠對鍵進行比較，所以我們將`target`強制轉換為`Comparable<? super K>`，這意味著它可以與類型`K`（或任何超類）的示例比較。如果你不熟悉“類型通配符”的用法，可以在 <http://thinkdast.com/gentut> 上閱讀更多內容。 幸運的是，Java 的類型系統的處理不是這個練習的重點。你的工作是填寫剩下的`findNode`。如果它發現一個包含`target`鍵的節點，它應該返回該節點。否則應該返回`null`。當你使其工作，`get`和`containsKey`的測試應該通過。 請注意，你的解決方案應該只搜索通過樹的一條路徑，因此它應該與樹的高度成正比。你不應該搜索整棵樹！ 你的下一個任務是填充`containsValue`。為了讓你起步，我提供了一個輔助方法`equals`，比較`target`和給定的鍵。請注意，樹中的值（與鍵相反）不一定是可比較的，所以我們不能使用`compareTo`；我們必須在`target`上調用`equals`。 不像你以前的`findNode`解決方案，你的`containsValue`解決方案應該搜索整個樹，所以它的運行時間正比于鍵的數量`n`，而不是樹的高度`h`。 > 譯者注：這里你可能想使用之前講過的 DFS 迭代器。 你應該填充的下一個方法是`put`。我提供了處理簡單情況的起始代碼： ```java public V put(K key, V value) { if (key == null) { throw new IllegalArgumentException(); } if (root == null) { root = new Node(key, value); size++; return null; } return putHelper(root, key, value); } private V putHelper(Node node, K key, V value) { // TODO: Fill this in. } ``` 如果你嘗試將`null`作為關鍵字，`put`則會拋出異常。 如果樹為空，則`put`創建一個新節點并初始化實例變量`root`。 否則，它調用`putHelper`，這是我定義的私有方法；它不是`Map`接口的一部分。 填寫`putHelper`，讓它搜索樹，以及： + 如果`key`已經在樹中，它將使用新值替換舊值，并返回舊值。 + 如果`key`不在樹中，它將創建一個新節點，找到正確的添加位置，并返回`null`。 你的`put`實現的是時間應該與樹的高度`h`成正比，而不是元素的數量`n`。理想情況下，你只需搜索一次樹，但如果你發現兩次更容易搜索，可以這樣做：它會慢一些，但不會改變增長級別。 最后，你應該填充`keySet`。根據 <http://thinkdast.com/mapkeyset> 的文檔，該方法應該返回一個`Set`，可以按順序迭代鍵；也就是說，按照`compareTo`方法，升序迭代。我們在 8.3 節中使用的`HashSet`實現不會維護鍵的順序，但`LinkedHashSet`實現可以。你可以閱讀 <http://thinkdast.com/linkedhashset>。 我提供了一個`keySet`的大綱，創建并返回`LinkedHashSet`： ``` public Set<K> keySet() { Set<K> set = new LinkedHashSet<K>(); return set; } ``` 你應該完成此方法，使其以升序向`set`添加樹中的鍵。提示：你可能想編寫一個輔助程序；你可能想讓它遞歸；你也可能想要閱讀 <http://thinkdast.com/inorder> 上的樹的中序遍歷。 當你完成時，所有測試都應該通過。下一章中，我會講解我的解法，并測試核心方法的性能。