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

В книге Essential C # 3.0 и .NET 3.5 я прочитал, что:

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

Это действительное руководство?

Я пробовал пару встроенных типов в .NET, и они не вели себя так.

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

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

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

Обновление
Эрик Липперт опубликовал блог, который дает отличную информацию о GetHashCode.

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

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

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

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

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

Но обо всем по порядку. Указанное в этом вопросе неправильное указание.

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

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

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

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

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

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

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

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

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

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

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

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

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

Это значит:

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

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

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

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

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

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

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

Из MSDN

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

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

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

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

Редактировать :

Также из 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 заявляет, что это недопустимо.

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

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

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

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

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

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

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

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

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

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

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

Итак, вкратце:

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

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

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