More Effective C# 10.了解 GetHashCode() 的陷阱 More Effective C# 10.了解 GetHashCode() 的陷阱(Understand the Pitfalls of GetHashCode())

這個做法在解釋為什麼覆寫 Equal 方法的時候同時要覆寫 GetHashCode 方法。

GetHashCode 方法是少數幾個內建在 System.Object 的方法,它要完成的任務是透過一個 hash function 計算並回傳一個專屬於這個物件的雜湊值, 以下是它的原始碼,預設的 hash function 會回傳物件的 sync block index 當成這個物件的 HashCode。

/// <summary>Serves as the default hash function.</summary>
/// <returns>A hash code for the current object.</returns>
public virtual int GetHashCode()
{
    // GetHashCode is intended to serve as a hash function for this object.
    // Based on the contents of the object, the hash function will return a suitable
    // value with a relatively random distribution over the various inputs.
    //
    // The default implementation returns the sync block index for this instance.
    // Calling it on the same object multiple times will return the same value, so
    // it will technically meet the needs of a hash function, but it's less than ideal.
    // Objects (& especially value classes) should override this method.

    return RuntimeHelpers.GetHashCode(this);
}

為什麼 GetHashCode 方法很重要? 是因為在例如 HashSet<T>Dictionary<K,V> 這種類別內部就是根據這個方法來決定 key 值, 像是 Dictionary 的 FindValue 方法就會使用到 GetHashCode 方法。

internal ref TValue FindValue(TKey key)
 {
     if (key == null)
     {
         ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key);
     }

     ref Entry entry = ref Unsafe.NullRef<Entry>();
     if (_buckets != null)
     {
         Debug.Assert(_entries != null, "expected entries to be != null");
         IEqualityComparer<TKey>? comparer = _comparer;
         if (typeof(TKey).IsValueType && // comparer can only be null for value types; enable JIT to eliminate entire if block for ref types
             comparer == null)
         {
             uint hashCode = (uint)key.GetHashCode();
             int i = GetBucket(hashCode);
             ...

首先 GetHashCode 方法會回傳一個 HashCode,接下來會使用 HashCode 來快速找出物件是存在哪一個 Bucket 裡面,找到正確的 Bucket 後就能 從它裡面取得正確的值,也就是說每個 Bucket 裡面存放的物件越少就能越快找到我們想要的內容。

一個可用的 GetHashCode 方法必須遵守幾個原則:

  1. 兩個相等(使用 equals 方法)的物件必須回傳相同的 HashCode。
  2. 物件狀態的改變不能影響 HashCode 的結果,這是為了要確保物件被放進 Bucket 以後能回來找到同樣的 Bucket。
  3. hash function 產出的 HashCode 必須要平均分佈,不能有過多的物件集中在某個 Bucket 這種情況發生。

從第一個原則可以看出兩個物件要使用 equals 方法決定是否相同,所以如果你有覆寫過 equals 方法可能就會導致 GetHashCode 判斷的規則跟你的 equals 方法不太一樣, 所以為了要遵循第一個相等性的原則,有覆寫過 equals 通常都要覆寫 GetHashCode 方法。

接下來看看這段程式碼,此處定義了一個字典並要求傳入 Customer 做為 key 值,並且又覆寫了 GetHashCode 的邏輯改成回傳 Name 值的 HashCode, 這就會導致字典選擇用 Name 值的 HashCode 做為 key,這樣做就違反了第二個原則,因為在下方我只要一把 Name 的值更換掉,就沒辦法找回字典中的資料了。

void Main()
{
	Customer c1 = new Customer("Acme Products");
	var dict = new Dictionary<Customer, int>();
	dict.Add(c1, 1);
	Console.WriteLine(c1.GetHashCode());
	c1.Name = "Acme Software";
	Console.WriteLine(c1.GetHashCode());
	Console.WriteLine(dict[c1]);
}

public class Customer
{
	private decimal revenue;
	public Customer(string name) =>
	this.Name = name;
	public string Name { get; set; }
	public override int GetHashCode() => Name.GetHashCode();
}

為了要符合第二個原則的要求,建議是將要使用 GetHashCode 計算的欄位變成 immutable,確保他在第一次初始化的時候就不要變動了, 如果真的要變動則是要透過建立新物件並把就物件移除掉的流程來處理。

void Main()
{
	Customer c1 = new Customer("Acme Products");
	var dict = new Dictionary<Customer, int>();
	dict.Add(c1, 1);
	Console.WriteLine(c1.GetHashCode());
	dict.First().GetHashCode().Dump();
	Customer c2 = c1.ChangeName("Acme Software");
	int o = dict[c1];
	dict.Remove(c1);
	dict.Add(c2, o);
}

public class Customer
{
	private decimal revenue;
	public Customer(string name) => this.Name = name;
	public string Name { get; }
	public decimal Revenue { get; set; }
	public override int GetHashCode() => Name.GetHashCode();
	public Customer ChangeName(string newName) => new Customer(newName) { Revenue = revenue };
}

要符合第三個原則的需求比較困難,一個常用的演算法是把型別中所有的欄位的 GetHashCode 回傳值做 XOR 運算, 但是要把 mutable 的欄位排除在外,否則會讓結果不隨機導致資料都集中在幾個 Bucket 中。

像是 Int32 覆寫的 GetHashCode 方法就沒有隨機性。

public override int GetHashCode()
{
    return m_value;
}

Summary

GetHashCode() 方法要求相同的物件必須產生相同的 HashCode,而且不會根據狀態改變而變動,並且要求分佈均勻。 只有 immutable 的類型可以滿足這三個需求,其他類型雖然也可以使用但要了解對應的缺陷。