Рекомендации GetHashCode в C #

Ответ в основном таков: это действительное руководство, но, возможно, не действительное правило. Это также не говорит всей истории.

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

Например, объект A возвращает хэш 1. Итак, он попадает в корзину 1 хеш-таблицы. Затем вы изменяете объект A таким образом, чтобы он возвращал хеш-значение 2. Когда хеш-таблица ищет его, она ищет его в корзине 2 и не может найти - объект находится в корзине 1. Вот почему хеш-код должен не менять на время существования объекта, и это лишь одна из причин, по которой написание реализаций GetHashCode является головной болью.

Обновление
Эрик Липперт разместил блог, в котором содержится отличная информация о GetHashCode.

Дополнительное обновление
Я внес несколько изменений выше:

1. Я проводил различие между руководством и правилом.
2. Я зачеркнул «на время жизни объекта».

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

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

Прошло много времени, но, тем не менее, я думаю, что все же необходимо дать правильный ответ на этот вопрос, в том числе объяснить, почему и как. Лучшим ответом на данный момент является тот, который исчерпывающе цитирует MSDN - не пытайтесь устанавливать свои собственные правила, ребята из MS знали, что они делают.

Но обо всем по порядку: Руководство, указанное в вопросе, неверно.

Теперь почему - их два

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

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

Второе предложение часто ошибочно интерпретируется как «Единственное правило состоит в том, что во время создания объекта хэш-коды одинаковых объектов должны быть одинаковыми». Не знаю, почему, но это и есть суть большинства ответов здесь.

Подумайте о двух объектах, содержащих имя, где имя используется в методе equals: То же имя -> то же самое. Создать экземпляр A: Name = Joe Создать экземпляр B: Name = Peter

Хэш-код A и Hashcode B, скорее всего, не будут одинаковыми. Что теперь произойдет, если имя экземпляра B будет изменено на Joe?

Согласно руководству из вопроса, хэш-код B не изменится. Результатом этого будет: A.Equals (B) ==> true Но в то же время: A.GetHashCode () == B.GetHashCode () ==> false.

Но именно такое поведение явно запрещено контрактом equals & hashcode.

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

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

Источник проблем хорошо описан в MSDN:

Из записи хеш-таблицы MSDN:

Ключевые объекты должны быть неизменными, пока они используются в качестве ключей в Hashtable.

Это означает:

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

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

Во-вторых, как Или дайте объекту флаг «вы сейчас хешированы», убедитесь, что все данные объекта являются приватными, проверьте флаг во всех функциях, которые могут изменять данные объектов, и выдать данные исключения, если изменение не разрешено (т. Е. Установлен флаг ). Теперь, когда вы помещаете объект в любую хешированную область, обязательно установите флаг, а также снимите флаг, когда он больше не нужен. Для простоты использования я бы посоветовал установить флаг автоматически внутри метода GetHashCode - таким образом его нельзя забыть. А явный вызов метода «ResetHashFlag» гарантирует, что программисту придется подумать, разрешено или не разрешено изменять данные объекта на данный момент.

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

Однако это требует, чтобы метод equals также не основывался на изменяемых данных. Итак, если я напишу объект и создаю метод GetHashCode, который вычисляет значение только один раз и сохраняет его внутри объекта, чтобы вернуть его при последующих вызовах, тогда я снова должен: абсолютно необходимо создать метод Equals, который будет использовать сохраненные значения для сравнения, так что A.Equals (B) также никогда не изменится с false на true. В противном случае контракт был бы разорван. Результатом этого обычно будет то, что метод Equals не имеет никакого смысла - это не исходная ссылка, равная, но и не равная по значению. Иногда это может быть запланированное поведение (например, записи о клиентах), но обычно это не так.

Итак, просто измените результат GetHashCode, когда данные объекта изменяются, и если использование объекта внутри хэша с использованием списков или объектов предполагается (или только возможно), тогда сделайте объект либо неизменяемым, либо создайте флаг только для чтения для использования для время жизни хешированного списка, содержащего объект.

