了解GetHashCode()的缺陷

 本條款讨論函數GetHashCode()的缺陷，這種情況在全書中是唯一的。幸運的是，GetHashCode()函數隻應用在一個地方：為一個基于散列（hash）的集合定義鍵的散列值，典型的集合為Hashtable或Dictionary容器。因為基類的GetHashCode()實作有很多問題。對引用類型來講，它可以正常工作，但是效率很低。對于值類型來講，基類中的實作通常是不正确的。更為糟糕的是，我們編寫的GetHashCode()不可能既有效率又正确。沒有哪個函數能比GetHashCode()産生更多的讨論和混淆。下面的内容可以幫助大家理清這些混淆。

如果我們定義的類型在容器中不會被當作鍵來使用，那就沒什麼問題。例如，表示視窗控件、Web頁面控件或者資料庫連接配接的類型就不太可能被當作鍵在集合中使用。在這些情況下，我們無需做任何事情。所有的引用類型都有一個正确的散列碼，盡管效率非常低下。值類型應該具有常量性（參見條款7），這時候預設的實作也可以正常工作，雖然效率也不高。在我們建立的大多數類型中，最好的做法就是完全避免自己實作GetHashCode()。

如果有一天，我們建立的類型要被當作散清單（hash table）中的鍵使用，我們就需要自己實作GetHashCode()。基于散列的容器使用散列碼來優化查詢。每一個對象都會産生一個稱做散列碼的整數值。基于散列碼的值，對象會被裝進一些“散列桶（bucket）”中。要搜尋一個對象，我們會請求它的鍵，并在其對應的“散列桶”中搜尋。在.NET中，每一個對象都有一個散列碼，其值由System.Object.GetHashCode()決定。任何GetHashCode()的重載[21]版本都必須遵循以下三條規則：

1. 如果兩個對象相等（由operator==定義），它們必須産生相同的散列碼。否則，這樣的散列碼不能用來查找容器中的對象[22]。

2. 對于任何一個對象A，A.GetHashCode()必須是一個執行個體不變式（invariant）。即不管在A上調用什麼方法，A.GetHashCode()都必須總是傳回相同的值。這可以確定放在“散列桶”中的對象總是位于正确的“散列桶”中。

3. 對于所有的輸入，散列函數應該在所有整數中産生一個随機的分布。這樣，我們才能從一個散列容器上獲得效率的提升。

要編寫一個正确且有效率的散列函數，我們需要對類型有充分的知識才能確定遵循第3條規則。System.Object和System.ValueType中定義的GetHashCode()沒有這方面的優勢，因為它們必須在對具體類型幾乎一無所知的情況下，提供最合适的預設行為。Object.GetHashCode()使用System.Object中的一個内部字段來産生散列值。系統建立的每一個對象在建立時都會有一個唯一的對象鍵（一個整數值）。這些鍵從1開始，每建立一個新的對象（任何類型），便會随之增長。對象辨別字段會在System.Object構造器中設定，并且之後不能被更改。對于一個給定的對象，Object.GetHashCode()會傳回該值作為散列碼。

現在讓我們對照上述三條規則，逐一檢查Object.GetHashCode()方法。在沒有重寫operator==的情況下，如果兩個對象相等[23]，那麼Object.GetHashCode()會傳回同樣的散列值。System.Object的operator==()判斷的是對象辨別。GetHashCode()會傳回内部的對象辨別字段。這樣做是可行的。但是，如果我們實作了自己的operator==，那就也必須實作GetHashCode()，以確定遵循第一條規則。有關相等判斷，參見條款9。

Object.GetHashCode()預設會滿足第二條規則：在對象建立之後，其散列碼永遠不會改變。

第三條規則：對于所有的輸入，散列函數應該在所有整數中産生一個随機的分布，Object.GetHashCode()不能被滿足該規則。除非我們建立了數量非常多的對象，否則一個數值序列在所有整數中不會是一個随機的分布。Object.GetHashCode()傳回的散列碼會集中在整數範圍的低端。

