# 原則7：明白 GetHashCode() 的陷阱 **By D.S.Qiu** 尊重他人的勞動，**支持原創，轉載請注明[出處](/blog/1981202)：[http://dsqiu.iteye.com](http://dsqiu.iteye.com)** 這是這本書介紹的唯一一個原則專門講一個你應該盡量避免的函數。 GetHashCode() 只用在一個地方：定義基于哈希 key 集合，典型地， HashSet<T> 或者 Dictionary<K,V> 容器。值得稱贊的是很多問題會隨著實現基類的 GetHashCode() 而解決。對于引用類型，是能起作用但是低效。對于值類型，基類版本的總是不正確的。所以這很糟糕。寫一個既高效又正確的 GetHashCode() 是完全可能的。沒有哪個函數會像 GetHashCode() 一樣產生這么多討論和困惑。看完下面的消除所有困惑。 如果你定義的類型沒有被用作容器的 key 這就沒關系了。Window 控件 Web page 控件，或數據庫連接很少被用作容器的 key 。在這些例子中，你什么也不用做。所有引用類型的哈希碼是正確的，即使這不是低效的。值類型應該是不可變的（immutable），才是正確的，盡管同樣地不高效。你創建的大多數類，最好避免 GetHashCode() 的存在。 如果有一天，你創建的類要被用作哈希 key ，你就需要實現 GetHashCode() ，所以繼續看下面的。基于哈希碼的容器可以優化查找。每個對象產出的整數被稱為哈希碼。對象根據哈希碼以桶的形式存儲。為了查找某個對象，你請求哈希碼而只是在那個桶里查找。在 .NET 中，每個對象都有一個產生自 System.Object.GetHashCode() 的哈希碼。任何重寫 GetHashCode() 必須遵循下面三個條件： 1.如果兩個對象相等（被操作符 == 定義），你產生相同的哈希值。否則哈希碼不能用來查找容器中的對象。 2.對任何對象 A ， A.GetHashCode() 必須是一個實例不變量。無論什么方法調用 A.GetHashCode() 必須返回相同的值。這保證了一個物體總是存儲在正確的桶中。 3.哈希函數應該針對所有輸入情況產生一個整數隨機分布。這就是為什么基于哈希容器高效。 寫一個正確且有效的哈希函數需要掌握大量類的知識來保證遵循以上3條規則。 System.Object 和 System.ValueType 定義的版本不具備這個優勢。這兩個版本是在對你定義的類不知情的情況下提供的默認行為。 Object.GetHashCode() 使用 System.Object 內部域來產生哈希值。每個對象產生的哈希值要保證唯一，而且存儲為整數。這些 key 從1開始而且每創建一個對象就遞增。對象ID域在 System.Object 構造器中設置，而且不會被后面改動。 Object.GetHashCode() 返回對象的哈希值。 基于上面三條規則逐一檢查 Object.GetHashCode() 。如果兩個對象是相等的， Object.GetHashCode() 返回相同的哈希值，除非你重寫操作符 == 。System.Object 的操作符 ==() 測試兩個對象的ID。 GetHashCode() 返回對象的內部ID域。它就是這樣獲得的。如果你重寫了自己版本的操作符 == ，你必須同時重寫 GetHashCode() 保證符合第一條規則。有關相等的細節查看原則6。 第二條規則是這樣的：對象唄創建之后，它的哈希值不會被改變。 第三條規則，對于所有輸入情況應該產生一個所有正式的隨機分布，而不持有。一個數字序列不是所有整數的隨機分布除非你創建了很大數量的對象。通過 Object.GetHashCode() 產生的哈希碼都集中在小范圍的整數段。 這意味著 Object.GetHashCode() 是正確但不高效。如果你定義基于哈希表的引用類型，System.Object 的默認行為是正確的但慢。如果你創建一個被用做哈希 key 的類，你應該重寫 GetHashCode() ，讓你的類型有一個更好的哈希值分布。 在介紹如果重寫 GetHashCode 之前，這部分討論 ValueType.GetHashCode() 遵循的上面三個規則。 System.ValueType 重寫了 GetHashCode() ，提供了所有值類型的默認行為。這個版本的哈希碼從類型的第一個域返回。考慮下面的例子： ``` public struct MyStruct { private string msg; private int id; private DateTime epoch; } ``` MyStruct 對象的哈希碼產生自 msg 域。假設 msg 不為 null ，下面這段代碼總是返回 true ： ``` MyStruct s = new MyStruct(); s.SetMessage("Hello"); return s.GetHashCode() == s.GetMessage().GetHashCode(); ``` 第一個規則說的是兩個對象相等（操作符 ==() 定義的）必須有相同的哈希碼。大多數情況下，這條規則是被值類型遵循的，但是也可以打破它，就跟引用類型一樣。 ValueType.operator==() 比較 struct 的第一個域，以及其他域。如果要遵從第一條規則，只要重寫 operator== 使用第一個域，就能正確工作。任何 struct 的第一個域不過不參與類型的相等比較就違反此規則，打破了 GetHashCode() 。 第二條規則規定哈希碼必須是實例不變量。只有 struct 的第一個域是不可變的菜遵循這個規則。如果第一個域的值會變，那么哈希值也會改變。那就打破了這條規則。是的， GetHashCode 是任何第一個域在生命期被改變的 struct 破壞了。這就是另外一個原因不可變值類型是你最好的考慮。 第三條規則依賴于類型第一個類的使用。如果第一個域產生一個整數隨機分布，而且第一個域也是分布在 struct 的所有值，然而 struct 產生一個均勻分布。然而，如果第一個域有相同的值，這個規則會被違反。小改動之前的 struct ： public struct MyStruct { private DateTime epoch; private string msg; private int id; } epoch 域被設置為當前日期（不包括時間），所有產生于同一日期的 MyStruct 對象都具體相同的哈希碼。這就不能形成均勻的哈希碼分布了。 總結下默認行為，Object.GetHashCode() 對于引用類型能正確工作，即使沒有產生有效的分布。（如果你重寫了 Object.operator==() ，你會破壞 GetHashCode() 。 ValueType.GetHashCode() 只有在 struct 的第一個域是只讀的才能正確工作。 ValueType.GetHashCode() 產生一個高效的哈希碼只有 struct 的第一個域是一個有意義的子集。 如果你想要構建一個更好的哈希碼，你需要對你的類型做些約束。理想情況下，你應該創建一個不可變值類型。不可變值類型的 GetHashCode() 的規則會比不做約束類型更簡單。現在自己構建一個 GetHashCode() 的實現，并對三條規則進行檢查。 首先，如果兩個對象相等， operator==() 定義的，它們必須返回相同的哈希值。任何用于產生哈希碼的屬性或數據都必須在相等判斷中同樣被考慮。明顯，這意味著屬性在相等判斷和哈希值產生中都被用到。在相等判斷用到的屬性可能在哈希碼計算中沒有用到。 System.ValueType 的默認行為就是那樣做的，這經常意味著規則3會被違反。相同的數據元素應該被用在兩者的計算中。 第二條規則是 GetHashCode() 的返回值必須是實例不變量。想象你定義的一個引用類型， Customer ： ``` public class Customer { private string name; private decimal revenue; public Customer(string name) { this.name = name; } public string Name { get { return name; } set { name = value; } } public override int GetHashCode() { return name.GetHashCode(); } } ``` 執行下面代碼： ``` Customer c1 = new Customer("Acme Products"); myHashMap.Add(c1, orders); // Oops, the name is wrong: c1.Name = "Acme Software"; ``` c1 有時在 HashMap 中會丟失。當你往 map 加入 c1 ，哈希碼產生自字符串“Acme Products”。當你改變 Customer 的 name 為 “Acme Software”。哈希碼改變了。哈希碼產生自新 name : “Acme Software”。 c1 存儲在定義為 “Acme Products”的桶中，但是它應該是在“Acme Software”中。你就丟失了 Customer 在你自己的集合中。丟失是因為哈希碼不是對象的不變量。你在存儲對象后改變了正確的桶。 前面情況只有 Customer 是引用類型才會發生。值類型表現不同，但同樣會出現問題。如果 Customer 是值類型， HashMap 存儲的是 c1 的復制。最后一行改變 name 的值，并不會對 HashMap 存儲有任何影響。因為封箱和拆箱和復制一樣，在加入集合之后，你不能改變值類型成員的值。 唯一能解決規則2的方法是使用對象的一個或多個不可變屬性定義哈希函數。 System.Object 使用不會改變的對象ID來恪守這條規則。 System.ValueType 希望你的類型的第一個域是不會改變的。你不能比讓你的變量不可變做的更好了。當你打算將值類型用作哈希集合的 key ，它必須是不可變類型。如果你違反了這條建議，將會破壞哈希表。回顧 Customer 類，你可以更改 name 為不可變。高亮表示 Customer 的改變： ``` public class Customer { private string name; private decimal revenue; public Customer(string name) { this.name = name; } public string Name { get { return name; } // Name is readonly } public decimal Revenue { get { return revenue; } set { revenue = value; } } public override int GetHashCode() { return name.GetHashCode(); } public Customer ChangeName(string newName) { return new Customer(newName) { Revenue = revenue }; } } ``` ChangeName 創建一個新的 Customer 對象，使用構造器和對象初始化語法設置當前 revenue。 name 不可變改變修改 Customer 對象 name 的方式： ``` Customer c1 = new Customer("Acme Products"); myDictionary.Add(c1, orders); // Oops, the name is wrong: Customer c2 = c1.ChangeName("Acme Software"); Order o = myDictionary[c1]; myDictionary.Remove(c1); myDictionary.Add(c2, o); ``` 你不得不移除原來的 Customer，改變 name ，然后把新的 Customer 對象加入到 Dictionary 中。這看起來比第一個版本更繁瑣，但是這個能正確工作。前一個版本運行程序員寫不正確的代碼。隨著強制用于計算哈希值的屬性為不可變，增強了代碼的正確性。使用你的類型不會出錯。是的，這個版本更好的工作。你要強迫開發者寫更多的代碼，因為這是正確代碼的唯一的方法。確保計算哈希值的數據成員要不可變。 第三條規則說的是 GetHashCode() 應該產生所有輸入情況的隨機分布。滿足這個需求特定依賴你創建的類型。如果魔術公式存在，它會被實現在 System.Object ，而且這個原則也不會存在。一個常用而且成功的算法是使用對所有域使用 XOR 返回 GetHashCode() 的值。如果你的類型包含了一些不可變域，使用它們來計算。 GetHashCode() 有一個非常特別的需求：相等的對象必須產生相等的哈希碼，而且這些哈希值必須是實例不可變的而且產生一個均勻分布會更有高效。只有不可變類型，三條才會滿足。對于其他類型，依靠默認行為，但是明白這里面的陷阱。 小結： 這篇的內容是我們最簡單了，好像也沒有我們什么事情，只要記住最后一句話： 對于其他類型，依靠默認行為，但是明白這里面的陷阱。本來不想寫的，聽了某人的鼓勵，還是決定堅持，雖然寫到了凌晨3點，但還是完成了。所以有時候堅持只是需要一個理由，雖然不太會受這個影響，但是還是會給自己一個心理暗示。 天亮了，還要上班，還要幫國外的幫，也就不能睡覺了，加油，我可以的！ 歡迎各種不爽，各種噴，寫這個純屬個人愛好，秉持”分享“之德！ 有關本書的其他章節翻譯請[點擊查看](/category/297763)，轉載請注明出處，尊重原創！ 如果您對D.S.Qiu有任何建議或意見可以在文章后面評論，或者發郵件（gd.s.qiu@gmail.com)交流，您的鼓勵和支持是我前進的動力，希望能有更多更好的分享。 轉載請在**文首**注明出處：[http://dsqiu.iteye.com/blog/1981202](/blog/1981202) 更多精彩請關注D.S.Qiu的博客和微博（ID：靜水逐風）