(Между прочим: все это не относится к C # или .NET - это характерно для всех реализаций хэш-таблиц или, в более общем смысле, для любого индексированного списка, что идентифицирующие данные объектов никогда не должны изменяться, пока объект находится в списке . Неожиданное и непредсказуемое поведение произойдет, если это правило будет нарушено. Где-то могут быть реализации списков, которые отслеживают все элементы внутри списка и выполняют автоматическую переиндексацию списка - но производительность этих элементов наверняка будет в лучшем случае ужасной.)

Из MSDN

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

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

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

Это означает, что если значение (я) объекта изменится, хэш-код должен измениться. Например, класс «Человек» со свойством «Имя», установленным на «Том», должен иметь один хэш-код и другой код, если вы измените имя на «Джерри». В противном случае Том == Джерри, что, вероятно, не то, что вы хотели.

Изменить:

Также из MSDN:

Производные классы, которые переопределяют GetHashCode, также должны переопределять Equals, чтобы гарантировать, что два объекта, которые считаются равными, имеют одинаковый хэш-код; в противном случае тип Hashtable может работать некорректно.

Из записи в хэш-таблице MSDN:

Ключевые объекты должны быть неизменными, пока они используются в качестве ключей в Hashtable.

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

В примере System.Drawing.Point объект является изменяемым, и действительно возвращает другой хэш-код при изменении значения X или Y. Это сделало бы его плохим кандидатом для использования в хэш-таблице.

Я думаю, что документация по GetHashcode немного сбивает с толку.

С одной стороны, MSDN заявляет, что хэш-код объекта никогда не должен изменяться и быть постоянным. С другой стороны, MSDN также заявляет, что возвращаемое значение GetHashcode должно быть равным для 2 объектов, если эти 2 объекта считаются равными.

MSDN:

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

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

Тогда это означает, что все ваши объекты должны быть неизменяемыми или метод GetHashcode должен основываться на неизменяемых свойствах вашего объекта. Предположим, например, что у вас есть этот класс (наивная реализация):

public class SomeThing
{
      public string Name {get; set;}

      public override GetHashCode()
      {
          return Name.GetHashcode();
      }

      public override Equals(object other)
      {
           SomeThing = other as Something;
           if( other == null ) return false;
           return this.Name == other.Name;
      }
}

Эта реализация уже нарушает правила, которые можно найти в MSDN. Предположим, у вас есть 2 экземпляра этого класса; для свойства Name экземпляра instance1 установлено значение «Pol», а для свойства Name экземпляра instance2 установлено значение «Piet». Оба экземпляра возвращают другой хэш-код, и они также не равны. Теперь предположим, что я изменяю имя instance2 на «Pol», тогда, согласно моему методу Equals, оба экземпляра должны быть равны, и согласно одному из правил MSDN они должны возвращать один и тот же хэш-код.
Однако , этого сделать нельзя, так как хэш-код instance2 изменится, а MSDN заявляет, что это запрещено.

Затем, если у вас есть сущность, вы могли бы реализовать хэш-код так, чтобы он использовал «первичный идентификатор» этой сущности, который в идеале может быть суррогатным ключом или неизменяемым свойством. Если у вас есть объект значения, вы можете реализовать хэш-код, чтобы он использовал «свойства» этого объекта значения. Эти свойства составляют «определение» объекта значения. Это, конечно, природа ценностного объекта; вас интересует не его идентичность, а его ценность.
И, следовательно, объекты-значения должны быть неизменяемыми. (Как и в платформе .NET, строка, дата и т. Д. Являются неизменяемыми объектами).

Еще одна вещь, которая приходит в голову:
Во время какого «сеанса» (я действительно не знаю, как это назвать) должен «GetHashCode» возвращать постоянное значение. Предположим, вы открываете свое приложение, загружаете экземпляр объекта из БД (сущность) и получаете его хэш-код. Он вернет определенное число. Закройте приложение и загрузите ту же сущность. Требуется ли, чтобы на этот раз хэш-код имел то же значение, что и при первой загрузке объекта? ИМХО нет.

Это хороший совет. Вот что говорит по этому поводу Брайан Пепин:

Это несколько раз сбивало меня с толку: убедитесь, что GetHashCode всегда возвращает одно и то же значение в течение всего времени существования экземпляра. Помните, что хэш-коды используются для идентификации «корзин» в большинстве реализаций хеш-таблиц. Если "корзина" объекта изменяется, хеш-таблица может не найти ваш объект. Это могут быть очень сложные ошибки, поэтому исправьте их с первого раза.

Не отвечая напрямую на ваш вопрос, но - если вы используете Resharper, не забывайте, что у него есть функция, которая генерирует разумную реализацию GetHashCode (а также метод Equals) для вас. Конечно, вы можете указать, какие члены класса будут учитываться при вычислении хэш-кода.

Посмотрите это сообщение в блоге Марка Брукса:

VTO, RTO и GetHashCode () - о, мой!

А затем ознакомьтесь с последующим постом (не могу ссылаться, поскольку я новичок, но есть ссылка в статье initlal), в котором обсуждается дальнейшее и рассматриваются некоторые незначительные недостатки в первоначальной реализации.

Это было все, что мне нужно было знать о создании реализации GetHashCode (), он даже предоставляет загрузку своего метода вместе с некоторыми другими утилитами, короче говоря, золото.

Хэш-код никогда не меняется, но также важно понимать, откуда берется хэш-код.

Если ваш объект использует семантику значений, т.е. идентичность объекта определяется его значениями (например, String, Color, все структуры). Если идентификатор вашего объекта не зависит от всех его значений, то хэш-код идентифицируется подмножеством его значений. Например, ваша запись StackOverflow хранится где-то в базе данных. Если вы измените свое имя или адрес электронной почты, запись о клиенте останется прежней, хотя некоторые значения изменились (в конечном итоге вы обычно идентифицируетесь по длинному идентификатору клиента #).

Вкратце:

Семантика типа значения - хэш-код определяется значениями Семантика ссылочного типа - хэш-код определяется некоторым идентификатором

Я предлагаю вам прочитать Domain Driven Design Эрика Эванса, где он переходит к сущностям и типам значений (что более или менее то, что я пытался сделать выше), если это все еще не имеет смысла.

Ознакомьтесь с рекомендациями и правилами для GetHashCode Эрика Липперта.