和相等性有關的介面

一個有趣的點是，和比較大小有關的介面有IComparable及IComparable，一個是泛型版本，參數是T，另一個是多型版本，參數是object。

比較相等性的介面只有泛型版本IEquatable，這是因為每個物件身上都繼承了Object.Equals(Object)方法。那為什麼要額外提出一個泛型版本的介面，不直接用多型版本的Equals就好呢？

因為泛型版本的效能會比較好。

.Equals(Object)要在run time才能判斷要選Object上的Equals，還是T類別上的Equals，而.Equals(T)可以在compile time就推斷出該方法。

而且.Equals(Object)裡頭的實做還要再將Object轉型成T型別，才能比較兩物件是否相等。與其每個型別都要寫一行轉型，不如用泛型會讓程式更簡潔。

Dictionary<TKey, TValue>, List, LinkedList等，這些容器的某些方法會需要相等性。像是Contains、IndexOf、LastIndexOf、Remove等等。於是很自然地這些Generic Collection都必須實做IEquatable介面。

如果實做了IEquatable，那麼也應該覆寫Equals(Object)並提供相同的行為。

那附帶一提，既然都實做了IEquatable，要不要實做IComparable呢？

答案是，看你有沒有需要排序。如果有需要排序，就會需要。如果不需要排序，那麼當然不需要。補充一點，Sort和Equal沒有絕對的關係，Sort可能會需要Equals，也可能不需要。像是class Person可以Sorted By Name，但是Name也可以和Equal無關，身份證字號才和Equal有關。

EqulityComparer

Library內還有一種被稱為相等性比較器的泛型類別EqualityComparer。實做了IEqualityComparer介面。

這個介面有兩個方法

這個介面暗示著相等性的比較不一定一定要用覆寫Equals的方法定義，你可以用另外一個物件實做相等性比較的行為，並傳入給像是Dictionary<TKey, TValue>的泛型類別建構式。

看看Dictionary的建構式，預設會使用EqualityComparer.Default作為T的相等性比較的預設實做。當然你也可以傳入相等性比較器。

Dictionary<TKey,TValue>()	Initializes a new instance of the Dictionary<TKey,TValue> class that is empty, has the default initial capacity, and uses the default equality comparer for the key type.
Dictionary<TKey,TValue>(IEqualityComparer)	Initializes a new instance of the Dictionary<TKey,TValue> class that is empty, has the default initial capacity, and uses the specified IEqualityComparer.

如果使用了Dictionary<TKey, TValue>，則Library會幫你實做一個預設的比較器，EqualityComparer.Default。實做的內容是判斷TKey是否實做了IEquatable，如果有的話就用該實做。如果沒有的話，就用T的Object.Equals和Object.GetHashCode實做。

語言的設計

為什麼C#的設計者要提供operator ==，又要提供.Equals，這兩種功能相似，又容易混淆的功能呢？
曾待過C# language design team的Eric Lippert在他的部落格文章中給出了觀點。這裡稍微整理一些重點。

設計其實是一連串的取捨。你可以選擇讓System.Object完全沒有.Equals方法，讓各個語言各自實現自己的相等性實做。但另一種設計的看法是，相等性這個概念是和語言無關的，不管用哪種語言來描述，物件都應該能和其他物件比較相等性。

另一個問題是相等性的本質。直觀上，我們都以為相等性是對稱的。其實相等性在物件導向中是個不對稱的概念。

Operator == 和Object.Equals是兩個不同層面的設計。Operator == 是語言層級的語法慣例。Object.Equals是框架層級的慣例。

首先以框架開發者的角度來看吧，你被要求設計一個物件導向的類別函式庫，而且你希望每個物件都能夠和其他物件進行比較，而物件可能有不同的型別，下面是幾種設計選擇。

1. 使用double dispatch，在執行期由a和b的runtime type動態決定要呼叫哪個比較方法。並且在CLR的層面實做double dispatching，所有支援CLR的語言都必須正確的理解double dispatching和產生正確的IL。
2. 使用single dispatch，並導入不對稱的相等性概念。開發者如果需要double dispatch，可以自己覆寫掉Equals。
3. make method non-virtual，無法覆寫，只能用System.Object.Equals的實做，byte-by-byte比較兩個物件是否相等。
4. 不實做這功能

這裡補充一下Double Dispatch的意思。C++, C#, Java這些語言在實做多型時，都是採用Single Dispatch，也就是在遇到objectA.method(objectB)這類的runtime call時，只用objectA的runtime type決定要呼叫的方法。而少數語言如Common Lisp, Julia, Perl6會在語言層級實做Double Dispatching，同時由objectA和objectB的型別決定要呼叫的實做。Single Dispatching可以藉由實做Visitor Pattern來達到Multiple Dispatching的效果。

