Общие рекомендации и рекомендации по правильному переопределению объекта. GetHashCode()

Согласно MSDN, хеш-функция должна иметь следующие свойства:

Если два объекта сравниваются как равные, метод GetHashCode для каждого объекта должен возвращать одно и то же значение. Однако, если два объекта не сравниваются как равные, методы GetHashCode для двух объектов не должны возвращать разные значения.

Метод GetHashCode для объекта должен последовательно возвращать один и тот же хэш-код, если не существует модификации состояния объекта, которая определяет возвращаемое значение метода Equals объекта. Обратите внимание, что это верно только для текущего выполнения приложения и что другой хэш-код может быть возвращен, если приложение снова запущено.

Для лучшей производительности хеш-функция должна генерировать случайное распределение для всех входных данных.

Я продолжаю находить себя в следующем сценарии: я создал класс, реализованный IEquatable<T> и переопределенный object.Equals(object). MSDN утверждает, что:

Типы, которые переопределяют Equals, также должны переопределять GetHashCode; в противном случае Hashtable может работать некорректно.

И тогда он обычно немного останавливается для меня. Потому что, как вы правильно переопределяете object.GetHashCode()? Никогда не знаю, с чего начать, и кажется, что у него много подводных камней.

Здесь, в StackOverflow, существует немало вопросов, связанных с переопределением GetHashCode, но большинство из них, по-видимому, относятся к конкретным случаям и конкретным проблемам. Поэтому я хотел бы получить хорошую компиляцию здесь. Обзор с общим советом и рекомендациями. Что делать, что не делать, общие ловушки, где начать и т.д.

Я хотел бы, чтобы он был особенно направлен на С#, но я бы подумал, что он будет работать одинаково для других языков .NET(?).

