Почему при переопределении Equals советуют также переопределять GetHashCode

#c_sharp #.net #c_sharp_faq

Почему при переопределении метода Equals() также советуют переопределять методGetHashCode()?
И еще один вытекающий вопрос:
Имея следующие поля    

public readonly int x, y;


На msdn.com метод GetHashCode() переопределяют следующим образом:    

public override int GetHashCode()
{
    return x ^ y;
}


А если бы поля выглядели бы таким образом:    

public readonly int x, y, z;


То переопределенный метод должен будет выглядеть так?    

public override int GetHashCode()
{
    return x ^ y ^ z;
}


Правильно я понял?
А что если тип данных у полей будет разным?
    

Ответы

Ответ 1

Дело в том, что любой объект в .NET можно положить в хеш-таблицу.

Допустим теперь, что у вас есть класс X, в котором переопределён метод Equals, но
не переопределён GetHashCode. Что будет в этом случае?

Пусть у вас есть два объекта x1 и x2 типа X, которые совпадают согласно функции Equals.
Поскольку вы не переопределили GetHashCode, то скорее всего их хэшкоды будут разными.

Если вы положите в HashSet значение x1, а потом будете искать там x2, то при этом
это значение не будет найдено, несмотря на то, что x1 и x2 у вас равны. Это произойдёт
потому, что при поиске в HashSet сначала ищется hash bucket, соответствующий хэшкоду,
и лишь в нём ищется сам элемент — это базовый принцип работы хэш-таблицы, обеспечивающий
её эффективность. Таким образом, элементы класса X нельзя будет нормально хранить в
хэш-таблицах.

То же относится и к Dictionary, который точно так же основан на хэш-таблице
и пользуется методом GetHashCode.



По поводу правильного определения GetHashCode, совет с MSDN не очень хорош. Дело
в том, что если у объекта есть два поля, то часто это маленькие числа, которые также
часто бывают равны. Поэтому при таком определении будет слишком мало различных значений
хэшкода, и много экземпляров X будут попадать в тот же самый hash bucket (что снижает
эффективность хэш-таблиц).

Рекомендованный метод, судя по всему, такой:

public override int GetHashCode()
{
    var hash = 19;
    // избегаем хэш-коллизий, используем (небольшое) простое число
    hash = hash * 37 + x.GetHashCode();
    hash = hash * 37 + y.GetHashCode();
    // обобщается на произвольное число полей
    return hash;
}


(19 и 37 — небольшие разные простые числа) Здесь типы полей неважны, т. к. на каждом
из них берётся хэшкод.

Обязательно придерживайтесь правила: если объекты равны по Equals, у них обязаны
быть одинаковые хэшкоды.



Ещё одно важное замечание: если вы кладёте в HashSet элемент, вы не должны менять
его состояние (значения полей) таким образом, чтобы его хэшкод изменился! Лучше всего,
разумеется, вовсе не менять его. Иначе при поиске этого элемента он просто не будет найден.



Дополнительное чтение по теме:


Хешкод, переопределение метода GetHashCode
What is the best algorithm for an overridden System.Object.GetHashCode?
Why is it important to override GetHashCode when Equals method is overridden?
Eric Lippert: Guidelines and rules for GetHashCode (перевод на русский: Правила и
рекомендации по переопределению GetHashCode)
Обзор альтернативных методов хэширования