Для чего существует GetHashCode() — C# — Киберфорум

Я понял что он разных для каждые объектов и его советуют переопределят если нужно использовать для сравнение.

Это должен быть лишь кодовый идентификатор для объекта,если так можно сказать?
Я могу писать и так

21.08.2012, 15:23

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

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

Как перегрузить методы Equals() и GetHashCode(), для сравнения свойств объектов?
Есть два объекта класса Квадрат.Необходимо сравнить их по площади заданной свойством. Для этого.

Для чего существует метод html.hidden?
Можете обьяснить для чего метод html.hidden(желательно на примерах).Смотрел msdn не сильно понял.

21.08.2012, 19:11 2

Решение

21.08.2012, 20:27 [ТС] 3

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

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

GetHashCode неявно вызывает Equals если совпадают? 0о

Добавлено через 48 секунд
И когда имеет смысл переопределять GetHashCode();
только для своих объектов,правильно?

21.08.2012, 21:00 4

Решение

GetHashCode, конечно, не вызывает Equals. Это делает соответствующий алгоритм при поиске, например, ключа в словаре — сначала сравнивает хэши, потом, если необходимо Equals.

Добавлено через 6 минут
Простейшие примеры реализации:
-если у вас в классе одно целое поле int i, то в GetHashCode вы его и возвращаете: return i
-если у вас в классе два целых поля int i и int j, то вы возвращаете XOR: return i^j
и так далее.
Очевидно что если у двух объектов поля i равны и поля j равны, то и i^j, то есть хэши, будут равны. С другой стороны, если хотя бы одно из полей не совпадает, то с высокой долей вероятности и i^j не будет совпадать. Плюс сравнить хэш коды быстрее, чем сравнить две пары целых. Что и требуется для хорошей хэш-функции.

Добавлено через 3 минуты
А про переопределение GetHashCode четко сказано в документации — если переопределяете Equals (то есть задаете свое правило сравнения объектов), то и GetHashCode надо переопределить (чтобы он новому вашему правилу соответствовал). А если не переопределяете, то и не надо GetHashCode трогать. Все объекты будут по ссылке сравниваться.

Object. Get Hash Code Метод

Определение

Служит хэш-функцией по умолчанию. Serves as the default hash function.

Возвращаемое значение

Хэш-код для текущего объекта. A hash code for the current object.

Примеры

Один из самых простых способов вычисления хэш-кода для числового значения, имеющего тот же или меньший диапазон, чем тип Int32, просто возвращает это значение. One of the simplest ways to compute a hash code for a numeric value that has the same or a smaller range than the Int32 type is to simply return that value. В следующем примере показана такая реализация для структуры Number . The following example shows such an implementation for a Number structure.

Часто тип имеет несколько полей данных, которые могут участвовать в формировании хэш-кода. Frequently, a type has multiple data fields that can participate in generating the hash code. Один из способов создания хэш-кода заключается в объединении этих полей с помощью операции XOR (eXclusive OR) , как показано в следующем примере. One way to generate a hash code is to combine these fields using an XOR (eXclusive OR) operation, as shown in the following example.

Предыдущий пример возвращает один и тот же хэш-код для (N1, N2) и (N2, N1), и поэтому может создавать больше конфликтов, чем желательно. The previous example returns the same hash code for (n1, n2) and (n2, n1), and so may generate more collisions than are desirable. Доступно несколько решений, чтобы хэш-коды в этих случаях не совпадали. A number of solutions are available so that hash codes in these cases are not identical. Один из них — возврат хэш-кода объекта Tuple , который отражает порядок каждого поля. One is to return the hash code of a Tuple object that reflects the order of each field. В следующем примере показана возможная реализация, использующая класс Tuple . The following example shows a possible implementation that uses the Tuple class. Однако обратите внимание, что затраты на производительность при создании экземпляра объекта Tuple могут существенно повлиять на общую производительность приложения, в котором хранятся большие числа объектов в хэш-таблицах. Note, though, that the performance overhead of instantiating a Tuple object may significantly impact the overall performance of an application that stores large numbers of objects in hash tables.