這意味着Object.GetHashCode()的實作是正确的，但是效率不夠好。如果我們基于自己實作的一個引用類型建立了一個散清單，System.Object的預設行為可以使我們的散清單正常工作，但是會比較慢。當我們建立的引用類型要用于散列鍵時，我們應該重寫其GetHashCode()方法，使其産生的散列值在所有整數範圍内有一個良好的分布。

在談論如何實作我們自己的GetHashCode()方法之前，我們先來對照上述三條規則，看看ValueType.GetHashCode()方法。System.ValueType重寫了GetHashCode()方法，為所有值類型提供了一種預設的實作。預設的實作會傳回類型中定義的第一個字段的散列碼。看下面的例子：

public struct MyStruct

{

  private string  _msg;

  private int      _id;

  private DateTime _epoch;

}

MyStruct對象傳回的散列碼實際等同于_msg字段的散列碼。下面的代碼将總是傳回true：

MyStruct s = new MyStruct();

return s.GetHashCode() == s._msg.GetHashCode();

第一條規則為：兩個相等（由operator==()定義）的對象也必須有相同的散列碼。在絕大多數情況下，我們的值類型會滿足該規則。但是我們也可能會破壞該規則，就像我們在引用類型中所做的那樣。預設情況下，ValueType.operator==()會比較結構中的第一個字段和其他每個字段。這将可以滿足第一條規則。如果我們在自己的結構中定義的operator==使用了第一個字段，那麼也可以滿足第一條規則。但是，如果結構的第一個字段沒有參與類型的“相等判斷”，那就違背了第一條規則，進而會破壞GetHashCode()方法[24]。

第二條規則要求散列碼必須是一個執行個體不變式。隻有當結構中的第一個字段是一個常量字段時，該規則才會被滿足。如果結構的第一個字段發生變化，那麼結構的散列碼也會随之改變。這就打破了該規則。是的，隻要結構中的第一個字段在對象的生存期中發生了改變，那麼GetHashCode()方法将遭到破壞。這是“盡可能實作具有常量性的值類型”的又一個理由（參見條款7）。

第三條規則依賴于第一個字段的類型，以及其使用情況。如果第一個字段會在所有的整數中産生一個随機的分布，同時第一個字段也會随機分布于結構的所有執行個體中，那麼GetHashCode()将會為結構産生一個比較均勻的分布。但是，如果第一個字段經常都是相同的值，那就将違反第三條規則。下面對前面的代碼做了一個很小的更改：

如果_epoch字段被設定為目前的日期（不包括時間），那麼在一個特定日期中建立的MyStruct對象将擁有相同的散列碼。這就會破壞散列碼的均勻分布。

條款10：了解GetHashCode()方法的缺陷　　67

我們來總結一下Object.GetHashCode()方法的預設行為：對于所有的引用類型，該方法會正常工作，雖然它并不必然會産生一個高效的分布。（如果我們重寫了Object.operator ==()，将會破壞GetHashCode()方法。）隻有在結構類型的第一個字段是隻讀的情況下，ValueType類型的GetHashCode()才會正常工作。隻有當第一個字段包含的值分布于“其輸入的一個有意義的子集上”時，ValueType.GetHashCode()才會産生一個比較高效的散列碼。

如果我們要建立一個更好的散列碼，就需要為類型添加一些限制。我們再來對照上述三條規則，看看如何建立一個能夠良好工作的GetHashCode()實作。

首先，如果兩個對象相等（由operator==()定義），它們必須傳回相同的散列碼。任何用來産生散列碼的屬性或者資料值，都必須參與到類型的相等判斷中。很明顯，這意味着會有相同的屬性同時用于相等判斷和散列碼計算中。但并非所有參與相等判斷的屬性，都會用來做散列碼計算。System.ValueType的預設行為就是這樣。但是，這又通常意味着會違反第三條規則。同樣的資料元素應該同時參與到兩種計算中。

第二條規則是GetHashCode()的傳回值必須是一個執行個體不變式。假設我們定義了如下的引用類型：

