Qual é o papel do GetHashCode no IEqualityComparer <T> no .NET?

142

Estou tentando entender o papel do método GetHashCode da interface IEqualityComparer.

O exemplo a seguir é retirado do 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();
    }
}

A implementação do método Equals não deveria ser suficiente para comparar dois objetos Box? É aí que dizemos à estrutura a regra usada para comparar os objetos. Por que o GetHashCode é necessário?

Obrigado.

Lucian

Lucian
fonte
Leia: en.wikipedia.org/wiki/Hash_table e veja se você entende melhor o objetivo do GetHashCode.
gastador
1
Veja esta ótima resposta: stackoverflow.com/a/3719802/136967
Mikhail

Respostas:

201

Um pouco de fundo primeiro ...

Todo objeto no .NET possui um método Equals e um método GetHashCode.

O método Equals é usado para comparar um objeto com outro objeto - para ver se os dois objetos são equivalentes.

O método GetHashCode gera uma representação inteira de 32 bits do objeto. Como não há limite para a quantidade de informações que um objeto pode conter, certos códigos de hash são compartilhados por vários objetos - portanto, o código de hash não é necessariamente único.

Um dicionário é uma estrutura de dados muito interessante que negocia uma maior área de cobertura de memória em troca de custos (mais ou menos) constantes para operações de Adicionar / Remover / Obter. É uma má escolha para iterar sobre embora. Internamente, um dicionário contém uma matriz de buckets, onde os valores podem ser armazenados. Quando você adiciona uma chave e um valor a um dicionário, o método GetHashCode é chamado na chave. O código hash retornado é usado para determinar o índice do bucket no qual o par Chave / Valor deve ser armazenado.

Quando você deseja acessar o Valor, passa a Chave novamente. O método GetHashCode é chamado na chave e o depósito que contém o valor está localizado.

Quando um IEqualityComparer é passado para o construtor de um dicionário, os métodos IEqualityComparer.Equals e IEqualityComparer.GetHashCode são usados ​​em vez dos métodos nos objetos Key.

Agora, para explicar por que os dois métodos são necessários, considere este exemplo:

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"); 

Usando o método BoxEqualityComparer.GetHashCode no seu exemplo, ambas as caixas têm o mesmo código de hash - 100 ^ 100 ^ 25 = 1000 ^ 1000 ^ 25 = 25 - mesmo que claramente não sejam o mesmo objeto. O motivo pelo qual eles são o mesmo código hash nesse caso é porque você está usando o operador ^ (OR bit a bit exclusivo) para que 100 ^ 100 cancele deixando zero, assim como 1000 ^ 1000. Quando dois objetos diferentes têm a mesma chave, chamamos isso de colisão.

Quando adicionamos dois pares de chave / valor com o mesmo código de hash a um dicionário, eles são armazenados no mesmo bloco. Portanto, quando queremos recuperar um Valor, o método GetHashCode é chamado em nossa Chave para localizar o depósito. Como há mais de um valor no intervalo, o dicionário itera sobre todos os pares Chave / Valor no intervalo, chamando o método Equals nas Chaves para encontrar o correto.

No exemplo que você postou, as duas caixas são equivalentes; portanto, o método Equals retorna true. Nesse caso, o dicionário possui duas chaves idênticas, portanto, lança uma exceção.

TLDR

Portanto, em resumo, o método GetHashCode é usado para gerar um endereço em que o objeto está armazenado. Portanto, um dicionário não precisa procurá-lo. Ele apenas calcula o código hash e pula para esse local. O método Equals é um teste melhor de igualdade, mas não pode ser usado para mapear um objeto em um espaço de endereço.