Второе альтернативное решение включает в себя весовые значения для отдельных хэш-кодов, сдвигяя хэш-коды последовательных полей двумя или более битами. A second alternative solution involves weighting the individual hash codes by left-shifting the hash codes of successive fields by two or more bits. Оптимально, биты, сдвинутые за пределы 31 бита, должны переноситься, а не удаляться. Optimally, bits shifted beyond bit 31 should wrap around rather than be discarded. Поскольку биты отбрасываются операторами сдвига влево как в, так C# и в Visual Basic, для этого требуется создать метод сдвига влево, как в следующем примере: Since bits are discarded by the left-shift operators in both C# and Visual Basic, this requires creating a left shift-and-wrap method like the following:

В следующем примере используется этот метод сдвига и переноса для вычисления хэш-кода структуры Point , используемой в предыдущих примерах. The following example then uses this shift-and-wrap method to compute the hash code of the Point structure used in the previous examples.

Комментарии

Хэш-код — это числовое значение, которое используется для вставки и обнаружения объекта в коллекции на основе хэша, такой как класс Dictionary , класс Hashtable или тип, производный от класса DictionaryBase. A hash code is a numeric value that is used to insert and identify an object in a hash-based collection such as the Dictionary class, the Hashtable class, or a type derived from the DictionaryBase class. Метод GetHashCode предоставляет этот хэш-код для алгоритмов, требующих быстрых проверок равенства объектов. The GetHashCode method provides this hash code for algorithms that need quick checks of object equality.

Сведения о том, как хэш-коды используются в хэш-таблицах и некоторых дополнительных алгоритмах хэш-кода, см. в записи хэш-функции в Википедии. For information about how hash codes are used in hash tables and for some additional hash code algorithms, see the Hash Function entry in Wikipedia.

Два объекта, которые равны, возвращают хэш-коды, равные. Two objects that are equal return hash codes that are equal. Однако обратная неверно: равные хэш-коды не подразумевают равенство объектов, так как разные (неравные) объекты могут иметь одинаковые хэш-коды. However, the reverse is not true: equal hash codes do not imply object equality, because different (unequal) objects can have identical hash codes. Более того, .NET не гарантирует реализацию метода GetHashCode по умолчанию, и значение, возвращаемое этим методом, может отличаться между реализациями .NET, такими как различные версии .NET Framework и .NET Core, а также платформы, такие как 32-разрядные и 64-разрядные платформы. Furthermore, .NET does not guarantee the default implementation of the GetHashCode method, and the value this method returns may differ between .NET implementations, such as different versions of .NET Framework and .NET Core, and platforms, such as 32-bit and 64-bit platforms. По этим причинам не следует использовать реализацию этого метода по умолчанию в качестве уникального идентификатора объекта для хэширования. For these reasons, do not use the default implementation of this method as a unique object identifier for hashing purposes. Ниже приведено два последствия. Two consequences follow from this:

Не следует рассчитывать, что равные хэш-коды подразумевают равенство объектов. You should not assume that equal hash codes imply object equality.

Никогда не следует сохранять или использовать хэш-код вне домена приложения, в котором он был создан, так как один и тот же объект может быть хэширован между доменами приложений, процессами и платформами. You should never persist or use a hash code outside the application domain in which it was created, because the same object may hash across application domains, processes, and platforms.

Хэш-код предназначен для эффективной вставки и уточняющего запроса в коллекциях, основанных на хэш-таблице. A hash code is intended for efficient insertion and lookup in collections that are based on a hash table. Хэш-код не является постоянным значением. A hash code is not a permanent value. По этой причине: For this reason:

  • Не сериализуются значения хэш-кода или не сохраняйте их в базах данных. Do not serialize hash code values or store them in databases.
  • Не используйте хэш-код в качестве ключа для получения объекта из коллекции с ключом. Do not use the hash code as the key to retrieve an object from a keyed collection.
  • Не отправляйте хэш-коды между доменами приложений или процессами. Do not send hash codes across application domains or processes. В некоторых случаях хэш-коды могут быть вычислены отдельно для каждого процесса или домена приложения. In some cases, hash codes may be computed on a per-process or per-application domain basis.
  • Не используйте хэш-код вместо значения, возвращаемого криптографической функцией хэширования, если требуется криптографически надежный хэш. Do not use the hash code instead of a value returned by a cryptographic hashing function if you need a cryptographically strong hash. Для криптографических хэшей используйте класс, производный от класса System.Security.Cryptography.HashAlgorithm или System.Security.Cryptography.KeyedHashAlgorithm. For cryptographic hashes, use a class derived from the System.Security.Cryptography.HashAlgorithm or System.Security.Cryptography.KeyedHashAlgorithm class.
  • Не проверяйте равенство хэш-кодов, чтобы определить, равны ли два объекта. Do not test for equality of hash codes to determine whether two objects are equal. (Неравные объекты могут иметь идентичные хэш-коды.) Чтобы проверить на равенство, вызовите метод ReferenceEquals или Equals. (Unequal objects can have identical hash codes.) To test for equality, call the ReferenceEquals or Equals method.

