Я пытаюсь понять роль метода GetHashCode интерфейса IEqualityComparer.
Следующий пример взят из MSDN:
using System;
using System.Collections.Generic;
class Example {
static void Main() {
try {
BoxEqualityComparer boxEqC = new BoxEqualityComparer();
Dictionary<Box, String> boxes = new Dictionary<Box,
string>(boxEqC);
Box redBox = new Box(4, 3, 4);
Box blueBox = new Box(4, 3, 4);
boxes.Add(redBox, "red");
boxes.Add(blueBox, "blue");
Console.WriteLine(redBox.GetHashCode());
Console.WriteLine(blueBox.GetHashCode());
}
catch (ArgumentException argEx) {
Console.WriteLine(argEx.Message);
}
}
}
public class Box {
public Box(int h, int l, int w) {
this.Height = h;
this.Length = l;
this.Width = w;
}
public int Height { get; set; }
public int Length { get; set; }
public int Width { get; set; }
}
class BoxEqualityComparer : IEqualityComparer<Box> {
public bool Equals(Box b1, Box b2) {
if (b1.Height == b2.Height & b1.Length == b2.Length
& b1.Width == b2.Width) {
return true;
}
else {
return false;
}
}
public int GetHashCode(Box bx) {
int hCode = bx.Height ^ bx.Length ^ bx.Width;
return hCode.GetHashCode();
}
}
Разве реализации метода Equals не должно хватить для сравнения двух объектов Box? Здесь мы сообщаем фреймворку правило, используемое для сравнения объектов. Зачем нужен GetHashCode?
Спасибо.
Люциан
c#
.net
gethashcode
iequalitycomparer
Люциан
источник
источник
Ответы:
Сначала немного предыстории ...
Каждый объект в .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. В этом случае в словаре есть два одинаковых ключа, поэтому возникает исключение.
TL; DR
Таким образом, метод GetHashCode используется для генерации адреса, где хранится объект. Таким образом, словарь не должен его искать. Он просто вычисляет хэш-код и переходит в это место. Метод Equals - лучший тест на равенство, но его нельзя использовать для отображения объекта в адресное пространство.
источник
GetHashCode используется в сборниках словаря и создает хеш для хранения в нем объектов. Вот хорошая статья, почему и как использовать IEqualtyComparer и GetHashCode http://dotnetperls.com/iequalitycomparer
источник
Хотя было бы возможно,
Dictionary<TKey,TValue>
чтобы егоGetValue
и аналогичные методы вызывалиEquals
каждый сохраненный ключ, чтобы увидеть, соответствует ли он искомому, это будет очень медленно. Вместо этого, как и многие коллекции на основе хешей, он полагается наGetHashCode
быстрое исключение из рассмотрения большинства несовпадающих значений. Если вызовGetHashCode
искомого элемента дает 42, а в коллекции 53 917 элементов, но вызовGetHashCode
53 914 элементов дал значение, отличное от 42, тогда только 3 элемента нужно будет сравнить с искомыми. Остальные 53 914 можно спокойно игнорировать.Причина, по которой a
GetHashCode
включен в an,IEqualityComparer<T>
состоит в том, чтобы учесть возможность того, что потребитель словаря может захотеть рассматривать как равные объекты, которые обычно не считают друг друга равными. Самый распространенный пример - вызывающий объект, который хочет использовать строки в качестве ключей, но при этом использует сравнения без учета регистра. Чтобы это работало эффективно, словарь должен иметь некоторую форму хэш-функции, которая будет давать одно и то же значение для «Fox» и «FOX», но, надеюсь, даст что-то еще для «box» или «zebra». ПосколькуGetHashCode
встроенный методString
не работает таким образом, словарь должен будет получить такой метод откуда-то еще,IEqualityComparer<T>
Equals
метод, который считает «лисицу» и «лису» идентичными друг другу, но не «коробку» или «зебру».источник