Skip to main content

談談C#的相等性(4)

Equals與GetHashCode​

如果要認真討論GetHashCode，那可以開另一個系列文了。這裡只講幾個要點。

GetHashCode是物件之母Object上的虛擬方法。GetHashCode()設計的目的只有一個，在CLR內，替任意物件提供一個hash值，使該物件能夠被安排進需要使用到Hash的資料結構，像是HashSet。

GetHashCode的回傳值是int32，int32的範圍是2^32，約有42億種可能。但單一程式上同一個type的物件數量可能超過42億種。所以就算是不同的物件，還是有可能有相同的Hash值。

  • 相同的物件，應該有相同的Hash值
  • 不同的物件，可能有相同的Hash值（但機率不高）

而何謂相同的物件，那就是Equals方法的職責。如果是Value Type的物件，只要值相同，就應該有相同的HashCode，那應該盡量讓GetHashCode使用到每個相等性比較會用到的欄位，並做到均勻分散。如果是Reference Type物件，預設相等的定義和值無關，所以預設的GetHashCode並不會用到任何物件的欄位。

mutable reference type as a key​

在Dictionary上使用Reference Type作為key還不算太糟糕，雖然有點不容易理解，但操作都會是正常的。最糟糕的情況是，使用Reference type作為key，修改了相等性的定義和GetHashCode後，在物件被放入Dictionary後操作了mutable field。

問題是這樣子的。

  1. 建立了reference type的物件a
  2. 將物件a作為key加到dictionary內。dictionary會取得該物件的hash code，放到適當的dictionary bucket內。
  3. 此時，們改變了物件a的狀態變成a'，這會讓hash值也跟著改變。但是物件還是存在原本的bucket上。
  4. 現在，如果我們用a'作為key尋找dictionary，當然找不到，因為用a'的hashcode找不到a物件。但接著用和原本的a物件相同的物件作為key尋找dictionary，也會找不到。因為該物件雖然和原本的a物件有相同的hash值，但仍舊和a'不同，所以dictionary會將其視為不同。
internal class NameEqualityComparer : IEqualityComparer<Person>
{
    public bool Equals(Person x, Person y)
    {
        if (x == null && y == null)
        {
            return true;
        }
        if (x == null || y == null)
        {
            return false;
        }
        return x.Name == y.Name;
    }
    public int GetHashCode(Person obj)
    {
        return obj.Name.GetHashCode();
    }
}
internal class Person
{
    public string Name { get; set; }
    public Person(string name)
    {
        Name = name;
    }
}
public static void Main(string[] args)
{
    var lookup = new Dictionary<Person, int>(new NameEqualityComparer());
    var personA = new Person("Tom");
    lookup.Add(personA, 30);
    // bad practice, hash code changes after object be put into a dictionary
    personA.Name = "Mary";
    Console.WriteLine(lookup.ContainsKey(personA));  // false
    var personB = new Person("Tom");
    Console.WriteLine(lookup.ContainsKey(personB));  // false
    personA.Name = "Tom";
    Console.WriteLine(lookup.ContainsKey(personA));  // true
    Console.WriteLine(lookup.ContainsKey(personB));  // true
}

要解決這個問題，最重要的關鍵是「不可以在物件根據GetHashCode的值被放入資料結構後，又修改物件的狀態，使其HashCode和原本不同。」

要想清楚一件事。一個物件如果作為Key被放入Dictionary中，或是作為一個element被放入HashSet內。那麼我們修改該element，如果這個物件是reference type，那麼修改該element的內容，你預期會有什麼結果？

修改後，還是可以用同樣參考的物件存取嗎？

如果不能，那你做這件事情幹麻？ 如果可以取出的話，那麼被修改的欄位應該跟hashcode無關。

修改後，可以用不同參考但相等的物件存取嗎？

如果不行，意味著你其實是把reference作為key。你要小心語意不一致的問題，對dictionary而言，你指的相等其實是reference相等，使用預設的GetHashCode和Equals就足夠。而你剛剛講的相等是Value相等，如果你已經改寫了.Equals方法，但是GetHashCode又使用預設的實做。會對其他開發者產生理解上的不一致。

如果可以，代表其實你並不那麼在乎參考，而是更在乎物件的內容本身。你應該要實做好Equals，而且協助判斷Equals的欄位應該也要參與hash的計算，才能均勻分散不同的物件到不同的hash值。

為了預防這個問題，在物件的HashCode被其他物件使用的期間，應該保持該物件的HashCode值不變。不會改到HashCode值，就不會發生上述的問題。沒有盲腸就沒有盲腸炎。

試想極端狀況，假設全部的物件的GetHashCode值都相同，這樣的系統還是會work，但效率會很差。因為GetHashCode完全無法提供分散不同物件的功能。因此GetHashCode應該盡可能設計成「不同的物件hash會不同」，儘管「不同的物件hash可能會相同」。

反過來說，如果物件上的某個欄位可以被修改，但Hash值不影響。那麼該欄位也不該影響相等性判斷。因為如果該欄位會影響相等性判斷，那Hash值就應該被影響。

所以物件欄位對相等性的影響，應該從最一開始的定義著手：「什麼叫做相等？」和相等性無關的欄位，即使被修改，也不應該影響到HashCode和Equals，和相等性有關的欄位，絕對會影響到Equals，也應該要影響到GetHashCode(儘管可能會產生相同的Hash值)，所以和相等性有關的欄位應該是immutable的。

Last updated on