Метод GetHashCode может быть переопределен производным типом. The GetHashCode method can be overridden by a derived type. Если GetHashCode не переопределяется, хэш-коды для ссылочных типов вычисляются путем вызова метода Object.GetHashCode базового класса, который выполняет вычисление хэш-кода на основе ссылки на объект; Дополнительные сведения см. в разделе RuntimeHelpers.GetHashCode. If GetHashCode is not overridden, hash codes for reference types are computed by calling the Object.GetHashCode method of the base class, which computes a hash code based on an object’s reference; for more information, see RuntimeHelpers.GetHashCode. Иными словами, два объекта, для которых метод ReferenceEquals возвращает true , имеют одинаковые хэш-коды. In other words, two objects for which the ReferenceEquals method returns true have identical hash codes. Если типы значений не переопределяют GetHashCode, метод ValueType.GetHashCode базового класса использует отражение для вычисления хэш-кода на основе значений полей типа. If value types do not override GetHashCode, the ValueType.GetHashCode method of the base class uses reflection to compute the hash code based on the values of the type’s fields. Иными словами, типы значений, поля которых имеют одинаковые значения, имеют одинаковые хэш-коды. In other words, value types whose fields have equal values have equal hash codes. Дополнительные сведения о переопределении GetHashCodeсм. в разделе «Примечания к наследникам». For more information about overriding GetHashCode, see the «Notes to Inheritors» section.

При переопределении метода GetHashCode следует также переопределить Equalsи наоборот. If you override the GetHashCode method, you should also override Equals, and vice versa. Если переопределенный метод Equals возвращает true при проверке на равенство двух объектов, переопределенный метод GetHashCode должен возвращать одно и то же значение для двух объектов. If your overridden Equals method returns true when two objects are tested for equality, your overridden GetHashCode method must return the same value for the two objects.

Если объект, используемый в качестве ключа в хэш-таблице, не предоставляет полезной реализации GetHashCode, можно указать поставщик хэш-кода, предоставив реализацию IEqualityComparer одной из перегрузок конструктора Hashtable класса. If an object that is used as a key in a hash table does not provide a useful implementation of GetHashCode, you can specify a hash code provider by supplying an IEqualityComparer implementation to one of the overloads of the Hashtable class constructor.

Примечания для Среда выполнения Windows Windows Runtime Notes for the Среда выполнения Windows Windows Runtime

При вызове метода GetHashCode для класса в Среда выполнения Windows Windows Runtime он предоставляет поведение по умолчанию для классов, которые не переопределяют GetHashCode. When you call the GetHashCode method on a class in the Среда выполнения Windows Windows Runtime , it provides the default behavior for classes that don’t override GetHashCode. Это является частью поддержки, предоставляемой .NET Framework для Среда выполнения Windows Windows Runtime (см. раздел поддержка .NET Framework для приложений Магазина Windows и среда выполнения Windows). This is part of the support that the .NET Framework provides for the Среда выполнения Windows Windows Runtime (see .NET Framework Support for Windows Store Apps and Windows Runtime). Классы в Среда выполнения Windows Windows Runtime не наследуют Objectи в настоящее время не реализуют GetHashCode. Classes in the Среда выполнения Windows Windows Runtime don’t inherit Object, and currently don’t implement a GetHashCode. Однако они имеют методы ToString, Equals(Object)и GetHashCode, когда они используются в коде C# или Visual Basic, а .NET Framework предоставляет поведение по умолчанию для этих методов. However, they appear to have ToString, Equals(Object), and GetHashCode methods when you use them in your C# or Visual Basic code, and the .NET Framework provides the default behavior for these methods.