public class Customer

  private string _name;

  private decimal _revenue;

  public Customer( string name )

  {

    _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 );

// Name錯了:

c1.Name = "Acme Software";

在上面的代碼中，c1會在myHashMap中的某個地方丢失。當我們将c1放入myHashMap中時，散列碼會根據字元串"Acme Products"來産生。但在我們将Name更改為"Acme Software"之後，散列碼也會更改。新的散列碼會根據"Acme Software"來産生。這時候c1仍然存儲在由"Acme Products"定義的“散列桶”中，雖然實際上它應該存儲在由"Acme Software"定義的“散列桶”中。我們将會在集合中失去c1這個Customer。丢失的原因在于散列碼不再是一個對象不變式。因為在存儲對象之後，我們更改了它的“散列桶”。

隻有在Customer是一個引用類型時，上述問題才會出現。值類型的行為有所不同，但是仍然會引起問題。如果Customer是一個值類型，将有一個c1的副本被存儲在myHashMap中。最後一行對Name的改變将不會對存儲在myHashMap中的副本産生任何效果。由于裝箱和拆箱都會導緻複制，是以“想在一個值類型對象被添加到一個集合中之後，再改變其成員”幾乎是不可能的。

解決第二條規則的唯一方式就是讓散列碼函數根據對象中的常量屬性（一個或多個）傳回一個值。System.Object使用對象辨別來遵循該規則，因為對象辨別不可能改變。System.ValueType希望我們類型中的第一個字段不會改變。如果不将類型實作為常量類型，我們将無法很好地滿足該規則。當我們定義的值類型要用作一個散列集合中的鍵時，它必須是一個常量類型。如果不遵循這種推薦，将類型作為鍵的使用者将有可能破壞散清單。下面的代碼對Customer類進行了修正，讓我們能夠在改變它的同時維持其Name屬性的常量性：

條款10：了解GetHashCode()方法的缺陷　　68

  private readonly string _name;

  public Customer( string name ) :

    this ( name, 0 )

  public Customer( string name, decimal revenue )

    _revenue = revenue;

  // 改變Name，傳回一個新對象:

  public Customer ChangeName( string newName )

    return new Customer( newName, _revenue );

将Name實作為常量屬性後，我們改變Customer.Name屬性的方式必須做如下的變動：

myHashMap.Add( c1,orders );

Customer c2 = c1.ChangeName( "Acme Software" );

Order o = myHashMap[ c1 ] as Order;

myHashMap.Remove( c1 );

myHashMap.Add( c2, o );

我們必須删除原來的Customer，改變其名字，然後再将新的Customer對象添加到散清單中。這看起來要比第一個版本麻煩，但是它可以正常工作。前一個版本會導緻程式員編寫不正确的代碼。通過将“用于散列碼計算的屬性”強制實作為常量屬性，我們可以確定正确的行為。類型的使用者将不可能在這個問題上犯錯。是的，這個版本需要的編碼更多。我們強制讓開發人員編寫更多的代碼，因為這是編寫正确代碼的唯一方式。我們要確定任何用于散列碼計算的資料成員都不會改變。

第三條規則要求GetHashCode()對于所有的輸入，應該在所有整數中産生一個随機的分布。滿足這條規則依賴于所建立的具體類型。如果有這樣的萬能公式存在，那麼System.Object就會實作它了，可惜事實上沒有。一個常用且成功的算法是對一個類型中的所有字段調用GetHashCode()傳回的值進行XOR（異或）。如果我們的類型中含有可變字段，那麼應該在計算時排除它們。

GetHashCode()有非常特殊的需求：相等的對象必須産生相同的散列碼；散列碼必須是對象不變式；必須産生一個均勻的分布以獲得比較好的效率。隻有具有常量性的類型，這三個需求才可能全部被滿足。對于其他類型，我們要依賴預設的行為，但是要清楚了解其缺陷。

本文轉自cnn23711151CTO部落格，原文連結： http://blog.51cto.com/cnn237111/588694，如需轉載請自行聯系原作者