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

Я пытаюсь понять роль метода 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?

Спасибо.

Лусиан

Ответы

Ответ 1

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

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

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

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

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

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

Когда IEqualityComparer передается в конструктор словаря, вместо методов объектов Key используются методы IEqualityComparer.Equals и 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 - хотя они явно не являются одним и тем же объектом. Причина, по которой они являются одним и тем же хэш-кодом в этом случае, заключается в том, что вы используете оператор ^ (побитовый исключающий-ИЛИ), поэтому 100 ^ 100 отменяет нулевое значение, равно 1000 1000. Когда два разных объекта имеют один и тот же ключ, мы называем это столкновением.

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

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

TL;DR

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

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

Ответ 2

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

Ответ 3

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

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