sheikhjabootie
fonte
4
Para aqueles que querem saber o que é o operador ^, este é o operador OR exclusivo bit a bit, consulte msdn.microsoft.com/en-us/library/zkacc7k1.aspx .
R. Schreurs
2
Apenas para apontar isso explicitamente: ( msdn.microsoft.com/en-us/library/ms132155.aspx ) Observações aos implementadores As implementações são necessárias para garantir que, se o método Equals retornar true para dois objetos x e y, o valor retornado pelo método GetHashCode para x deve ser igual ao valor retornado para y.
Diego Frehner
2
@DiegoFrehner - Você está certo. Outra coisa que pode enganar as pessoas é que o valor do método GetHashCode não deve variar se o objeto for modificado. Portanto, os campos dentro do objeto que GetHashCode depende devem ser somente leitura (imutáveis). Há uma explicação aqui: stackoverflow.com/a/4868940/469701
sheikhjabootie
1
@ Centric: O código hash de um objeto não deve mudar, a menos que seja alterado de uma maneira que afete a igualdade. Se uma classe puder ser modificada de maneira a afetar a igualdade, o código deve evitar armazenar em um dicionário qualquer instância que possa ser exposta a um código que a modifique enquanto estiver no dicionário. Se o código que armazena o objeto obedecer a essa regra, ter um código de hash que reflita o estado mutável pode ser útil. Pena que o .NET não distinga melhor a igualdade e a equivalência de estados, pois ambos são conceitos úteis.
Supercat 02/02
3
@ Centric: Mesmo além do uso de código hash para o endereçamento de tabelas, a idéia fundamental por trás de um código hash é que o conhecimento de que dois objetos têm códigos hash diferentes implica que eles são desiguais e não precisam compará-los. Como corolário, o conhecimento de que os códigos de hash de muitos objetos não correspondem ao código de hash de um determinado objeto implica que nenhum deles é igual ao objeto. Usar um código hash para endereçar é basicamente uma maneira de ignorar objetos que possuem códigos hash diferentes.
22614
9

GetHashCode é usado em coletas de dicionário e cria hash para armazenar objetos nele. Aqui está um bom artigo sobre por que e como usar IEqualtyComparer e GetHashCode http://dotnetperls.com/iequalitycomparer

Cinza
fonte
4
Mais: Se você precisar comparar Equals, seria suficiente, mas quando você precisar obter o elemento do Dictionary, será mais fácil fazer isso por hash, não usando Equals .
Ash
5

Enquanto isso seria possível para um Dictionary<TKey,TValue>para ter seus GetValuee semelhantes métodos chamar Equalsem cada chave armazenada para ver se ele corresponde a um ser procurado, isso seria muito lento. Em vez disso, como muitas coleções baseadas em hash, ele depende GetHashCodepara excluir rapidamente a maioria dos valores não correspondentes da consideração. Se a solicitação GetHashCodede um item procurado render 42, e uma coleção tiver 53.917 itens, mas a solicitação de 53.914 itens tiver GetHashCodeum valor diferente de 42, apenas 3 itens terão que ser comparados aos itens procurados. Os outros 53.914 podem ser ignorados com segurança.

O motivo para a GetHashCodeinclusão de a em a IEqualityComparer<T>é permitir a possibilidade de o consumidor de um dicionário querer considerar objetos iguais que normalmente não se considerariam iguais. O exemplo mais comum seria um chamador que deseja usar cadeias de caracteres como chaves, mas usa comparações que não diferenciam maiúsculas de minúsculas. Para que isso funcione com eficiência, o dicionário precisará ter alguma forma de função de hash que produza o mesmo valor para "Fox" e "FOX", mas esperamos que produza outra coisa para "box" ou "zebra". Como o GetHashCodemétodo incorporado Stringnão funciona dessa maneira, o dicionário precisará obter esse método de outro lugar,IEqualityComparer<T>Equals método que considera "Fox" e "FOX" idênticos entre si, mas não para "box" ou "zebra".

supercat
fonte
A resposta correta e direta à pergunta! GetHashCode () precisa complementar Equals () para os objetos em questão.
Sumith 10/10/19
@ Sumith: Muitas discussões sobre hash falam sobre buckets, mas acho que é mais útil pensar em exclusão. Se as comparações forem caras, o hash pode oferecer benefícios mesmo ao usar coleções que não são organizadas em buckets.
supercat