上面四種作法其實都可以。只是.NET框架的設計者選擇了2，不用修改CLR的設計，同時提供開發者足夠的彈性。代價是開發者必須要手動做些工作，但如果開發者滿意預設的Equals實做，則可以什麼都不管。

對Operator == 而言，開發者通常習慣該運算子左右的型別是對稱的。語言設計者得考慮要在什麼樣的程度允許開發者多載Operator == 運算子。

多載運算子的方法

1. 使用Double Dispatch，並搭配Compiler的Code Gen，但Code Gen會變得非常複雜，而且這些操作在CLR層面並不會比較有效率。
2. 使用Single Dispatch，根據左邊物件執行期的型別決定要呼叫什麼實做。但這在語意上意味著運算子左右兩邊是不對稱的。幾乎等於是x.Equals(y)的語法糖。
3. 實做對稱的non-virtual static method，根據compile-time判斷左右的型別，決定要多載哪個行為。
4. 不實做這功能

語言設計者選擇了3。

替自訂型別定義相等性

替自訂義的類別(class)或結構(struct)定義相等性時，請滿足下列五個性質

1. x.Equals(x)為真，數學上的Reflexive property
2. x.Equals(y) == y.Equals(x)，Symmetric property
3. 若 x.Equals(y) && y.Equals(z) 為真，則x.Equals(z)為真，遞移性
4. 只要x, y沒有修改，則不管呼叫幾次，x.Equals(y)結果相同。
5. x.Equals(null)請回傳false，null.Equals(null)擲出例外。這是特例。

任何自定義的struct已經有一個預設的value equality實做，其繼承自System.ValueType，覆寫掉Object.Equals(Object)。內容是透過反射檢查所有的field與property確保一致。但也因為是透過反射，所以效能通常不算好。

1. 覆寫掉virtual Object.Equials(Object)
2. 實做System.IEquatable，提供一個該型別的Equals方法。會在這個方法內寫詳細的欄位比較。不要在這個方法擲出例外。C#的struct不能繼承struct，但class是可以繼承其他class的，對於class要特別留意只在Equals內撰寫該class內的成員。parent class成員的比較就用base.Equals去處理。唯一的例外是如果直接繼承自Object，不要呼叫Object.Equals(Object)，因為這方法會比reference。
3. 選擇性建議：overload operator==與operator!=
4. 覆寫Object.GetHashCode()，使兩個object如果value equality相同，就產生相同的hash code。
5. 選擇性建議：提供greater than和less than，實做IComparable Interface。並且記得多載<=和>=。

其他細節可以參考How to: Define Value Equality for a Type (C# Programming Guide)

Reference Link

呼...不知不覺就寫成系列文了。為了寫這篇文章，參考了很多資料。一開始只是想了解C#的Library中Equality介面為什麼這樣設計，和Collection中Equality的問題，結果不知不覺越挖越深，乾脆整理成系列文，文章內有任何錯誤，歡迎留言指正。

1. How does HashSet compare elements for equality?(stackoverflow)
2. When should I use == and when should I use Equals?(MS C# FAQ team)
3. Multiple Dispatch(Wiki)
4. Back to basics: Dictionary part 3, built-in GetHashCode(Mark Vincze)
5. Should an override of equals on a reference type always mean value equality(stackoverflow)
6. Guidelines and rules for GetHashCode(Eric Lippert)
7. When Should a .NET Class Override Equals()? When Should it Not?
   (stackoverflow)
8. Why does Microsoft recommend skip implementing equality operator for reference types?
9. Double Your Dispatch, Double Your Fun(Eric Lippert)
10. Overloading operator== versus Equals()(stackoverflow)
11. Overriding Equals in C#(Logan Franken)
12. Difference between == operator and Equals() method in C#?(stackoverflow)
13. C# difference between == and Equals()(stackoverflow)
14. GetHashCode系列文(hello[at]30abysses.com)
15. MSDN
    1. HashSet
    2. Object
    3. IEqualityComparer
    4. CA2104: Do not declare read only mutable reference types
    5. Do not overload operator equals on reference types
    6. source reference comparer.cs
    7. Operator==
    8. How to: Test for Reference Equality (Identity) (C# Programming Guide)
    9. How to: Define Value Equality for a Type (C# Programming Guide)
    10. Boxing and Unboxing (C# Programming Guide)
    11. IEquatable Interface