Среда выполнения Windows Windows Runtime классы, написанные на C# или Visual Basic, могут переопределять метод GetHashCode. classes that are written in C# or Visual Basic can override the GetHashCode method.

Примечания для тех, кто наследует этот метод

Хэш-функция используется для быстрого создания числа (хэш-кода), соответствующего значению объекта. A hash function is used to quickly generate a number (hash code) that corresponds to the value of an object. Хэш-функции обычно относятся к каждому типу, и для уникальности в качестве входных данных должно использоваться хотя бы одно из полей экземпляра. Hash functions are usually specific to each type and, for uniqueness, must use at least one of the instance fields as input. Хэш-коды не должны вычисляться с помощью значений статических полей. Hash codes should not be computed by using the values of static fields.

Для классов, производных от Object, метод GetHashCode может делегировать базовому классу GetHashCode() реализацию только в том случае, если производный класс определяет равенство на равенство ссылок. For classes derived from Object, the GetHashCode method can delegate to the base class GetHashCode() implementation only if the derived class defines equality to be reference equality. Реализация GetHashCode() по умолчанию для ссылочных типов возвращает хэш-код, эквивалентный тому, который возвращается методом GetHashCode(Object). The default implementation of GetHashCode() for reference types returns a hash code that is equivalent to the one returned by the GetHashCode(Object) method. Можно переопределить GetHashCode() для неизменяемых ссылочных типов. You can override GetHashCode() for immutable reference types. Как правило, для изменяемых ссылочных типов следует переопределить GetHashCode() только в том случае, если: In general, for mutable reference types, you should override GetHashCode() only if: — Хэш-код можно вычислить из полей, которые не являются изменяемыми. ни — You can compute the hash code from fields that are not mutable; or — Можно гарантировать, что хэш-код изменяемого объекта не изменится, пока объект содержится в коллекции, зависящей от его хэш-кода. — You can ensure that the hash code of a mutable object does not change while the object is contained in a collection that relies on its hash code.

В противном случае может показаться, что изменяемый объект будет потерян в хэш-таблице. Otherwise, you might think that the mutable object is lost in the hash table. Если вы решите переопределить GetHashCode() для изменяемого ссылочного типа, в документации должен быть ясно, что пользователи вашего типа не должны изменять значения объектов, пока объект хранится в хэш-таблице. If you do choose to override GetHashCode() for a mutable reference type, your documentation should make it clear that users of your type should not modify object values while the object is stored in a hash table.

Для типов значений GetHashCode() предоставляет реализацию хэш-кода по умолчанию, использующую отражение. For value types, GetHashCode() provides a default hash code implementation that uses reflection. Рекомендуется переопределять его для повышения производительности. You should consider overriding it for better performance.

Дополнительные сведения и примеры, которые вычисляют хэш-коды различными способами, см. в разделе «примеры». For more information and examples that compute hash codes in a variety of ways, see the Examples section.

GetHashCode — вычисление хэш

Мне интересно узнать, каким образом формируется хэш объекта в C#. Например, есть тестовый класс:

Далее где-нибудь в коде:

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

1 ответ 1

Для начала, поскольку ваш класс A не переопределяет GetHashCode() , эта функция наследуется от object .

Точный алгоритм вычисления GetHashCode() для object не специфицирован:

Реализация GetHashCode по умолчанию не гарантирует уникальные значения для различных объектов. Кроме того, .NET Framework не гарантирует, что реализация GetHashCode по умолчанию, в том числе значения, возвращаемые ей, не поменяются при смене версии фреймворка. Соответственно, значение функции GetHashCode по умолчанию не должно быть использована как уникальный идентификатор объекта с целью хеширования.

