Какова роль GetHashCode в IEqualityComparer <T>в .NET? - PullRequest
Новая
       62

Какова роль GetHashCode в IEqualityComparer <T>в .NET?

130 голосов
/ 04 ноября 2010

Я пытаюсь понять роль метода GetHashCode интерфейса IEqualityComparer.

Следующий пример взят из MSDN.хватит сравнивать два объекта Box?Именно здесь мы сообщаем каркасу правило, используемое для сравнения объектов.Зачем нужен GetHashCode?

Спасибо.

Люциан

Ответы [ 3 ]

193 голосов
/ 04 ноября 2010

Сначала немного фона ...

Каждый объект в .NET имеет метод Equals и метод GetHashCode.

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

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

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

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

Когда IEqualityComparer передается в конструктор словаря, методы IEqualityComparer.Equals и IEqualityComparer.GetHashCode используются вместо методов объектов Key.

Теперь, чтобы объяснить, почему оба метода необходимы, рассмотрим следующий пример: 

BoxEqualityComparer boxEqC = new BoxEqualityComparer(); 

Dictionary<Box, String> boxes = new Dictionary<Box, string>(boxEqC); 

Box redBox = new Box(100, 100, 25);
Box blueBox = new Box(1000, 1000, 25);

boxes.Add(redBox, "red"); 
boxes.Add(blueBox, "blue");

Используя метод BoxEqualityComparer.GetHashCode в вашем примере, оба этих блока имеют одинаковый хэш-код - 100 ^ 100 ^ 25 = 1000 ^ 1000 ^ 25 = 25 - даже если они явно не являются одним и тем же объектом. Причина того, что они имеют одинаковый хэш-код в этом случае, заключается в том, что вы используете оператор ^ (побитовое исключающее-ИЛИ), поэтому 100 ^ 100 отменяет оставляя ноль, как и 1000 ^ 1000. Когда два разных объекта имеют одинаковый ключ, мы называем это столкновением.

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

В приведенном вами примере два поля эквивалентны, поэтому метод Equals возвращает значение true. В этом случае в словаре есть два идентичных ключа, поэтому он выдает исключение.

TLDR

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

Надеюсь, это поможет

7 голосов
/ 04 ноября 2010

GetHashCode используется в словарных подборках и создает хэш для хранения в нем объектов. Вот хорошая статья, почему и как использовать IEqualtyComparer и GetHashCode http://dotnetperls.com/iequalitycomparer

3 голосов
/ 18 марта 2015

Хотя для Dictionary<TKey,TValue> было бы возможно, чтобы его GetValue и подобные методы вызывали Equals для каждого сохраненного ключа, чтобы увидеть, соответствует ли он искомому, это будет очень медленно. Вместо этого, как и во многих коллекциях на основе хеша, он полагается на GetHashCode, чтобы быстро исключить из рассмотрения большинство несоответствующих значений. Если при вызове GetHashCode для искомого предмета получено 42, а в коллекции 53 917 предметов, но при вызове GetHashCode для 53 914 предметов получено значение, отличное от 42, то сравнивать нужно только 3 предмета с искал. Остальные 53 914 можно смело игнорировать.

Причина, по которой GetHashCode включен в IEqualityComparer<T>, заключается в том, что покупатель словаря может захотеть рассматривать как равные объекты, которые обычно , а не рассматривают друг друга как равные. Наиболее распространенным примером может быть вызывающий, который хочет использовать строки в качестве ключей, но использует сравнения без учета регистра. Чтобы сделать это эффективно, словарь должен иметь некоторую форму хэш-функции, которая будет давать одинаковое значение для «Fox» и «FOX», но, надеюсь, что-то еще для «box» или «zebra». Поскольку метод GetHashCode, встроенный в String, не работает таким образом, словарь должен будет получить такой метод откуда-то еще, и IEqualityComparer<T> является наиболее логичным местом, поскольку необходимость в таком хэш-коде будет очень сильно ассоциируется с Equals методом, который считает «Fox» и «FOX» идентичными друг другу, но не «коробке» или «зебре».

...