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

142

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

Спасибо.

Люциан

Люциан
источник
Прочтите: en.wikipedia.org/wiki/Hash_table и посмотрите, лучше ли вы понимаете цель GetHashCode.
Спендер
1
См. Этот отличный ответ: stackoverflow.com/a/3719802/136967
Михаил

Ответы:

204

Сначала немного предыстории ...

Каждый объект в .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 - лучший тест на равенство, но его нельзя использовать для отображения объекта в адресное пространство.

шейхджабути
источник
4
Для тех, кому интересно, что такое ^ -оператор, это побитовый оператор исключающего ИЛИ, см. Msdn.microsoft.com/en-us/library/zkacc7k1.aspx .
R. Schreurs
2
Просто чтобы указать на это явно: ( msdn.microsoft.com/en-us/library/ms132155.aspx ) Примечания для разработчиков. Реализации необходимы, чтобы гарантировать, что если метод Equals возвращает true для двух объектов x и y, то возвращаемое значение методом GetHashCode для x должно быть равно значение, возвращаемое для y.
Diego Frehner 02
2
@DiegoFrehner - Вы совершенно правы. Еще одна вещь, которая может сбить с толку, - это то, что значение метода GetHashCode не должно изменяться при изменении объекта. Таким образом, поля внутри объекта, от которых зависит GetHashCode, должны быть доступны только для чтения (неизменяемыми). Здесь есть объяснение: stackoverflow.com/a/4868940/469701
sheikhjabootie 07
1
@Acentric: хэш-код объекта не должен изменяться, если он не видоизменен способом, влияющим на равенство. Если класс может быть изменен таким образом, чтобы повлиять на равенство, код должен избегать хранения в словаре любого экземпляра, который может подвергнуться воздействию кода, который может изменить его, пока он находится в словаре. Если код, в котором хранится объект, соответствует этому правилу, может оказаться полезным наличие хэш-кода, отражающего изменяемое состояние. Жаль, что .NET не лучше различает равенство состояний и эквивалентность, поскольку оба понятия полезны.
supercat 02
3
@Acentric: даже помимо использования хэш-кода для адресации хэш-таблицы, фундаментальная идея хэш-кода заключается в том, что знание того, что два объекта имеют разные хеш-коды, подразумевает, что они не равны и не должны сравнивать их. Как следствие, знание того, что хэш-коды многих объектов не соответствуют хэш-коду данного объекта, подразумевает, что ни один из них не равен объекту. Использование хэш-кода для адресации - это, по сути, способ игнорирования объектов с разными хэш-кодами.
supercat
9

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

Ясень
источник
4
Подробнее: Если вам нужно сравнить Equals , будет достаточно, но когда вам нужно получить элемент из Dictionary, это проще сделать с помощью хеша, а не с помощью Equals .
Эш
5

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

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

суперкар
источник
Правильный и точный ответ на вопрос! GetHashCode () должен дополнять Equals () для рассматриваемых объектов.
Sumith
@Sumith: Многие обсуждения хеширования говорят о ведрах, но я думаю, что более полезно подумать об исключении. Если сравнение обходится дорого, хеширование может дать преимущества даже при использовании коллекций, которые не организованы в сегменты.
supercat