То, что вам два объекта кажутся идентичными, не гарантирует, что у них при реализации по умолчанию совпадут хеш-коды. С другой стороны, посудите сами: если у двух людей совпадает имя и фамилия, это ведь ещё не значит, что это один и тот же человек? Так и .NET framework, если у двух экземпляров класса A совпадают все поля, ещё не считает эти экземпляры одним и тем же объектом. Соответственно, по умолчанию используется что угодно — например, адрес при создании или время создания, документация не говорит о точном методе. Если вас не устраивает поведение по умолчанию, вы должны его перекрыть.

Если ваш класс не использует операцию Equals и не является ключом в хеш-таблицах, в принципе можно ничего и не делать, вас должно устраивать и поведение по умолчанию. Но если ваш класс служит ключом, вам необходимо переопределить как Equals , так и GetHashCode() , причём согласованным образом: если x.Equals(y) возвращает true , то и хеш-коды у x и y обязаны совпадать.

Отсюда следует, что вы должны переопределять функцию GetHashCode() вместе с функцией Equals . Например, так:

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

Примером объекта первого типа являются, например, числа: если вы пишете

— нет никакой разницы между первой и второй пятёркой, это одна и та же сущность. Подобные штуки называются в .NET типами-значениями и вводятся ключевым словом struct . Для них метод Equals по умолчанию сравнивает значения всех полей, и если они равны, заключает, что и структуры равны, одинаковы. Поэтому структуры можно копировать по значению, структуру можно безболезненно заменить на её копию. (Метод GetHashCode по умолчанию определён соответствующим образом: для равных структур он гарантированно возвращает одинаковый хеш.)

Примером другой сущности может служить, например, автомобиль, атрибутами которого являются марка, год выпуска, мощность двигателя и т. п. Два автомобиля с одинаковыми техническими параметрами — это всё же разные автомобили. Такие объекты в C# называются ссылочными типами и вводятся ключевым словом class . Для классов, соответственно, реализация Equals по умолчанию не имеет права предполагать, что одинаковые значения полей автоматически означают равенство, каждый экземпляр класса считается уникальным.

Подумайте, не нужна ли вам на самом деле вместо класса A структура?

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

Класс Object

В C# предусмотрен специальный класс object, который неявно считается базовым классом для всех остальных классов и типов, включая и типы значений. Иными словами, все остальные типы являются производными от object. Это, в частности, означает, что переменная ссылочного типа object может ссылаться на объект любого другого типа. Кроме того, переменная типа object может ссылаться на любой массив, поскольку в C# массивы реализуются как объекты. Формально имя object считается в C# еще одним обозначением класса System.Object, входящего в библиотеку классов для среды .NET Framework.

Практическое значение этого в том, что помимо методов и свойств, которые вы определяете, также появляется доступ к множеству общедоступных и защищенных методов-членов, которые определены в классе Object. Эти методы присутствуют во всех определяемых классах.

Методы System.Object

Ниже перечислены все методы данного класса:

ToString()

Метод ToString() возвращает символьную строку, содержащую описание того объекта, для которого он вызывается. Кроме того, метод ToString() автоматически вызывается при выводе содержимого объекта с помощью метода WriteLine(). Этот метод переопределяется во многих классах, что позволяет приспосабливать описание к конкретным типам объектов, создаваемых в этих классах.

Применяйте этот метод, когда нужно получить представление о содержимом объекта — возможно, в целях отладки. Он предлагает очень ограниченные средства форматирования данных. Например, даты в принципе могут быть отображены в огромном разнообразии форматов, но DateTime.ToString() не оставляет никакого выбора в этом отношении. Если нужно более сложное строковое представление, которое, например, принимает во внимание установленные предпочтения или местные стандарты, то понадобится реализовать интерфейс IFormattable.

GetHashCode()

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

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

Equals() и ReferenceEquals()

По умолчанию метод Equals (object) определяет, ссылается ли вызывающий объект на тот же самый объект, что и объект, указываемый в качестве аргумента этого метода, т.е. он определяет, являются ли обе ссылки одинаковыми. Метод Equals (object) возвращает логическое значение true, если сравниваемые объекты одинаковы, в противном случае — логическое значение false. Он может быть также переопределен в создаваемых классах. Это позволяет выяснить, что же означает равенство объектов для создаваемого класса. Например, метод Equals (object) можно определить таким образом, чтобы в нем сравнивалось содержимое двух объектов.

