Рекомендации GetHashCode в C#
https://stackoverflow.com/questions/462451
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Я прочитал в книге Essential C# 3.0 и .NET 3.5, что:
Возврат gethashcode () в течение срока службы конкретного объекта должен быть постоянным (одинаковым значением), даже если данные объекта изменяются.Во многих случаях вы должны кэшировать метод, возвращаясь к принуждению этого.
Это действительная рекомендация?
Я попробовал пару встроенных типов в .NET, и они себя не вели.
Решение
Ответ: в основном это действительная рекомендация, но, возможно, не действительное правило.Это также не рассказывает всю историю.
Суть в том, что для изменяемых типов вы не можете основывать хеш-код на изменяемых данных, поскольку два равных объекта должны возвращать один и тот же хеш-код, а хеш-код должен быть действительным в течение всего времени существования объекта.Если хэш-код изменится, вы получите объект, который потеряется в хешированной коллекции, поскольку он больше не находится в правильном хеш-ящике.
Например, объект A возвращает хэш, равный 1.Итак, он попадает в ячейку 1 хеш-таблицы.Затем вы меняете объект A так, чтобы он возвращал хэш, равный 2.Когда хеш-таблица ищет его, она ищет его в бункере 2 и не может его найти — объект теряется в бункере 1.Вот почему хеш-код не должен меняться. на весь срок существования объекта, и это лишь одна из причин, почему написание реализаций GetHashCode — это головная боль.
Обновлять
Эрик Липперт опубликовал блог который дает превосходную информацию о GetHashCode.
Дополнительное обновление
Я внес пару изменений выше:
- Я провел различие между руководством и правилом.
- Я прочеркнул "на время жизни объекта".
Руководство – это всего лишь руководство, а не правило.В действительности, GetHashCode должен следовать этим рекомендациям только тогда, когда ожидается, что объект будет следовать этим рекомендациям, например, когда он хранится в хеш-таблице.Если вы никогда не собираетесь использовать свои объекты в хеш-таблицах (или в чем-либо еще, что зависит от правил GetHashCode), ваша реализация не обязательно должна следовать рекомендациям.
Когда вы видите «на протяжении всего времени жизни объекта», вам следует читать «на время, в течение которого объекту необходимо взаимодействовать с хеш-таблицами» или что-то подобное.Как и большинство вещей, GetHashCode Речь идет о том, чтобы знать, когда следует нарушать правила.
Другие советы
Прошло много времени, но тем не менее я считаю необходимым дать правильный ответ на этот вопрос, включая объяснения почему и как.На данный момент лучшим ответом является исчерпывающая ссылка на MSDN - не пытайтесь устанавливать свои собственные правила, ребята из MS знали, что делали.
Но обо всем по порядку:Руководство, указанное в вопросе, неверно.
Теперь почему - их две
Сначала почему:Если хеш-код вычисляется таким образом, что он не меняется в течение всего времени существования объекта, даже если сам объект изменяется, это нарушит контракт равенства.
Помнить:«Если два объекта сравниваются как равные, метод GetHashCode для каждого объекта должен возвращать одно и то же значение.Однако если два объекта не сравниваются как равные, методы GetHashCode для двух объектов не обязаны возвращать разные значения».
Второе предложение часто ошибочно интерпретируется как «Единственное правило состоит в том, что во время создания объекта хэш-код равных объектов должен быть равным».Не знаю почему, но это и есть суть большинства ответов здесь.
Представьте себе два объекта, содержащих имя, где это имя используется в методе равенства:То же имя -> то же самое.Создать экземпляр А:Name = Joe Create Encement B:Имя = Питер
Хэш-код A и Хэш-код B, скорее всего, не будут одинаковыми.Что теперь произойдет, если имя экземпляра B изменится на Joe?
Согласно руководству из вопроса, хэш-код B не изменится.Результатом этого будет:A.Equals (b) ==> true, но в то же время:A.GetHashCode() == B.GetHashCode() ==> false.
Но именно такое поведение явно запрещено контрактом равенства и хеш-кода.
Во-вторых, почему:Конечно, верно, что изменения в хеш-коде могут привести к поломке хеш-списков и других объектов, использующих хэш-код, но верно и обратное.Если не изменить хеш-код, в худшем случае будут получены хешированные списки, в которых все множество различных объектов будут иметь один и тот же хеш-код и, следовательно, находиться в одном и том же хэш-корзине - например, это происходит, когда объекты инициализируются стандартным значением.
Теперь, как хорошо, на первом взгляде, кажется, существует противоречие - в любом случае, код сломается.Но ни одна из проблем не возникает из-за измененного или неизмененного хэш-кода.
Источник проблем хорошо описан в MSDN:
Из записи хеш-таблицы MSDN:
Ключевые объекты должны быть неизменными, если они используются в качестве ключей в хэштере.
Это означает:
Любой объект, создающий хэш-значение, должен изменять хэш-значение при изменении объекта, но он не должен - абсолютно не должен - допускать какие-либо изменения в себе, когда он используется внутри хеш-таблицы (или любого другого объекта, использующего хэш, конечно). .
Во -первых, как, конечно, самым простым способом разработки неподвижных объектов только для использования в хэш -стенах, которые будут созданы как копии нормальных, изменяемых объектов, когда это необходимо.Внутри неизменяемых объектов, очевидно, можно кэшировать хэш-код, поскольку он неизменяем.
Во-вторых, как или дайте объекту «вы хэшируете сейчас»-FLAG, убедитесь, что все данные объекта являются приватными, проверьте флаг во всех функциях, которые могут изменить данные объектов, и добавлять данные исключения, если изменение не разрешено (т.е.флаг установлен).Теперь, когда вы помещаете объект в любую хешированную область, обязательно установите флаг, а также снимите его, когда он больше не нужен.Для удобства использования я бы посоветовал автоматически устанавливать флаг внутри метода GetHashCode — чтобы его нельзя было забыть.А явный вызов метода ResetHashFlag позволит программисту задуматься, можно или нельзя сейчас изменять данные объектов.
Хорошо, что еще следует сказать:Бывают случаи, когда можно иметь объекты с изменяемыми данными, где хеш-код, тем не менее, остается неизменным, когда данные объекта изменяются, без нарушения контракта равенства и хэш-кода.
Однако для этого требуется, чтобы метод Equals также не основывался на изменяемых данных.Итак, если я пишу объект и создаю метод GetHashCode, который вычисляет значение только один раз и сохраняет его внутри объекта, чтобы вернуть его при последующих вызовах, тогда я снова должен:абсолютно необходимо создать метод Equals, который будет использовать сохраненные значения для сравнения, чтобы A.Equals(B) никогда не менялся с false на true.В противном случае контракт будет разорван.Результатом этого обычно будет то, что метод Equals не имеет никакого смысла — это не исходная ссылка, равная, но и не равное значение.Иногда это может быть намеренное поведение (т.е.записи клиентов), но обычно это не так.
Итак, просто измените результат GetHashCode, когда данные объекта изменяются, и если предполагается (или просто возможно) использование объекта внутри хеша с использованием списков или объектов, тогда сделайте объект либо неизменяемым, либо создайте флаг только для чтения, который будет использоваться для время жизни хеш-списка, содержащего объект.
(Кстати:Все это не является специфичным для C# или .NET - это характерно для всех реализаций хэш-таблиц или, в более общем смысле, для любого индексированного списка, что идентифицирующие данные объектов никогда не должны меняться, пока объект находится в списке.Если это правило будет нарушено, произойдет неожиданное и непредсказуемое поведение.Где-то могут существовать реализации списков, которые отслеживают все элементы внутри списка и выполняют автоматическую переиндексацию списка, но производительность таких списков в лучшем случае наверняка будет ужасной.)
Из MSDN
Если два объекта сравниваются как равные, Метод GetHashCode для каждого объекта должен вернуть то же значение. Тем не мение, если два объекта не сравниваются как равны, методы GetHashCode для два объекта не должны возвращаться разные значения.
Метод GetHashCode для объекта должен последовательно возвращать один и тот же хеш код до тех пор, пока нет изменение состояния объекта, что определяет возвращаемое значение метод Equals объекта. Обратите внимание, что это верно только для текущего выполнения приложения, и что другой хэш-код может быть возвращен, если приложение запускается снова.
Для лучшей производительности, хеш функция должна генерировать случайный распределение для всего ввода.
Это означает, что если значения объекта изменятся, хеш-код должен измениться. Например, & Quot; Person & Quot; класс с " имя " свойство установлено в " Tom " должен иметь один хэш-код и другой код, если вы измените имя на " Jerry " ;. В противном случае, Том == Джерри, что, вероятно, не то, что вы хотели бы.
<Ч>Изменить .
Также из MSDN:
Производные классы, которые переопределяют GetHashCode, также должны переопределять Equals, чтобы гарантировать, что два объекта, считающихся равными, имеют одинаковый хэш-код; в противном случае тип Hashtable может работать некорректно.
Ключевые объекты должны быть неизменяемыми, если они используются в качестве ключей в Hashtable.
Я прочитал это так, что изменяемые объекты должны возвращать разные хеш-коды при изменении их значений, если они не предназначены для использования в хеш-таблице.
В примере System.Drawing.Point объект является изменяемым, и действительно возвращает другой хэш-код при изменении значения X или Y. Это сделает его плохим кандидатом для использования в хеш-таблице как есть.
Я думаю, что документация, касающаяся GetHashcode, немного сбивает с толку.
С одной стороны, MSDN утверждает, что хэшкод объекта никогда не должен меняться, а с другой стороны, MSDN также утверждает, что возвращаемое значение геташкода должно быть равным для 2 объектов, если эти 2 объекта считаются равными.
Хэш-функция должна иметь следующие свойства:
- Если два объекта сравниваются как равные, метод 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 экземпляра1 установлено значение «Pol», а для свойства Name экземпляра2 установлено значение «Piet».Оба экземпляра возвращают разные хэш-коды, и они также не равны.Теперь предположим, что я изменил Имя экземпляра2 на «Pol», тогда, согласно моему методу Equals, оба экземпляра должны быть равны, и согласно одному из правил MSDN, они должны возвращать один и тот же хеш-код.
Однако сделать это невозможно, поскольку хэш-код экземпляра2 изменится, а MSDN заявляет, что это недопустимо.
Затем, если у вас есть сущность, вы могли бы реализовать хэш-код так, чтобы он использовал «основной идентификатор» этой сущности, который в идеале может быть суррогатным ключом или неизменяемым свойством.Если у вас есть объект значения, вы можете реализовать Hashcode, чтобы он использовал «свойства» этого объекта значения.Эти свойства составляют «определение» объекта значения.Это, конечно, природа объекта-ценности;вас интересует не его идентичность, а его ценность.
И, следовательно, объекты-значения должны быть неизменяемыми.(Точно так же, как в .NET framework, строке, дате и т. д.).все являются неизменяемыми объектами).
Еще что приходит на ум:
Во время какого «сеанса» (я действительно не знаю, как мне это назвать) должен «GetHashCode» возвращать постоянное значение.Предположим, вы открываете свое приложение, загружаете экземпляр объекта из БД (сущность) и получаете его хэш-код.Он вернет определенное число.Закройте приложение и загрузите тот же объект.Требуется ли, чтобы хеш-код на этот раз имел то же значение, что и при первой загрузке объекта?ИМХО, нет.
Это хороший совет. Вот что Брайан Пепин должен сказать по этому вопросу:
Это сбило меня с толку больше, чем один раз: убедитесь, что GetHashCode всегда возвращает то же значение через время жизни экземпляра. Помни что хеш-коды используются для идентификации & Quot; & Ковши Quot; в самой хэш-таблице Реализации. Если объект & Quot; & Ковш Quot; изменения, хеш-таблица не может быть в состоянии найти свой объект. Эти могут быть очень трудно найти ошибки, так что получите прямо с первого раза.
Непосредственно не отвечая на ваш вопрос, но - если вы используете Resharper, не забывайте, что у него есть функция, которая генерирует разумную реализацию GetHashCode (а также метод Equals) для вас. Конечно, вы можете указать, какие члены класса будут учитываться при вычислении хеш-кода.
Ознакомьтесь с этой записью в блоге Марка Брукса:
VTO, RTO и GetHashCode () - - Боже мой!
А затем ознакомьтесь с последующим сообщением (не могу связать, поскольку я новичок, но в статье initlal есть ссылка), в котором обсуждаются более подробно и рассматриваются некоторые незначительные недостатки в первоначальной реализации.
Это было все, что мне нужно было знать о создании реализации GetHashCode (), он даже обеспечивает загрузку своего метода вместе с некоторыми другими утилитами, вкратце.
Хеш-код никогда не меняется, но также важно понимать, откуда взялся хэш-код.
Если ваш объект использует семантику значений, то есть идентичность объекта определяется его значениями (такими как String, Color, все структуры). Если идентификатор вашего объекта не зависит от всех его значений, то хэш-код идентифицируется подмножеством его значений. Например, ваша запись StackOverflow хранится где-то в базе данных. Если вы измените свое имя или адрес электронной почты, ваша запись клиента останется прежней, хотя некоторые значения изменились (в конечном итоге вы обычно идентифицируетесь по какому-то длинному идентификатору клиента #).
Короче говоря:
Семантика типа значения - хэш-код определяется значениями Семантика ссылочного типа - хеш-код определяется некоторым идентификатором
Я предлагаю вам прочесть Эрик Эванс, основанный на доменном дизайне, где он рассматривает сущности и типы значений (что более или менее я пытался сделать выше), если это все еще не имеет смысла.
Ознакомьтесь с рекомендациями и правилами для GetHashCode Эрик Липперт