Я думаю, что, может быть, лучший способ - создать один ответ на тему с быстрым и коротким ответом сначала (рядом с одним лайнером, если это вообще возможно), тогда, возможно, еще немного информации и закончите с соответствующими вопросами, обсуждениями, сообщениями в блоге и т.д., если они есть. Затем я могу создать одно сообщение в качестве принятого ответа (чтобы получить его сверху) только с "оглавлением". Постарайтесь держать его коротким и кратким. И не просто ссылку на другие вопросы и сообщения в блоге. Попытайтесь взять их суть, а затем скорее обратитесь к источнику (особенно потому, что источник может исчезнуть. Также попробуйте отредактировать и улучшить ответы вместо созданных очень похожих.

Я не очень хороший технический писатель, но я по крайней мере попытаюсь отформатировать ответы, чтобы они выглядели одинаково, создавали оглавление и т.д. Я также попытаюсь найти некоторые из связанных вопросов здесь, в SO, что ответы на некоторые из них и, возможно, вытащить сущность тех, которыми я могу управлять. Но поскольку я не очень стабилен в этой теме, я постараюсь держаться подальше по большей части: p

Ответ 1

Содержание

Вещи, которые я хотел бы покрыть, но еще не были:

Как создать целое число (как "преобразовать" объект в int было не очень очевидно для меня в любом случае).
В каких полях помещается хэш-код.
- Если это должно быть только в неизменяемых полях, что, если есть только изменчивые?
Как создать хорошее случайное распределение. (Свойство MSDN № 3)
- Часть к этому, кажется, выбирает хорошее магическое простое число (видели 17, 23 и 397), но как вы его выбираете, и что это точно?
Как убедиться, что хеш-код остается неизменным на протяжении всего жизненного цикла объекта. (Свойство MSDN № 2)
- Особенно, когда равенство основано на изменяемых полях. (Свойство MSDN # 1)
Как работать с полями, которые являются сложными типами (не среди встроенных типов С#).
- Сложные объекты и структуры, массивы, коллекции, списки, словари, общие типы и т.д.
- Например, даже если список или словарь могут быть только для чтения, это не означает, что это содержимое.
Как работать с унаследованными классами.
- Если вы каким-то образом включите base.GetHashCode() в свой хеш-код?
Не могли бы вы технически просто лениться и вернуться 0? В значительной степени нарушит базовый номер MSDN №3, но, по крайней мере, убедитесь, что # 1 и # 2 всегда верны: P
Общие ошибки и ошибки.

Ответ 2

Каковы эти магические числа, часто встречающиеся в реализациях GetHashCode?

Это простые числа. Основные номера используются для создания хэш-кодов, потому что простое число максимизирует использование пространства хеш-кода.

В частности, начните с малого простого числа 3 и рассмотрите только низкоуровневые nybbles результатов:

3 * 1 = 3 = 3 (mod 8) = 0011
3 * 2 = 6 = 6 (mod 8) = 1010
3 * 3 = 9 = 1 (mod 8) = 0001
3 * 4 = 12 = 4 (mod 8) = 1000
3 * 5 = 15 = 7 (mod 8) = 1111
3 * 6 = 18 = 2 (mod 8) = 0010
3 * 7 = 21 = 5 (mod 8) = 1001
3 * 8 = 24 = 0 (mod 8) = 0000
3 * 9 = 27 = 3 (mod 8) = 0011

И мы начинаем все заново. Но вы заметите, что последовательные множители нашего простого числа генерируют каждую возможную перестановку бит в нашем nybble, прежде чем начинать повторять. Мы можем получить тот же эффект с любым простым числом и любым количеством битов, что делает простые числа оптимальными для генерации почти случайных хеш-кодов. Причина, по которой мы обычно видим большие простые числа вместо небольших простых чисел, таких как 3 в приведенном выше примере, состоит в том, что для большего количества бит в нашем хеш-коде результаты, полученные при использовании небольшого простого числа, даже не псевдослучайны, - это просто увеличивая последовательность до тех пор, пока не произойдет переполнение. Для оптимальной случайности следует использовать простое число, которое приводит к переполнению для довольно малых коэффициентов, если вы не можете гарантировать, что ваши коэффициенты не будут небольшими.

Ссылки по теме:

Почему '397 используется для переопределения GetHashCode ReSharper?

Ответ 3

Отъезд Руководства и правила для GetHashCode Эрика Липперта

Ответ 4

Вы должны переопределять его всякий раз, когда у вас есть значимая мера равенства для объектов такого типа (т.е. вы переопределяете Equals). Если бы вы знали, что объект не будет хэширован по какой-либо причине, вы можете его оставить, но вряд ли вы это заранее узнаете.

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


public override int GetHashCode()
{
    int mc = //magic constant, usually some prime
    return mc * prop1.GetHashCode() * prop2.GetHashCode * ... * propN.GetHashCode();
}

Я обычно предполагаю, что умножение значений вместе приведет к довольно равномерному распределению, предполагая, что каждая функция hashcode свойства выполняет то же самое, хотя это может быть и неправильным. Используя этот метод, если свойства, определяющие равенство объектов, изменяются, тогда также может измениться хеш-код, что приемлемо для данного определения №2 в вашем вопросе. Он также охватывает все типы в едином виде.

Вы можете вернуть одно и то же значение для всех экземпляров, хотя это сделает некоторые алгоритмы, которые используют хеширование (например, словари) очень медленно - по сути, все экземпляры будут хэшироваться в одном и том же ведре, а затем поиск станет O (n) ожидаемого O (1). Это, конечно, отрицает любые преимущества использования таких структур для поиска.

Ответ 5

Почему мне нужно переопределить `object.GetHashCode()`?

Переопределение этого метода важно, поскольку следующее свойство всегда должно оставаться верным:

Если два объекта сравниваются как равные, метод GetHashCode для каждого объекта должен возвращать одно и то же значение.

Причина, указанная JaredPar в сообщении при реализации равенства, заключается в том, что

Многие классы используют хэш-код для классификации объекта. В частности, хеш-таблицы и словари имеют тенденцию размещать объекты в ведрах на основе их хеш-кода. Когда вы проверяете, находится ли объект в хеш-таблице, он сначала ищет его в ведре. Если два объекта равны, но имеют разные хеш-коды, они могут быть помещены в разные ковши, и словарь не сможет найти объект.

Ссылки по теме:

Ответ 6

A) Вы должны переопределить как Equals, так и GetHashCode, если вы хотите использовать равенство значений вместо стандартного равенства по умолчанию. С более поздней версией две ссылки на объекты сравниваются как равные, если оба они ссылаются на один и тот же экземпляр объекта. С первым они сравниваются как равные, если их значение одинаково, даже если они относятся к различным объектам. Например, вы, вероятно, хотите использовать равенство значений для объектов Date, Money и Point.

B) Чтобы реализовать равенство значений, вы должны переопределить Equals и GetHashCode. Оба должны зависеть от полей объекта, которые инкапсулируют значение. Например, Date.Year, Date.Month и Date.Day; или Money.Currency и Money.Amount; или Point.X, Point.Y и Point.Z. Вы также должны рассмотреть переопределяющий оператор ==, operator! =, Operator < и operator > .

C) Хэш-код не должен оставаться постоянным на протяжении всего жизненного цикла объекта. Однако он должен оставаться неизменным, пока он участвует в качестве ключа в хеше. Из MSDN doco для словаря: "Пока объект используется как ключ в словаре < (Of < (TKey, TValue > ) > ), он не должен каким-либо образом изменять его хеш-значение". Если вы должны изменить значение ключа, удалите запись из словаря, измените значение ключа и замените запись.

D) IMO, вы упростите свою жизнь, если ваши объекты ценности сами по себе являются неизменными.

Ответ 7

Когда я переопределяю `object.GetHashCode()`?

Как MSDN:

Типы, которые переопределяют Equals, также должны переопределять GetHashCode; в противном случае Hashtable может работать некорректно.

Ссылки по теме:

Когда переопределять GetHashCode()?

Ответ 8

В каких полях помещается хэш-код? Если это должно быть только на неизменяемых полях, что, если есть только изменчивые?

Он не должен основываться только на неизменяемых полях. Я бы основал его на полях, которые определяют результат метода equals.

Ответ 9

Как убедиться, что хэш-код остается неизменным на протяжении всего жизненного цикла объекта. (Свойство MSDN # 2) Особенно, когда равенство основано на изменяемых полях. (Свойство MSDN # 1)

Кажется, вы неправильно поняли Property # 2. Хэш-код не должен оставаться неизменным при жизни объектов. Он просто должен оставаться таким же, пока значения, определяющие результат метода equals, не изменяются. Таким образом, логически вы используете хэш-код только для этих значений. Тогда не должно быть проблем.

Ответ 10

public override int GetHashCode()
{
    return IntProp1 ^ IntProp2 ^ StrProp3.GetHashCode() ^ StrProp4.GetHashCode ^ CustomClassProp.GetHashCode;
}

Сделайте то же самое в методе customClass GetHasCode. Работает как шарм.