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

Question

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

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

Является ли это действительным руководством?

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

Answer 1

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

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

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

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

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

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

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

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

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

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

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

---

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

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

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

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

Это значит:

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

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

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

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

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

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

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

Answer 2

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

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

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

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

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

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

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

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

Answer 3

Я думаю, что документация относительно 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, строки, Date и т. Д. ... являются неизменяемыми объектами).

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

Answer 4

С MSDN

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

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

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

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

---

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

Также из MSDN:

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

С Запись хеш-таблицы MSDN :

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

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

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

Answer 5

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

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

Answer 6

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

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

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

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

Answer 7

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

Answer 8

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

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

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

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

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

Answer 9

Check Руководства и правила для GetHashCode от Eric Lippert