9. Тонкости GetHashCode(). Начало
GetHashCode() – одна из тех функций, которую, по возможности, не стоит реализовывать самостоятельно. Она используется только в одном месте: для определения значения хеш-функции для ключей в коллекциях на основе хеша (обычно это HashSet<T> или Dictionary<K,V>). Есть ряд проблем с реализацией GetHashCode() в базовом классе. Для ссылочных типов она работает, но не очень эффективно. Для типов значений есть специальные оптимизации, если он не имеет ссылочных полей, в противном случае функция работает медленно и не всегда верно. Но дело не только в этом. Скорее всего, вы не сможете самостоятельно реализовать GetHashCode() и эффективно, и правильно.Контейнеры используют хэш-коды для оптимизации поиска по коллекции, так что он занимает время близкое к постоянному, независимо от размера. Если вы определяете тип, который никогда не будет использоваться в качестве ключа в контейнере, ничего делать не нужно: ссылочные типы будут иметь правильный хеш-код, значимые типы должны быть неизменяемыми, и в этом случае реализация по умолчанию всегда будет работать. В большинстве типов, которые вы создаёте, лучшим подходом будет игнорирование существования
GetHashCode().В .NET каждый объект имеет хеш-код, определённый в
System.Object.GetHashCode(). Любая перегрузка GetHashCode() должна следовать трём правилам:1. Если два объекта равны (как определено экземплярным методом
Equals()), они должны генерировать один и тот же хеш-код.Версия оператора
== в System.Object проверяет идентичность объектов. GetHashCode() возвращает внутреннее поле - идентификатор объекта, и это правило работает. Однако, если вы переопределили метод Equals(), нужно переопределить и GetHashCode(), чтобы обеспечить соблюдение правила.2. Для любого объекта
A хеш-код должен быть инвариантен. То есть, независимо от того, какие методы вызываются на объекте, A.GetHashCode() всегда должен возвращать одно и то же значение. К примеру, изменение значения поля не должно приводить к изменению хэш-кода.3. Хеш-функция должна генерировать равномерное распределение среди всех целых чисел для всех типичных входных наборов. Это более-менее соблюдается для
System.Object.Написание правильной и эффективной хэш-функции требует глубоких знаний о типе, чтобы обеспечить соблюдение правила 3. Стандартные версии не эффективны, потому что должны обеспечивать лучшее поведение по умолчанию, практически не зная вашего конкретного типа.
Для типов-значений стандартная версия
GetHashCode возвращает хэш-код только первого ненулевого поля, смешивая его с идентификатором типа. Проблема в том, что в этом случае начинает играть роль порядок полей типа. Если значение первого поля экземпляров одинаково, то хэш-функция будет выдавать одинаковый результат. Таким образом, если большинство экземпляров типа имеют одинаковое значение первого поля, то производительность поиска по хэш-набору или хэш-таблице из таких элементов резко упадет (см. тест в статье на Хабре).Окончание следует…
Источники:
- Bill Wagner “More Effective C#”. – 2nd ed. Глава 10.
- https://habr.com/ru/company/microsoft/blog/418515/