Как несложно догадаться, учитывая существование трех различных методов сравнения объектов, среда .NET использует довольно сложную схему определения эквивалентности объектов. Следует учитывать и использовать тонкие различия между этими тремя методами и операцией сравнения ==. Кроме того, также существуют ограничения, регламентирующие, как следует переопределять виртуальную версию Equals() с одним параметром, если вы решитесь на это — поскольку некоторые базовые классы из пространства имен System.Collections вызывают этот метод и ожидают от него определенного поведения.

Finalize()

Назначение этого метода в C# примерно соответствует деструкторам С++, и он вызывается при сборке мусора для очистки ресурсов, занятых ссылочным объектом. Реализация Finalize() из Object на самом деле ничего не делает и игнорируется сборщиком мусора. Обычно переопределять Finalize() необходимо, если объект владеет неуправляемыми ресурсами, которые нужно освободить при его уничтожении. Сборщик мусора не может сделать это напрямую, потому что он знает только об управляемых ресурсах, поэтому полагается на финализацию, определенную вами.

GetType()

Этот метод возвращает экземпляр класса, унаследованный от System.Type. Этот объект может предоставить большой объем информации о классе, членом которого является ваш объект, включая базовый тип, методы, свойства и т.п. System.Type также представляет собой стартовую точку технологии рефлексии .NET.

Clone()

Этот метод создает копию объекта и возвращает ссылку на эту копию (а в случае типа значения — ссылку на упаковку). Отметим, что при этом выполняется неглубокое копирование, т.е. копируются все типы значений в классе. Если же класс включает в себя члены ссылочных типов, то копируются только ссылки, а не объекты, на которые они указывают. Этот метод является защищенным, а потому не может вызываться для копирования внешних объектов. К тому же он не виртуальный, а потому переопределять его реализацию нельзя.

Давайте рассмотрим применение некоторых из этих методов на конкретном примере:

Откуда растут руки у GetHashCode в .NET

Введение

Данная статья посвящена теме генерации хеш-кодов на платформе .NET. Тема является достаточно интересной, и думаю любой уважающий себя .NET разработчик должен ее знать. Поэтому поехали!

Что хранится в объектах помимо их полей?

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

У каждого объекта ссылочного типа есть так называемый заголовок (Header), который состоит из двух полей: указатель на тип которым является данный объект (MethodTablePointer), а так же индекс синхронизации (SyncBlockIndex).

Для чего они нужны?

Первое поле необходимо для того, чтобы каждый управляемый объект мог предоставить информацию о своем типе во время выполнения, то есть нельзя выдать один тип за другой, это сделано для безопасности типов. Так же этот указатель используется для реализации динамической диспетчеризации методов, фактически через него вызываются методы данного объекта. Метод Object.GetType фактически возвращает именно указатель MethodTablePointer.

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

