IEquatableを完全に理解する

等価性判定のためのインターフェース`IEquatable<T>`についてガイドラインを示し、完全に理解できるよう解説します。

```cs
public interface IEquatable<T>
{
    bool Equals(T other);
}
```

ref.
[IEquatable<T> Interface](https://docs.microsoft.com/ja-jp/dotnet/api/system.iequatable-1?view=netframework-4.7.2)


#まとめ

###本記事中の用語

- **等価性（Equality）**[^equality]: 2つのインスタンスが等しいこと。`Equals()`。
  - **同一性（Identity）**: 2つのインスタンスが同じインスタンスであること。`ReferenceEquals()`。参照の等価性（Reference Equality）。
  - **同値性（Value Equality）**: 2つのインスタンスの値が等しいこと。同じインスタンスとは限らない。値の等価性。

クラス・構造体は可変型と不変型に分けられます。

- **可変（Mutable）型**: インスタンスを生成した後に状態を変更できる型。
- **不変（Immutable）型**: 一度インスタンスを生成したら状態を変更できないようにしてある型。



###クラスでのガイドライン

クラスは参照型であり、既定の`Equals()`では同一性判定が行われます。（= `ReferenceEquals()`）

- **可変型**:
`IEquatable<T>`を実装しない（実装したいならクラスを不変型にする）
- **不変型****で値を表す（値オブジェクト）**: `IEquatable<T>`を実装することを検討し、実装するなら`Equals()`・`GetHashCode()`・`==`/`!=`演算子を全て実装する[^operator]
- **不変型****で値以外を表す**: `IEquatable<T>`を実装しない方が無難だが、実装するなら`Equals()`・`GetHashCode()`を実装し、`==`/`!=`演算子は実装しない



###構造体でのガイドライン

構造体は値型であり、既定の`Equals()`では同値性判定が行われます。

- **可変型**: [構造体は不変型にすべき](https://docs.microsoft.com/en-us/dotnet/standard/design-guidelines/struct)なので検討外
- **不変型**: 常に`IEquatable<T>`を実装して、`Equals()`・`GetHashCode()`・`==`/`!=`演算子を全て実装する



###実装方法

Visual Studio 2017では`IEquatable<T>.Equals(T)`・`Object.Equals(Object)`のオーバーライド・`GetHashCode()`・`==`/`!=`演算子を全て[**自動生成**できるようになりました](https://docs.microsoft.com/en-us/visualstudio/ide/reference/generate-equals-gethashcode-methods?view=vs-2017)（[ReSharperでもできます](https://www.jetbrains.com/help/resharper/Code_Generation__Equality_Members.html)）。バグを埋め込まないよう、原則として手書きではなく自動生成するのが良いでしょう。本記事では自動生成する前提で、詳細なコーディングについては省略します。

※VSCodeでの生成方法がもしあれば教えてください。


#完全に理解する

###`IEquatable<T>`を実装するメリット

等価性判定のカスタマイズを考えた時、そもそも全てのクラス・構造体には`Object`クラスで定義された`Object.Equals(Object)`が既にあります。これを単にオーバーライドするだけと、`IEquatable<T>.Equals(T)`を実装するのとでは何が違うのでしょうか。

```cs
public class Object
{
    public virtual bool Equals(Object obj);
}
```
```cs
public interface IEquatable<T>
{
    bool Equals(T other);
}
```

- `IEquatable<T>.Equals(T)`では無関係な型との等価性判定という意味のないコード（おそらく書き間違い）をコンパイルエラーとして検出できます。
- 構造体に対して`Object.Equals(Object)`を呼び出すと`Object`型へキャストすることによるボックス化[^boxing]が発生します。また既定で構造体用にオーバーライド済みの`ValueType.Equals(Object)`の実装は、リフレクションにより同値性判定を行う[^valuetypeequals]ため、非常に時間がかかってしまいます。これを避けるために`IEquatable<T>`を常に実装します。
- `Object.Equals(Object)`を呼び出すと、`Object`型を経由した仮想メソッド呼び出しになりパラメータのキャストが必要です。型付けされた`IEquatable<T>.Equals(T)`を呼び出すのに比べ、若干ですが余計なコストがかかります。

念のため[こちらのコードで](https://gist.github.com/cactuaroid/5106f3e45d2b1494238e421e85a3668d)パフォーマンス比較してみました。[^issue31283]

|                                     Method |       Mean |     Error |    StdDev |
|------------------------------------------- |-----------:|----------:|----------:|
|             &#39;構造体 Object.Equals(Object) 既定&#39; | 419.431 ns | 1.1720 ns | 1.0963 ns |
|        &#39;構造体 Object.Equals(Object) オーバーライド&#39; |   9.504 ns | 0.0675 ns | 0.0631 ns |
|        &#39;構造体 IEquatable&lt;T&gt;.Equals(T) 直接呼出し&#39; |   2.464 ns | 0.0136 ns | 0.0128 ns |
| &#39;構造体 IEquatable&lt;T&gt;.Equals(T) インターフェース呼び出し&#39; |   3.462 ns | 0.0171 ns | 0.0160 ns |
|                      &#39;クラス Object.Equals(Object) オーバーライド&#39; |   4.106 ns | 0.0263 ns | 0.0246 ns |
|            &#39;クラス IEquatable&lt;T&gt;.Equals(T) 直接呼出し&#39; |   2.519 ns | 0.0123 ns | 0.0115 ns |
|     &#39;クラス IEquatable&lt;T&gt;.Equals(T) インターフェース呼び出し&#39; |   2.955 ns | 0.0112 ns | 0.0105 ns |

構造体・クラス共にIEquatable<T>.Equals(T)直接呼出しが最も速く、次いで` IEquatable<T>.Equals(T)`インターフェース呼び出し、`Object.Equals(Object)`仮想メソッド呼び出しの順となり、構造体の既定実装であるリフレクションは2桁遅い結果となりました。

このようにパフォーマンス上の理由があるため、`Dictionary<TKey, TValue>`や`List<T>`といった多くのクラスの等価性判定を伴う処理では、`IEquatable<T>`を実装している型については`Object.Equals(Object)`ではなく`IEquatable<T>.Equals(T)`を呼ぶように最適化されています。`IEquatable<T>`を実装するデメリットは特にないので、`Equals()`をオーバーライドしたいなら常に`IEquatable<T>`を実装することをお勧めします。

なお、`IEquatable<T>`を実装する場合、以下のように`Object.Equals(Object)`は定型パターンでオーバーライドして`IEquatable<T>.Equals(T)`を呼び出すようにします（自動生成されます）。本記事中ではこれらを特に区別せず`Equals()`と表現します。

```cs
public override bool Equals(object obj) // Object.Equals(Object)のオーバーライド
{
    return Equals(obj as MyClass);
}

public bool Equals(MyClass other) // IEquatable<T>.Equals(T)の実装
{
    // 比較処理
}
```

ref.
[What's the difference between IEquatable and just overriding Object.Equals()?](https://stackoverflow.com/questions/2734914/whats-the-difference-between-iequatable-and-just-overriding-object-equals)



###値を表さないクラスに`IEquatable<T>`を実装しないほうが良いワケ

- クラスに`IEquatable<T>`を実装するということは`Equals()`を同値性判定でオーバーライドすることを意味します。これは「このクラスの等価性とは同値性のことだ」と宣言することになります。なぜ同値性判定が分かりやすく有用なのかというと、値を表すクラスだからです。
- 値を表さないクラスでも`IEquatable<T>`を実装したり`Equals()`をオーバーライドできますが、避けた方が無難でしょう。代わりに例えば、`IEquatable<T>`を実装せず`Equals()`よりも説明的な名前で同値性判定メソッドを定義する[^stringbuilder]という手があります。



###可変型クラスに`IEquatable<T>`を実装してはいけないワケ
- 2つのインスタンスについて`Equals()`が`true`を返すなら`GetHashCode()`が返すハッシュ値も同じでなければなりません[^hash]。ハッシュ値を利用する辞書などでは`Equals()`と`GetHashCode()`の両方が使用されており、このルールを破ると期待通りに動作しません。`Equals()`をオーバーライドする場合はその動作に合わせて`GetHashCode()`もオーバーライドする必要があります。
- ハッシュ値はインスタンスの生存期間中、不変でなければなりません。もし辞書に登録しておいたインスタンスのハッシュ値が変わると行方不明になってしまいます。したがって、可変型では`IEquatable<T>`を実装してはいけません。
- 可変型で同値性判定が必要な場合は、`IEquatable<T>`を実装せずに普通のメソッドとして実装してください。

辞書等に入れないなら可変型クラスに`IEquatable<T>`を実装していいのか？

- そのクラスのハッシュ値が永久に絶対に使われないと言い切るのは大変難しいです。原則として避けてください。パフォーマンスチューニングなどやむを得ない事情で原則に違反した実装をする場合、クラスの可視性を制限したりコメントで注意喚起するなど十分警戒してください。

値を表す不変型はプリミティブ型のように簡単に扱うことができ、**値オブジェクト**と呼ばれます。ここまでをまとめると、値オブジェクトには`IEquatable<T>`を実装し、値オブジェクトでなければ`IEquatable<T>`は実装しない方が無難ということになります。



###値を表さないクラスに`==`/`!=`演算子を実装しないほうが良いワケ

- 演算子による演算結果は自明でなければなりません。例えば`String`クラスでは`"abc" + "def"`は結合されることが自明ですし、`"abc" == "abc"`は`true`になることが自明です。値以外を表すクラスで演算子をオーバーロードしてしまうと、演算結果が自明ではなくなってしまいます。
- `==`/`!=`演算子は、値の比較では同値性判定、値以外の比較では同一性判定が期待されます。構造体は値を意味しますが、クラスは値を表すことも、値以外を表すこともあります。値以外を表すクラスで`==`/`!=`演算子をオーバーロードして同値性判定にしてしまうと期待と動作が一致しません。

例えば`StringBuilder`クラス[^stringbuilder]を考えると

```cs
var builder1 = new StringBuilder();
var builder2 = new StringBuilder();
if (builder1 == builder2) { } // "false" もしこれが内部状態を比較してtrueになったとすると直感に反する
```

一方で、参照型であっても値を表す不変なクラスであれば、値型と同等に`==`/`!=`演算子で比較できると直感に一致します。例えば構造体である[Guid](https://docs.microsoft.com/en-us/dotnet/api/system.guid)とクラスである[Version](https://docs.microsoft.com/en-us/dotnet/api/system.version)は同じ感覚で使えます。

```cs
var guid1 = new Guid();
var guid2 = new Guid();
if (guid1 == guid2) { } // "true"
```
```cs
var version1 = new Version("1.0.0.0");
var version2 = new Version("1.0.0.0");
if (version1 == version2) { } // "true" もしこれがfalseになったとすると直感に反する
```

ref.
[Operator Overloads](https://docs.microsoft.com/en-us/dotnet/standard/design-guidelines/operator-overloads)
[方法: 型の値の等価性を定義する (C# プログラミング ガイド)](https://docs.microsoft.com/ja-jp/dotnet/csharp/programming-guide/statements-expressions-operators/how-to-define-value-equality-for-a-type)
[==演算子とEqualsメソッドの違いとは？［C#］](http://www.atmarkit.co.jp/ait/articles/1802/28/news028.html)



###継承での`IEquatable<T>`に注意

`MyBase`クラスと、その派生クラス`MySub`があったとします。

```cs
var myBase1 = new MyBase();
var myBase2 = new MySub() as MyBase;
// ...
if (myBase1.Equals(myBase2)) { } // MyBase.Equals()で期待通りに判定されますか？
```
```cs
var myBase1 = new MySub() as MyBase;
var myBase2 = new MySub() as MyBase;
// ...
if (myBase1.Equals(myBase2)) { } // MyBase.Equals()で期待通りに判定されますか？
```

`Equals()`に期待される動作は何でしょうか。基底クラスの情報だけで同値性判定すべきなのか、派生クラスの情報も含めるべきなのか、クラスの意味と等価性判定する文脈によって異なり、そのどちらを期待するかも人によって異なるでしょう。

継承関係にあるクラスの同値性判定には意味が自明ではないケースがあります。`IEquatable<T>`を実装するかわりに`Equals()`よりも説明的な名前のメソッドを別に用意することを検討してください。



###配列等に注意

例えば配列をメンバに含むクラスの場合、`Equals()`はどう判定すべきでしょうか。配列の各要素それぞれについての同値性判定が期待されるはずです。しかしVisual StudioもReSharperも自動生成された`Equals()`はそのような実装になっておらず、配列自体を比較してしまいますので、配列の要素が同値であっても`false`になってしまいます。これを解決するには手で書き換える必要があります。

```cs
public string[] Values { get; }

public bool Equals(MyClass other)
{
    return other != null &&
           // EqualityComparer<string[]>.Default.Equals(Value, other.Value); 自動生成されたコード
           // 期待されるのは要素ごとの同値性判定なので以下のようになる
           (Values == null && other.Values == null) ||
           (Values != null && other.Values != null && Values.SequenceEqual(other.Values)); 
}
```

配列に限らず`IEnumerable<T>`を実装するあらゆる型について言えることです。



###Visual Studioが生成した`Object.Equals()`は型チェックしないの？

Visual Studioが生成したコードはシンプルにこうなっています。

```cs
public override bool Equals(object obj)
{
    return Equals(obj as MyClass);
}
```

一方、MSDNやEffective C#のサンプルやReSharperが生成したコードはこんな感じです。

```cs
public override bool Equals(object obj)
{
    if (ReferenceEquals(null, obj)) return false;
    if (ReferenceEquals(this, obj)) return true;
    if (obj.GetType() != this.GetType()) return false;
    return Equals((MyClass) obj);
}
```

nullチェックと同一性判定は良いとして、`GetType()`で実行時の型チェックしているところがVisual Studioの生成したコードと大きく違います。以下のコードで動作が異なります。

```cs
((object)myBase).Equals(mySub)
```
```cs
object.Equals(myBase, mySub1) // 内部でObject.Equals()が呼ばれる
```

Visual Studio版では実行時の型チェックをしないので`true`になりますが、MSDN版では`false`になります。ただ、どちらが正しいと言い切るのは難しく、同値性判定で実行時の型チェックが期待されるか？という問題です。これは前項の継承の話と同類の問題なので、そもそもこのコードの違いが動作の違いとして現れる設計は避けたいところです。



###`GetHashCode()`のハッシュアルゴリズム

`GetHashCode()`はよく分散したハッシュ値を素早く返すことが求められます。

XORハッシュ（`Value1.GetHashCode() ^ Value2.GetHashCode()`みたいなの）を目にしたことがあるかもしれませんが、例えば`Value1`と`Value2`の値が同じ場合、値に関わらず計算結果はすべて0になり、結果が偏ってしまうので良くありません。

Visual Studioが生成する`GetHashCode()`のハッシュアルゴリズムはBernsteinハッシュです。ReSharperならFNVハッシュです。ちなみに`ValueTuple`の内部実装では`HashHelpers.Combine()`が使われており、Modified Bernsteinハッシュで実装されています。いずれも十分に分散したハッシュ値を比較的素早く得られるアルゴリズムのようです。

ref.
http://eternallyconfuzzled.com/tuts/algorithms/jsw_tut_hashing.aspx
[What is the best algorithm for an overridden System.Object.GetHashCode?]
(https://stackoverflow.com/questions/263400/what-is-the-best-algorithm-for-an-overridden-system-object-gethashcode)
[Why is '397' used for ReSharper GetHashCode override?](https://stackoverflow.com/questions/102742/why-is-397-used-for-resharper-gethashcode-override)



#リファレンス
[Object.Equals Method](https://docs.microsoft.com/en-us/dotnet/api/system.object.equals)
[ValueType.Equals(Object) Method](https://docs.microsoft.com/en-us/dotnet/api/system.valuetype.equals)
[等価比較 (C# プログラミング ガイド)](https://docs.microsoft.com/ja-jp/dotnet/csharp/programming-guide/statements-expressions-operators/equality-comparisons)



[^equality]: 「2つのインスタンスの」等価性・同一性・同値性という書き方が正確だが、`IEquatable<T>`は2つのインスタンスを比較するためのインターフェースであり本記事中では文脈から明らかと思われるので省略する。
[^operator]: [Object.Equals Method](https://docs.microsoft.com/en-us/dotnet/api/system.object.equals)やEffective C#によると、`Equals()`をオーバーライドしたとしても`==`/`!=`演算子をオーバーロードすべきケースは非常に少ないと説明されている。一方、[方法: 型の値の等価性を定義する (C# プログラミング ガイド)](https://docs.microsoft.com/ja-jp/dotnet/csharp/programming-guide/statements-expressions-operators/how-to-define-value-equality-for-a-type)では`==`/`!=`演算子をオーバーロードすることが推奨されている。矛盾しているようにも思え非常に混乱するが、前者は値オブジェクト以外で`Equals()`をオーバーライドすることを想定しているように読める。値オブジェクト以外ならば本記事中で説明しているように`==`/`!=`演算子をオーバーロードすべきでないが、そもそも値オブジェクト以外で`Equals()`をオーバーライドすべきでなく、良い設計へ導くためのガイドラインとしては不適切ではないだろうか。
[^issue31283]: 生成された`IEquatable<T>.Equals(T)`のnullチェックが`!=`演算子を使用しているため、`!=`演算子も生成してあると同値性判定になってしまい遅いので`is null`に書き換えて計測した。修正依頼済みで、マイルストーンに含まれているのでそのうち直る？（[Issue #31283](https://github.com/dotnet/roslyn/issues/31283)）。
[^valuetypeequals]: リフレクションとは、型自体の情報を取得すること。参照型のメンバを含まない場合リフレクションは発生せず高速に動作するが、メンテナンス性の観点からも`IEquatable<T>`を実装しておいた方が良いだろう。また、リフレクションによる同値性判定ではすべてのフィールド・プロパティの比較が行われるが、構造体が意味する値に期待される挙動とは異なる可能性がある。
[^boxing]: ボックス化とは、値型のインスタンスを参照型の入れ物にコピーして、参照型として扱えるようにすること。値型を参照型の変数に代入したりキャストしたりすると発生する。
[^stringbuilder]: `StringBuilder`には`Equals()`があり内部の文字列の同値性を比較できるが、これを悪い例として紹介する。可変型なので`IEquatable<T>`は実装されていないし`Object.Equals()`も`GetHashCode()`もオーバーライドされていないのでルール違反ではないが、この挙動が直観と一致する人はどれだけいるのだろうか。例えば`ValueEquals()`という名前だったらはるかに分かりやすく混乱しなかっただろう。
[^hash]: 2つのインスタンスのハッシュ値が同じであっても`Equals()`が`true`を返すとは限らない。ハッシュ値の等価性はインスタンスの等価性を表すわけではない。