Dictionaryの仕組みとGetHashCode

Dictionary<TKey, TValue>へ入れたり取り出したりするとき、こんな感じになっている。

参考:https://referencesource.microsoft.com/#mscorlib/system/collections/generic/dictionary.cs,bcd13bb775d408f1

もしkey1.GetHashCode()の返すハッシュが途中で変わってしまった場合、値の入ったバケツが見つからなくなってしまう。そうならないよう、GetHashCode()はインスタンスの存続する限り同じ値を返さなければならないことが分かる。

もう1点、同じハッシュを返すキーが多いとEqualsでなめる回数が増えてしまう。そうならないよう、GetHashCode()は十分に分散したハッシュを返すべきであることが分かる。

デフォルトのGetHashCode()の実装では、インスタンスごとに固有の適当な値が返るようになっているため、これら両方を満たす。しかし、クラスをキーとする場合、参照の等価性により引き当てられるため、辞書に入れた時のキーのインスタンスそのものをキーとしないとアクセスできない。これを値の同値性で引き当てたい場合、同値と判定されるインスタンス同士が同じハッシュを返す必要があり、(IEquatableの実装に加えて)適切な実装でGetHashCode()をoverrideする必要がある。詳しくは下記の記事参照。

qiita.com