Когда загружается CLR, она создает так называемый пул блоков синхронизации, можно сказать обычный массив этих блоков синхронизации. Когда объекту необходимо работать в многопоточном окружении (это делается с помощью метода Monitor.Enter или конструкции языка C# lock), CLR отыскивает свободный блок синхронизации в своем списке и записывает его индекс в то самое поле в заголовке объекта. Как только объект перестает нуждаться в многопоточном окружение, CLR просто присваивает значение -1 этому полю и тем самым освобождает блок синхронизации.

Блоки синхронизации — это фактически новое воплощение критических секций из С++. Создатели CLR посчитали, что ассоциировать с каждым управляемым объектом структуру критической секции будет слишком накладно, учитывая, что большинство объектов вообще не используют многопоточное окружение.

Для большего понимания ситуации рассмотрим следующую картинку:

По картинке видно, что ObjectA и ObjectB имеют один тип, поскольку их MethodTablePointer-ы указывают на один и тот же тип. ObjectC же имеет другой тип. Так же видно, что ObjectA и ObjectC задействуют пул блоков синхронизации, то есть фактически используют многопоточное окружение. ObjectB не использует пул поскольку его SyncBlockIndex = -1.

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

Как работает GetHashCode у ссылочных типов
То, что метод GetHashCode возвращает адрес объекта в управляемой куче — это миф. Этого быть не может, в виду его не постоянства, сборщик мусора, уплотняя кучу, смещает объекты и соответственно меняет им всем адреса.


Я не зря начал статью с объяснения того, что такое SyncBlock, поскольку в первых версиях фреймворка в качестве хеш-кода ссылочного типа использовался именно свободный индекс некоторого SyncBlock-а. Таким образом, в .NET 1.0 и .NET 1.1 вызов метода GetHashCode приводил к созданию SyncBlock и занесением его индекса в заголовок объекта в поле SyncBlockIndex. Как вы понимаете это не очень хорошая реализация для хеш-функции, поскольку во-первых создаются не нужные внутренние структуры, которые занимают память + тратиться время на их создание, во-вторых хеш-коды будут идти подряд, то есть будут предсказуемыми. Вот ссылка на блог, в котором один из разработчиков CLR говорит, что такая реализация плохая, и что они ее поменяют в следующей версии.

Начиная с .NET 2.0 алгоритм хеширования изменился. Теперь он использует manage идентификатор потока, в котором выполняется метод. Если верить реализации в SSCLI20, то метод выглядит так:

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

Как и раньше хеш-код вычисляется один раз и сохраняется в заголовке объекта в поле SyncBlockIndex (это оптимизация CLR). Теперь возникает вопрос, что если после вызова метода GetHashCode нам понадобиться использовать индекс синхронизации? Куда его записывать? И что делать с хеш-кодом?

Для ответа на эти вопросы рассмотрим структуру SyncBlock.

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

Как работает GetHashCode у значимых типов

Теперь поговорим о том, как работает метод GetHashCode у значимых типов. Скажу заранее, он работает достаточно интересно.

Первое, что надо сказать так это то, что создатели CLR рекомендуют всегда переопределять данный метод у пользовательских типов, поскольку он может работать не очень быстро, да и поведение его по умолчанию, возможно, не всегда Вас удовлетворит.

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

Первая версия:
Если структура не имеет ссылочных полей, а так же между ее полями нет свободного места, то используется быстрая версия метода GetHashCode. CLR просто xor — ит каждый 4 байта структуры и получает ответ. Это хороший хеш, так как задействовано всё содержимое структуры. Например, структура, у которой есть поле типа bool и int будет иметь свободное пространство в 3 байта, поскольку JIT когда размещает поля выравнивает их по 4 байта, а, следовательно, будет использована вторая версия для получения хеш-кода.

Кстати, в реализации данной версии был баг, который исправлен только в .NET 4. Он заключается в том, что хеш-код для типа decimal вычислялся не правильно.

С точки зрения чисел d1 и d2 равны, но их битовые представления отличаются (из-за особенностей представления decimal). А поскольку CLR xor — ит каждый 4 байта (которых всего 4 так как decimal занимает 16 байт), то получаются разные хеш-коды. Кстати, данный баг проявлялся не только у decimal, но и у любой структуры, которая содержит данный тип, а так же использует быструю версию для вычисления хеш-кода.

Вторая версия:
Если структура содержит ссылочные поля или между ее полями имеется свободное пространство, то используется медленная версия метода. CLR выбирает первое поле структуры, на основание которого и создает хеш-код. Это поле по возможности должно быть неизменяемым, например, иметь тип string, иначе при его изменении хеш-код будет так же меняться, и мы не сможем уже найти нашу структуру в хеш-таблице, если она использовалась в качестве ключа. Получается, если первое поле структуры будет изменяемым, то это ломает стандартную логику метода GetHashCode. Это еще одна причина по которой структуры должны быть не изменяемыми. CLR xor-ит хеш-код данного поля с указателем на тип данного поля (MethodTablePointer). CLR не рассматривает статические поля, так как статичным полем может быть поле с данным же типов, в результате чего мы впадем в бесконечную рекурсию.

На заметку

Структуры не могут содержать экземплярные поля своего же типа. То есть следующий код не будет компилироваться:

Связано это с тем, что структура не может принимать значения null. Следующий код подтверждение тому, что это невозможно:

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

На заметку

Чтобы понять ситуацию лучше рассмотрим следующий код:

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

k1 — 411217769, k2 — 411217771

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

v1 — 411217780, v2 — 411217780

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

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

Как работает GetHashCode у строкового типа

Класс String переопределяет метод GetHashCode. Его реализация в.NET 4.5 выглядит так:

Это код для 64 разрядной машины, но если взглянем на общий код с директивами

то заметим, что имеются отличия в зависимости от того какая машина 32 или 64 разрядная.

Следует сказать, что реализация данного метода меняется с каждым выходом .NET. Об этом писал Эрик Липперт. Он предупреждал, чтобы наш код ни в коем случае не сохранял хеши, которые сгенерированы стандартным путем в базе данных или на диске, поскольку они, скорее всего, поменяют реализацию в следующем выпуски .NET. Так оно и происходило на протяжения последних 4 выпусков .NET.

Реализация хеширования у строкового типа не подразумевает кэширования результата. То есть каждый раз при вызове метода GetHashCode мы будем заново вычислять хеш-код для строки. По словам Эрика Липперта, это сделано чтобы сэкономить память, лишние 4 байта для каждого объекта строкового типа того не стоят. Учитывая, что реализация очень быстрая, думаю это правильное решение.

Если вы заметили, в реализации метода GetHashCode появился код, которого раньше не было:

Оказывается в .NET 4.5 появилась возможность вычислять хеш-код для строк для каждого домена. Таким образом, установив значение атрибута в 1 можно добиться, чтобы хеш-код вычислялся на основе домена, в котором вызывается метод. Таким образом, одинаковые строки в разных доменах будут иметь разные хеш-коды. Метод, который генерирует этот хеш-код, является секретным и его реализация не раскрывается.

Как работает GetHashCode у делегатов

Прежде чем переходить к рассмотрению реализации метода GetHashCode у делегатов поговорим о том, как они реализованы.

Каждый делегат наследуется от класса MulticastDelegate, который в свою очередь наследуется от класса Delegate. Эта иерархия сложилась исторически, поскольку можно было бы обойтись одним классом MulticastDelegate.

Реализация метода GetHashCode в классе Delegate выглядит так

то есть фактически возвращается хеш-код типа делегата. Получается, делегаты одного типа содержащие разные методы для вызова всегда возвращают один и тот же хеш-код.

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

Реализация метода в классе MulticastDelegate выглядит так

Как известно, делегат хранит свои методы в списке _invocationList только в том случае если их более одного.

Если делегат содержит только один метод, то в коде выше objArray = null и соответственно хеш-код делегата будет равен хеш-коду типа делегата.

Для прояснения ситуации рассмотрим следующий код

хеш-коды данных делегатов равны хеш-коду типа Func , то есть равны между собой.

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

И последний случай

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

Как работает GetHashCode у анонимных типов

Как известно, анонимные типы — это новая фича в языке C# 3.0. Причем, это именно фича языка, так называемый синтаксический сахар поскольку CLR о них ничего не знает.

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

Для такого анонимного типа будет сгенерирован следующий код:

На заметку

Учитывая, что метод GetHashCode переопределен метод Equals, так же должен быть переопределен соответствующим образом.

На консоль будет выведено следующее:

method Equals return true
operator == return false

Все дело в том, что анонимные типы переопределяют метод Equals таким образом, что он проверяет все поля как это сделано у ValueType (только без рефлексии), но не переопределяет оператор равенства. Таким образом, метод Equals сравнивает по значению, в то время как оператор равенства сравнивает по ссылкам.

Для чего надо было переопределять методы Equals и GetHashCode?
Учитывая, что анонимные типы были созданы для упрощения работы с LINQ, ответ становится понятным. Анонимные типы удобно использовать в качестве хеш-ключей в операциях группировки (group) и соединения (join) в LINQ.

На заметку
Заключение

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

Спасибо за прочтение! Надеюсь, статья оказалось полезной.

Благодарность пользователю DreamWalker за любезное предоставление обновленных картинок к статье.

Оцените статью
Fobosworld.ru
Добавить комментарий

Adblock
detector