第十章哈希 · 數據結構思維中文版

# 第十章哈希 > 原文：[Chapter 10 Hashing](http://greenteapress.com/thinkdast/html/thinkdast011.html) > 譯者：[飛龍](https://github.com/wizardforcel) > 協議：[CC BY-NC-SA 4.0](http://creativecommons.org/licenses/by-nc-sa/4.0/) > 自豪地采用[谷歌翻譯](https://translate.google.cn/) 在本章中，我定義了一個比`MyLinearMap`更好的`Map`接口實現，`MyBetterMap`，并引入哈希，這使得`MyBetterMap`效率更高。 ## 10.1 哈希為了提高`MyLinearMap`的性能，我們將編寫一個新的類，它被稱為`MyBetterMap`，它包含`MyLinearMap`對象的集合。它在內嵌的映射之間劃分鍵，因此每個映射中的條目數量更小，這加快了`findEntry`，以及依賴于它的方法的速度。這是類定義的開始： ```java public class MyBetterMap<K, V> implements Map<K, V> { protected List<MyLinearMap<K, V>> maps; public MyBetterMap(int k) { makeMaps(k); } protected void makeMaps(int k) { maps = new ArrayList<MyLinearMap<K, V>>(k); for (int i=0; i<k; i++) { maps.add(new MyLinearMap<K, V>()); } } } ``` 實例變量`maps`是一組`MyLinearMap`對象。構造函數接受一個參數`k`，決定至少最開始，要使用多少個映射。然后`makeMaps`創建內嵌的映射并將其存儲在一個`ArrayList`中。現在，完成這項工作的關鍵是，我們需要一些方法來查看一個鍵，并決定應該進入哪個映射。當我們`put`一個新的鍵時，我們選擇一個映射；當我們`get`同樣的鍵時，我們必須記住我們把它放在哪里。一種可能性是隨機選擇一個子映射，并跟蹤我們把每個鍵放在哪里。但我們應該如何跟蹤？看起來我們可以用一個`Map`來查找鍵，并找到正確的子映射，但是練習的重點是編寫一個有效的`Map`實現。我們不能假設我們已經有了。一個更好的方法是使用一個哈希函數，它接受一個`Object`，一個任意的`Object`，并返回一個稱為哈希碼的整數。重要的是，如果它不止一次看到相同的`Object`，它總是返回相同的哈希碼。這樣，如果我們使用哈希碼來存儲鍵，當我們查找時，我們將得到相同的哈希碼。在Java中，每個`Object`都提供了`hashCode`，一種計算哈希函數的方法。這種方法的實現對于不同的對象是不同的；我們會很快看到一個例子。這是一個輔助方法，為一個給定的鍵選擇正確的子映射： ```java protected MyLinearMap<K, V> chooseMap(Object key) { int index = 0; if (key != null) { index = Math.abs(key.hashCode()) % maps.size(); } return maps.get(index); } ``` 如果`key`是`null`，我們任意選擇索引為`0`的子映射。否則，我們使用`hashCode`獲取一個整數，調用`Math.abs`來確保它是非負數，然后使用余數運算符`%`，這保證結果在`0`和`maps.size()-1`之間。所以`index`總是一個有效的`maps`索引。然后`chooseMap`返回為其所選的映射的引用。我們使用`chooseMap`的`put`和`get`，所以當我們查詢鍵的時候，我們得到添加時所選的相同映射，我們選擇了相同的映射。至少應該是 - 稍后我會解釋為什么這可能不起作用。這是我的`put`和`get`的實現： ```java public V put(K key, V value) { MyLinearMap<K, V> map = chooseMap(key); return map.put(key, value); } public V get(Object key) { MyLinearMap<K, V> map = chooseMap(key); return map.get(key); } ``` 很簡單，對吧？在這兩種方法中，我們使用`chooseMap`來找到正確的子映射，然后在子映射上調用一個方法。這就是它的工作原理。現在讓我們考慮一下性能。如果在`k`個子映射中分配了`n`個條目，則平均每個映射將有`n/k`個條目。當我們查找一個鍵時，我們必須計算其哈希碼，這需要一些時間，然后我們搜索相應的子映射。因為`MyBetterMap`中的條目列表，比`MyLinearMap`中的短`k`倍，我們的預期是`?`倍的搜索速度。但運行時間仍然與`n`成正比，所以`MyBetterMap`仍然是線性的。在下一個練習中，你將看到如何解決這個問題。 ## 10.2 哈希如何工作？哈希函數的基本要求是，每次相同的對象應該產生相同的哈希碼。對于不變的對象，這是比較容易的。對于具有可變狀態的對象，我們必須花費更多精力。作為一個不可變對象的例子，我將定義一個`SillyString`類，它包含一個`String`： ```java public class SillyString { private final String innerString; public SillyString(String innerString) { this.innerString = innerString; } public String toString() { return innerString; } ``` 這個類不是很有用，所以它叫做`SillyString`。但是我會使用它來展示，一個類如何定義它自己的哈希函數： ```java @Override public boolean equals(Object other) { return this.toString().equals(other.toString()); } @Override public int hashCode() { int total = 0; for (int i=0; i<innerString.length(); i++) { total += innerString.charAt(i); } return total; } ``` 注意`SillyString`重寫了`equals`和`hashCode`。這個很重要。為了正常工作，`equals`必須和`hashCode`一致，這意味著如果兩個對象被認為是相等的 - 也就是說，`equals`返回`true` - 它們應該有相同的哈希碼。但這個要求只是單向的；如果兩個對象具有相同的哈希碼，則它們不一定必須相等。 `equals`通過調用`toString`來工作，返回`innerString`。因此，如果兩個`SillyString`對象的`innerString`實例變量相等，它們就相等。 `hashCode`的原理是，迭代`String`中的字符并將它們相加。當你向`int`添加一個字符時，Java 將使用其 Unicode 代碼點，將字符轉換為整數。你不需要了解 Unicode 的任何信息來弄清此示例，但如果你好奇，可以在 <http://thinkdast.com/codepoint> 上閱讀更多內容。該哈希函數滿足要求：如果兩個`SillyString`對象包含相等的內嵌字符串，則它們將獲得相同的哈希碼。這可以正常工作，但它可能不會產生良好的性能，因為它為許多不同的字符串返回相同的哈希碼。如果兩個字符串以任何順序包含相同的字母，它們將具有相同的哈希碼。即使它們不包含相同的字母，它們可能會產生相同的總量，例如`"ac"`和`"bb"`。如果許多對象具有相同的哈希碼，它們將在同一個子映射中。如果一些子映射比其他映射有更多的條目，那么當我們有`k`個映射時，加速比可能遠遠小于`k`。所以哈希函數的目的之一是統一；也就是說，以相等的可能性，在這個范圍內產生任何值。你可以在 <http://thinkdast.com/hash> 上閱讀更多設計完成的，散列函數的信息。 ## 10.3 哈希和可變性 `String`是不可變的，`SillyString`也是不可變的，因為`innerString`定義為`final`。一旦你創建了一個`SillyString`，你不能使`innerString`引用不同的`String`，你不能修改所指向的`String`。因此，它將始終具有相同的哈希碼。但是讓我們看看一個可變對象會發生什么。這是一個`SillyArray`定義，它與`SillyString`類似，除了它使用一個字符數組而不是一個`String`： ```java public class SillyArray { private final char[] array; public SillyArray(char[] array) { this.array = array; } public String toString() { return Arrays.toString(array); } @Override public boolean equals(Object other) { return this.toString().equals(other.toString()); } @Override public int hashCode() { int total = 0; for (int i=0; i<array.length; i++) { total += array[i]; } System.out.println(total); return total; } ``` `SillyArray`也提供`setChar`，它能夠修改修改數組內的字符。 ```java public void setChar(int i, char c) { this.array[i] = c; } ``` 現在假設我們創建了一個`SillyArray`，并將其添加到`map`。 ```java SillyArray array1 = new SillyArray("Word1".toCharArray()); map.put(array1, 1); ``` 這個數組的哈希碼是`461`。現在如果我們修改了數組內容，之后嘗試查詢它，像這樣： ```java array1.setChar(0, 'C'); Integer value = map.get(array1); ``` 修改之后的哈希碼是`441`。使用不同的哈希碼，我們就很可能進入了錯誤的子映射。這就很糟糕了。一般來說，使用可變對象作為散列數據結構中的鍵是很危險的，這包括`MyBetterMap`和`HashMap`。如果你可以保證映射中的鍵不被修改，或者任何更改都不會影響哈希碼，那么這可能是正確的。但是避免這樣做可能是一個好主意。 ## 10.4 練習 8 在這個練習中，你將完成`MyBetterMap`的實現。在本書的倉庫中，你將找到此練習的源文件： + `MyLinearMap.java`包含我們在以前的練習中的解決方案，我們將在此練習中加以利用。 + `MyBetterMap.java`包含上一章的代碼，你將填充一些方法。 + `MyHashMap.java`包含按需增長的哈希表的概要，你將完成它。 + `MyLinearMapTest.java`包含`MyLinearMap`的單元測試。 + `MyBetterMapTest.java`包含`MyBetterMap`的單元測試。 + `MyHashMapTest.java`包含`MyHashMap`的單元測試。 + `Profiler.java`包含用于測量和繪制運行時間與問題大小的代碼。 + `ProfileMapPut.java`包含配置該`Map.put`方法的代碼。像往常一樣，你應該運行`ant build`來編譯源文件。然后運行`ant MyBetterMapTest`。幾個測試應該失敗，因為你有一些工作要做！從以前的章節回顧`put`和`get`的實現。然后填充`containsKey`的主體。提示：使用`chooseMap`。再次運行`ant MyBetterMapTest`并確認通過了`testContainsKey`。填充`containsValue`的主體。提示：不要使用`chooseMap`。`ant MyBetterMapTest`再次運行并確認通過了`testContainsValue`。請注意，比起找到一個鍵，我們必須做更多的操作才能找到一個值。類似`put`和`get`，這個實現的`containsKey`是線性的，因為它搜索了內嵌子映射之一。在下一章中，我們將看到如何進一步改進此實現。