Какова роль метода GetHashCode в in.NET компаратор IEqualityComparer?
Я пытаюсь понять роль метода 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?
спасибо.
Lucian
3 ответов:
немного фона в первую очередь...
каждый объект в .NET имеет метод Equals и метод GetHashCode.
метод Equals используется для сравнения одного объекта с другим объектом - чтобы увидеть, эквивалентны ли эти два объекта.
метод GetHashCode генерирует 32-разрядное целочисленное представление объекта. Поскольку нет ограничений на то, сколько информации может содержать объект, некоторые хэш-коды совместно используются несколькими объектами - поэтому хэш-код не является обязательно уникальный.
словарь-это действительно классная структура данных, которая торгует более высоким объемом памяти в обмен на (более или менее) постоянные затраты на операции добавления/удаления/получения. Это плохой выбор для перебора. Внутри словарь содержит массив сегментов, в которых могут храниться значения. При добавлении ключа и значения в словарь, метод GetHashCode вызывается на ключ. Возвращенный хэш-код используется для определения индекса ведра, в котором Пара ключ / значение должна быть сохранена.
когда вы хотите получить доступ к значению, вы передаете ключ снова. Метод GetHashCode вызывается на ключ, и ведро, содержащее значение находится.
когда IEqualityComparer передается в конструктор словаря, IEqualityComparer.Равно и IEqualityComparer.Методы GetHashCode используются вместо методов на ключевых объектах.
теперь, чтобы объяснить, почему оба метода необходимы, рассмотрим это пример:
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 - хотя они явно не являются одним и тем же объектом. Причина, по которой они являются одним и тем же хэш-кодом в этом случае, заключается в том, что вы используете оператор ^ (побитовый exclusive-OR), поэтому 100^100 отменяет выход из нуля, как и 1000^1000. Когда два разных объекта имеют один и тот же ключ, мы называем это столкновением.
когда мы добавляем две пары ключ / значение с одним и тем же хэш-кодом в словарь, они оба хранятся в одном ведре. Поэтому, когда мы хотим получить значение, метод GetHashCode вызывается на нашем ключе, чтобы найти ведро. Поскольку в ведре есть более одного значения, словарь перебирает все пары ключ/значение в ведре, вызывая метод Equals на ключах, чтобы найти правильный.
в Примере, который вы опубликовали, эти два поля эквивалентны, поэтому метод Equals возвращает значение true. В этом случае словарь имеет два одинаковых ключа, поэтому он выдает исключение.
TLDR
Надежда это помогает
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входит вIEqualityComparer<T>должен учитывать возможность того, что потребитель словаря может захотеть рассматривать как равные объекты, которые обычно не считайте друг друга равными. Наиболее распространенным примером может быть вызывающий объект, который хочет использовать строки в качестве ключей, но использовать сравнения без учета регистра. Для того, чтобы сделать эту работу эффективно, словарь должен будет иметь некоторую форму хэш-функции, которая даст то же значение для "Fox" и "FOX", но, надеюсь, даст что-то еще для "box" или "zebra". Так какGetHashCodeметод построен вStringне работает таким образом, словарь должен будет получить такой метод откуда-то еще, иIEqualityComparer<T>является наиболее логичным местом, так как потребность в таком хэш-коде будет очень сильно связана сEqualsметод, который считает" Fox "и" FOX " идентичными друг друга, но не до "коробки" или "зебры".
Comments