хеш-коды объектов
Разработчики FCL решили, что было бы чрезвычайно полезно иметь возмож-
ность добавления в хеш-таблицы любых экземпляров любых типов. С этой целью
в
System.Object
включен виртуальный метод
GetHashCode
, позволяющий вычис-
лить для любого объекта целочисленный (
Int32
) хеш-код.
Если вы определяете тип и переопределяете метод
Equals
, вы должны пере-
определить и метод
GetHashCode
. Если при определении типа переопределить
только один из этих методов, компилятор C# выдаст предупреждение. Например,
при компиляции представленного далее кода появится предупреждение:
warning
CS0659
:
'Program'
overrides
Object.Equals(Object
o)
but
does
not
override
Object.GetHashCode()
(
'Program'
переопределяет
Object.Equals(Object
o)
, но
не переопределяет
Object.GetHashCode()
).
public sealed class Program {
public override Boolean Equals(Object obj) { ... }
}
176
Глава.5 .Примитивные,.ссылочные.и.значимые.типы
Причина, по которой в типе должны быть определены оба метода —
Equals
и
GetHashCode
, — состоит в том, что реализация типов
System.Collections.
Hashtable
,
System.Collections.Generic.Dictionary
и любых других коллекций
требует, чтобы два равных объекта имели одинаковые значения хеш-кодов. По-
этому, переопределяя
Equals
, нужно переопределить
GetHashCode
и обеспечить
соответствие алгоритма, применяемого для вычисления равенства, алгоритму,
используемому для вычисления хеш-кода объекта.
По сути, когда вы добавляете пару «ключ-значение» в коллекцию, первым
вычисляется хеш-код ключа. Он указывает, в каком «сегменте» будет храниться
пара «ключ-значение». Когда коллекции требуется найти некий ключ, она вы-
числяет для него хеш-код. Хеш-код определяет «сегмент» поиска имеющегося
в таблице ключа, равного заданному. Применение этого алгоритма хранения и
поиска ключей означает, что если вы измените хранящийся в коллекции ключ
объекта, коллекция больше не сможет найти этот объект. Если вы намерены
изменить ключ объекта в хеш-таблице, то сначала удалите имеющуюся пару
«ключ-значение», модифицируйте ключ, а затем добавьте в хеш-таблицу новую
пару «ключ-значение».
В определении метода
GetHashCode
нет особых хитростей. Однако для некоторых
типов данных и их распределения в памяти бывает непросто подобрать алгоритм
хеширования, который выдавал бы хорошо распределенный диапазон значений.
Вот простой алгоритм, неплохо подходящий для объектов
Point
:
internal sealed class Point {
private readonly Int32 m_x, m_y;
public override Int32 GetHashCode() {
return m_x ^ m_y; // Исключающее ИЛИ для m_x и m_y
}
...
}
Выбирая алгоритм вычисления хеш-кодов для экземпляров своего типа, ста-
райтесь следовать определенным правилам:
Используйте алгоритм, который дает случайное распределение, повышающее
производительность хеш-таблицы.
Алгоритм может вызывать метод
GetHashCode
базового типа и использовать
возвращаемое им значение, однако в общем случае лучше отказаться от вызова
встроенного метода
GetHashCode
для типа
Object
или
ValueType
, так как эти реа-
лизации обладают низкой производительностью алгоритмов хеширования.
В алгоритме должно использоваться как минимум одно экземплярное поле.
Поля, используемые в алгоритме, в идеале не должны изменяться, то есть они
должны инициализироваться при создании объекта и сохранять значение в те-
чение всей его жизни.
Алгоритм должен быть максимально быстрым.
177
Примитивный.тип.данных.dynamic
Объекты с одинаковым значением должны возвращать одинаковые коды. На-
пример, два объекта
String
, содержащие одинаковый текст, должны возвращать
одно значение хеш-кода.
Реализация
GetHashCode
в
System.Object
ничего «не знает» о производных типах
и их полях. Поэтому этот метод возвращает число, однозначно идентифицирующее
объект в пределах домена приложений; при этом гарантируется, что это число не
изменится на протяжении всей жизни объекта.
Do'stlaringiz bilan baham: |