談談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的。

Leave a Reply

avatar
  Subscribe  
Notify of