Por que é importante substituir GetHashCode quando o método Equals é substituído?

1445

Dada a seguinte classe

public class Foo
{
    public int FooId { get; set; }
    public string FooName { get; set; }

    public override bool Equals(object obj)
    {
        Foo fooItem = obj as Foo;

        if (fooItem == null) 
        {
           return false;
        }

        return fooItem.FooId == this.FooId;
    }

    public override int GetHashCode()
    {
        // Which is preferred?

        return base.GetHashCode();

        //return this.FooId.GetHashCode();
    }
}

Eu substituí o Equalsmétodo porque Foorepresenta uma linha para a Footabela s. Qual é o método preferido para substituir o GetHashCode?

Por que é importante substituir GetHashCode?

David Basarab
fonte
36
É importante implementar iguais e gethashcode, devido a colisões, em particular ao usar dicionários. se dois objetos retornarem o mesmo código hash, eles serão inseridos no dicionário com encadeamento. Ao acessar o item, o método igual é usado.
DarthVader

Respostas:

1320

Sim, é importante se o seu item for usado como chave em um dicionário ou HashSet<T>etc - pois é usado (na ausência de um costume IEqualityComparer<T>) para agrupar itens em baldes. Se o código hash para dois itens não corresponder, eles nunca poderão ser considerados iguais ( iguais simplesmente nunca serão chamados).

O método GetHashCode () deve refletir a Equalslógica; as regras são:

  • se duas coisas são iguais ( Equals(...) == true), elas devem retornar o mesmo valor paraGetHashCode()
  • se o GetHashCode()for igual, é não necessário para que eles sejam o mesmo; isso é uma colisão e Equalsserá chamado para ver se é uma igualdade real ou não.

Nesse caso, parece que " return FooId;" é uma GetHashCode()implementação adequada . Se você estiver testando várias propriedades, é comum combiná-las usando o código abaixo, para reduzir colisões diagonais (ou seja, para que ele new Foo(3,5)tenha um código hash diferente new Foo(5,3)):

unchecked // only needed if you're compiling with arithmetic checks enabled
{ // (the default compiler behaviour is *disabled*, so most folks won't need this)
    int hash = 13;
    hash = (hash * 7) + field1.GetHashCode();
    hash = (hash * 7) + field2.GetHashCode();
    ...
    return hash;
}

Ah - por conveniência, você também pode considerar fornecer ==e !=operadores ao substituir Equalse GetHashCode.


Uma demonstração do que acontece quando você comete um erro está aqui .

Marc Gravell
fonte
49
Posso perguntar por que você está se multiplicando com esses fatores?
Leandro López
22
Na verdade, eu provavelmente poderia perder um deles; o objetivo é tentar minimizar o número de colisões - para que um objeto {1,0,0} tenha um hash diferente de {0,1,0} e {0,0,1} (se você entende o que quero dizer ),
Marc Gravell
13
Ajustei os números para torná-lo mais claro (e adicionei uma semente). Alguns códigos usam números diferentes - por exemplo, o compilador C # (para tipos anônimos) usa uma semente de 0x51ed270b e um fator de -1521134295.
Marc Gravell
76
@Leandro López: Geralmente, os fatores são escolhidos para serem números primos, pois diminui o número de colisões.
Andrei Rînea 22/10/10
29
"Ah - por conveniência, você também pode considerar fornecer operadores == e! = Ao substituir Equals e GethashCode.": A Microsoft desencoraja o operador de implementação == para objetos que não são imutáveis ​​- msdn.microsoft.com/en-us/library/ ms173147.aspx - "Não é uma boa idéia substituir o operador == em tipos não imutáveis."
Antiduh
137

Na verdade, é muito difícil de implementar GetHashCode()corretamente porque, além das regras que Marc já mencionou, o código de hash não deve ser alterado durante a vida útil de um objeto. Portanto, os campos usados ​​para calcular o código de hash devem ser imutáveis.

Finalmente encontrei uma solução para esse problema quando estava trabalhando com o NHibernate. Minha abordagem é calcular o código de hash a partir do ID do objeto. O ID pode ser definido apenas pelo construtor, portanto, se você deseja alterar o ID, o que é muito improvável, é necessário criar um novo objeto que tenha um novo ID e, portanto, um novo código de hash. Essa abordagem funciona melhor com GUIDs porque você pode fornecer um construtor sem parâmetros que gera aleatoriamente um ID.

Albic
fonte
20
@vanja. Eu acredito que tem a ver com: se você adicionar o objeto a um dicionário e alterar a identificação do objeto, ao buscar mais tarde, você usará um hash diferente para recuperá-lo, para que nunca o obtenha no dicionário.
ANeves
74
A documentação da função GetHashCode () da Microsoft não indica nem implica que o hash do objeto deve permanecer consistente ao longo da vida útil. De fato, ele explica especificamente um caso permitido no qual ele não pode : "O método GetHashCode para um objeto deve retornar consistentemente o mesmo código de hash, desde que não haja modificação no estado do objeto que determine o valor de retorno do método Equals do objeto . "
PeterAllenWebb
37
"o código hash não deve mudar durante a vida útil de um objeto" - isso não é verdade.
apocalypse
7
Uma maneira melhor de dizer que é "o código hash (nem a avaliação de iguais) deve mudar durante o período em que o objeto é usado como uma chave para uma coleção". Portanto, se você adicionar o objeto a um dicionário como uma chave, deverá garantir que GetHashCode e Equals não alterarão sua saída para uma determinada entrada até você remover o objeto do dicionário.
22813 Scott Scott
11
@ScottChamberlain Acho que você não se esqueceu do seu comentário, deveria ser: "o código hash (nem a avaliação de iguais) NÃO deve mudar durante o período em que o objeto é usado como chave para uma coleção". Direita?
Stan Prokop
57

Ao substituir o Equals, você basicamente afirma que é quem sabe como comparar duas instâncias de um determinado tipo; portanto, é provável que você seja o melhor candidato a fornecer o melhor código de hash.

Este é um exemplo de como o ReSharper grava uma função GetHashCode () para você:

public override int GetHashCode()
{
    unchecked
    {
        var result = 0;
        result = (result * 397) ^ m_someVar1;
        result = (result * 397) ^ m_someVar2;
        result = (result * 397) ^ m_someVar3;
        result = (result * 397) ^ m_someVar4;
        return result;
    }
}

Como você pode ver, apenas tenta adivinhar um bom código de hash com base em todos os campos da classe, mas como você conhece o domínio ou os intervalos de valores do seu objeto, você ainda pode fornecer um melhor.

Armadilha
fonte
7
Isso sempre não retornará zero? Provavelmente deve inicializar o resultado para 1! Também precisa de mais alguns pontos e vírgulas.
Sam Mackrill
16
Você está ciente do que o operador XOR (^) faz?
Stephen Drew
1
Como eu disse, é isso que o R # escreve para você (pelo menos é o que ele fez em 2008) quando solicitado. Obviamente, esse trecho deve ser ajustado pelo programador de alguma maneira. Quanto aos pontos e vírgulas ausentes ... sim, parece que eu os deixei de fora quando copiei o código de uma seleção de região no Visual Studio. Eu também pensei que as pessoas descobririam as duas coisas.
Armadilha
3
@SamMackrill Adicionei o ponto e vírgula que faltava.
Matthew Murdoch
5
@SamMackrill Não, nem sempre ele retornará 0. 0 ^ a = a, então 0 ^ m_someVar1 = m_someVar1. Ele também pode definir o valor inicial de resultcomo m_someVar1.
Millie Smith
41

Não se esqueça de verificar o parâmetro obj nullao substituir Equals(). E também compare o tipo.

public override bool Equals(object obj)
{
    Foo fooItem = obj as Foo;

    if (fooItem == null)
    {
       return false;
    }

    return fooItem.FooId == this.FooId;
}

A razão para isso é: Equalsdeve retornar false em comparação com null. Consulte também http://msdn.microsoft.com/en-us/library/bsc2ak47.aspx

huha
fonte
6
Essa verificação de tipo falhará na situação em que uma subclasse se refere ao método Equals da superclasse como parte de sua própria comparação (ou seja, base.Equals (obj)) - deve ser usada como alternativa
sweetfa
@sweetfa: Depende de como o método Equals da subclasse é implementado. Também poderia chamar base.Equals ((BaseType) obj)), que estaria funcionando bem.
huha 27/08/13
2
Não, não vai: msdn.microsoft.com/en-us/library/system.object.gettype.aspx . Além disso, a implementação de um método não deve falhar ou ter êxito, dependendo da maneira como é chamado. Se o tipo de tempo de execução de um objeto for uma subclasse de alguma classe básica, então o Equals () da classe básica retornará true se for objrealmente igual a, thisindependentemente de como Equals () da classe básica foi chamada.
Jupiter
2
Mover fooItempara o topo e, em seguida, verificar se há nulo terá um desempenho melhor no caso de um tipo nulo ou errado.
IllidanS4 quer Monica de volta 06/02
1
@ 40Alpha Bem, sim, então obj as Fooseria inválido.
IllidanS4 quer Monica de volta 15/02
35

E se:

public override int GetHashCode()
{
    return string.Format("{0}_{1}_{2}", prop1, prop2, prop3).GetHashCode();
}

Assumindo que o desempenho não é um problema :)

Ludmil Tinkov
fonte
1
erm - mas você está a devolver uma cadeia para um método baseado int; _0
Tollan jim
32
Não, ele chama GetHashCode () do objeto String, que retorna um int.
Richard Clayton
3
Não espero que seja tão rápido quanto gostaria de ser, não apenas pelo boxe envolvido por tipos de valor, mas também pelo desempenho de string.Format. Outro nerd que eu já vi é new { prop1, prop2, prop3 }.GetHashCode(). Não é possível comentar qual seria mais lento entre esses dois. Não abuse das ferramentas.
Nawfal
16
Isso retornará verdadeiro para { prop1="_X", prop2="Y", prop3="Z" }e { prop1="", prop2="X_Y", prop3="Z_" }. Você provavelmente não quer isso.
voetsjoeba
2
Sim, você sempre pode substituir o símbolo de sublinhado por algo não tão comum (por exemplo, •, ▲, ►, ◄, ☺, ☻) e torcer para que seus usuários não usem esses símbolos ... :)
Ludmil Tinkov
13

Temos dois problemas para resolver.

  1. Você não pode fornecer um sentido GetHashCode()se qualquer campo no objeto puder ser alterado. Muitas vezes, um objeto NUNCA será usado em uma coleção que depende GetHashCode(). Portanto, o custo de implementação GetHashCode()geralmente não vale a pena ou não é possível.

  2. Se alguém colocar seu objeto em uma coleção que chama GetHashCode()e você substituir, Equals()sem fazer com que GetHashCode()se comporte da maneira correta, essa pessoa poderá passar dias rastreando o problema.

Portanto, por padrão, eu faço.

public class Foo
{
    public int FooId { get; set; }
    public string FooName { get; set; }

    public override bool Equals(object obj)
    {
        Foo fooItem = obj as Foo;

        if (fooItem == null)
        {
           return false;
        }

        return fooItem.FooId == this.FooId;
    }

    public override int GetHashCode()
    {
        // Some comment to explain if there is a real problem with providing GetHashCode() 
        // or if I just don't see a need for it for the given class
        throw new Exception("Sorry I don't know what GetHashCode should do for this class");
    }
}
Ian Ringrose
fonte
5
A exceção de GetHashCode é uma violação do contrato de objeto. Não há dificuldade em definir uma GetHashCodefunção de forma que dois objetos iguais retornem o mesmo código de hash; return 24601;e return 8675309;seriam implementações válidas de GetHashCode. O desempenho de Dictionaryapenas será decente quando o número de itens for pequeno e ficará muito ruim se o número de itens for grande, mas funcionará corretamente em qualquer caso.
Supercat 19/12
2
@ supercat, Não é possível implementar GetHashCode de maneira sensata se os campos de identificação no objeto puderem mudar, pois o código hash nunca deve mudar. Fazer o que você diz pode levar alguém a passar muitos dias rastreando o problema de desempenho e, em seguida, várias semanas em um grande sistema reprojetando para remover o uso dos dicionários.
quer
2
Eu costumava fazer algo assim para todas as classes que defini que necessitavam de Equals () e onde eu tinha certeza absoluta de que nunca usaria esse objeto como chave em uma coleção. Então, um dia, um programa em que eu tinha usado um objeto como esse para inserir um controle DevExpress XtraGrid caiu. Acontece que o XtraGrid, pelas minhas costas, estava criando um HashTable ou algo baseado em meus objetos. Entrei em uma discussão menor com o pessoal de suporte do DevExpress sobre isso. Eu disse que não era inteligente que eles baseassem a funcionalidade e a confiabilidade de seus componentes em uma implementação desconhecida do cliente de um método obscuro.
RenniePet
O pessoal do DevExpress era bastante irritante, basicamente dizendo que eu devo ser um idiota para lançar uma exceção em um método GetHashCode (). Ainda acho que eles devem encontrar um método alternativo de fazer o que estão fazendo - lembro-me de Marc Gravell em um tópico diferente, descrevendo como ele constrói um dicionário de objetos arbitrários sem depender de GetHashCode () - não consigo lembrar como ele fez isso Apesar.
RenniePet
4
@RenniePet, é melhor ter uma queda por lançar uma exceção, depois ter um erro muito difícil de encontrar devido a uma implementação inválida.
Ian Ringrose
12

Isso ocorre porque a estrutura exige que dois objetos iguais tenham o mesmo código hash. Se você substituir o método equals para fazer uma comparação especial de dois objetos e os dois objetos forem considerados iguais pelo método, o código de hash dos dois objetos também deverá ser o mesmo. (Dicionários e hashtables baseiam-se nesse princípio).

kemiller2002
fonte
11

Apenas para adicionar as respostas acima:

Se você não substituir Igual, o comportamento padrão é que as referências dos objetos sejam comparadas. O mesmo se aplica ao código de hash - a implementação padrão geralmente é baseada no endereço de memória da referência. Como você substituiu Equals, significa que o comportamento correto é comparar o que você implementou em Equals e não as referências; portanto, você deve fazer o mesmo com o código de hash.

Os clientes da sua classe esperam que o código hash tenha uma lógica semelhante ao método equals, por exemplo, os métodos linq que usam um IEqualityComparer comparam primeiro os códigos hash e, somente se forem iguais, eles compararão o método Equals (), que pode ser mais caro para executar, se não implementarmos o código de hash, o objeto igual provavelmente terá códigos de hash diferentes (porque eles têm um endereço de memória diferente) e será determinado incorretamente como não igual (Equals () nem atingirá).

Além disso, exceto o problema de que talvez você não consiga encontrar seu objeto se o tiver usado em um dicionário (porque ele foi inserido por um código de hash e quando você o procura, o código de hash padrão provavelmente será diferente e novamente Equals () nem será chamado, como Marc Gravell explica em sua resposta, você também introduzirá uma violação do dicionário ou do conceito de hashset que não deve permitir chaves idênticas - você já declarou que esses objetos são essencialmente os mesmos quando substituem o Igual para não deseja que ambos sejam chaves diferentes em uma estrutura de dados que suponha ter uma chave única, mas como eles têm um código de hash diferente, a chave "mesma" será inserida como uma chave diferente.

BornToCode
fonte
8

O código hash é usado para coleções baseadas em hash, como Dictionary, Hashtable, HashSet etc. O objetivo desse código é pré-classificar rapidamente objetos específicos, colocando-os em um grupo específico (bucket). Essa pré-classificação ajuda tremendamente na localização desse objeto quando você precisa recuperá-lo novamente da coleção de hash porque o código precisa procurar seu objeto em apenas um bloco em vez de em todos os objetos que ele contém. A melhor distribuição dos códigos de hash (melhor exclusividade) e a recuperação mais rápida. Na situação ideal em que cada objeto tem um código de hash exclusivo, descobrir que é uma operação O (1). Na maioria dos casos, ele se aproxima de O (1).

Maciej
fonte
7

Não é necessariamente importante; isso depende do tamanho das suas coleções e dos seus requisitos de desempenho e se sua classe será usada em uma biblioteca na qual você talvez não conheça os requisitos de desempenho. Sei com frequência que meus tamanhos de coleção não são muito grandes e meu tempo é mais valioso do que alguns microssegundos de desempenho obtidos com a criação de um código hash perfeito; então (para me livrar do aviso irritante do compilador) eu simplesmente uso:

   public override int GetHashCode()
   {
      return base.GetHashCode();
   }

(É claro que eu poderia usar um #pragma para desativar o aviso também, mas prefiro assim.)

Quando você está na posição que você não precisa do desempenho de todas as questões mencionadas por outros aqui se aplicam, naturalmente. Mais importante - caso contrário, você obterá resultados incorretos ao recuperar itens de um conjunto de hash ou dicionário: o código de hash não deve variar com o tempo de vida de um objeto (mais precisamente, durante o tempo em que o código de hash é necessário, como durante a uma chave em um dicionário): por exemplo, o seguinte está errado, pois Value é público e, portanto, pode ser alterado externamente para a classe durante o tempo de vida da instância, portanto, você não deve usá-lo como base para o código de hash:


   class A
   {
      public int Value;

      public override int GetHashCode()
      {
         return Value.GetHashCode(); //WRONG! Value is not constant during the instance's life time
      }
   }    

Por outro lado, se o Valor não puder ser alterado, você poderá usar:


   class A
   {
      public readonly int Value;

      public override int GetHashCode()
      {
         return Value.GetHashCode(); //OK  Value is read-only and can't be changed during the instance's life time
      }
   }
ILoveFortran
fonte
3
Votado. Isso está completamente errado. Até a Microsoft declara no MSDN ( msdn.microsoft.com/en-us/library/system.object.gethashcode.aspx ) que o valor de GetHashCode DEVE mudar quando o estado do objeto for alterado de uma maneira que possa afetar o valor de retorno de uma chamada para Equals () e, mesmo em seus exemplos, também mostra implementações GetHashCode que dependem totalmente de valores publicamente alteráveis.
Sebastian PR Gingter
Sebastian, eu discordo: se você adicionar um objeto a uma coleção que usa códigos de hash, ele será colocado em uma lixeira dependente do código de hash. Se você agora alterar o código de hash, não encontrará o objeto novamente na coleção, pois a lixeira errada será pesquisada. Isso é, de fato, algo que aconteceu em nosso código e foi por isso que achei necessário salientar isso.
ILoveFortran
2
Sebastian, Além disso, não consigo ver uma declaração no link ( msdn.microsoft.com/en-us/library/system.object.gethashcode.aspx ) que GetHashCode () deve ser alterado. Pelo contrário - NÃO deve mudar desde que Equals retorne o mesmo valor para o mesmo argumento: "O método GetHashCode para um objeto deve retornar consistentemente o mesmo código de hash, desde que não haja nenhuma modificação no estado do objeto que determine o valor de retorno do método Equals do objeto ". Esta declaração não implica o contrário, que deve ser alterada se o valor de retorno para Equals for alterado.
ILoveFortran
2
@ João, você está confundindo o lado cliente / consumidor do contrato com o produtor / implementador. Estou falando da responsabilidade do implementador, que substitui GetHashCode (). Você está falando sobre o consumidor, aquele que está usando o valor.
ILoveFortran
1
Incompreensão completa ... :) A verdade é que o código de hash deve mudar quando o estado do objeto muda, a menos que seja irrelevante para a identidade do objeto. Além disso, você nunca deve usar um objeto MUTABLE como chave em suas coleções. Use objetos somente leitura para esse fim. GetHashCode, Equals ... e alguns outros métodos cujos nomes não me lembro neste momento NUNCA devem lançar.
darlove
0

Você sempre deve garantir que, se dois objetos forem iguais, conforme definido por Equals (), eles retornem o mesmo código de hash. Como alguns dos outros comentários afirmam, em teoria isso não é obrigatório se o objeto nunca for usado em um contêiner baseado em hash como o HashSet ou o Dictionary. Eu aconselho você a sempre seguir esta regra. O motivo é simplesmente porque é muito fácil para alguém alterar uma coleção de um tipo para outro com a boa intenção de realmente melhorar o desempenho ou apenas transmitir a semântica do código de uma maneira melhor.

Por exemplo, suponha que mantemos alguns objetos em uma lista. Algum tempo depois, alguém realmente percebe que um HashSet é uma alternativa muito melhor devido às melhores características de pesquisa, por exemplo. É aí que podemos ter problemas. A lista usaria internamente o comparador de igualdade padrão para o tipo que significa Equals no seu caso, enquanto o HashSet usa GetHashCode (). Se os dois se comportarem de maneira diferente, o mesmo acontecerá com o seu programa. E lembre-se de que esses problemas não são os mais fáceis de solucionar.

Resumi esse comportamento com algumas outras armadilhas GetHashCode () em uma postagem do blog onde você pode encontrar mais exemplos e explicações.

Vasil Kosturski
fonte
0

A partir do .NET 4.7método preferido de substituição GetHashCode()é mostrado abaixo. Se você estiver direcionando versões .NET mais antigas, inclua o pacote de nuget System.ValueTuple .

// C# 7.0+
public override int GetHashCode() => (FooId, FooName).GetHashCode();

Em termos de desempenho, esse método superará a maioria das implementações de código hash composto . O ValueTuple é um structpara que não haja lixo, e o algoritmo subjacente é o mais rápido possível.

l33t
fonte
-1

Entendo que o GetHashCode () original retorna o endereço de memória do objeto, por isso é essencial substituí-lo se você deseja comparar dois objetos diferentes.

EDITADO: Isso estava incorreto, o método GetHashCode () original não pode garantir a igualdade de 2 valores. Embora objetos iguais retornem o mesmo código de hash.

user2855602
fonte
-6

Abaixo, usar a reflexão me parece uma opção melhor, considerando as propriedades públicas, pois com isso você não precisa se preocupar com a adição / remoção de propriedades (embora não seja um cenário tão comum). Também achei que esse desempenho estava melhor (tempo comparado usando o cronômetro da Diagonistics).

    public int getHashCode()
    {
        PropertyInfo[] theProperties = this.GetType().GetProperties();
        int hash = 31;
        foreach (PropertyInfo info in theProperties)
        {
            if (info != null)
            {
                var value = info.GetValue(this,null);
                if(value != null)
                unchecked
                {
                    hash = 29 * hash ^ value.GetHashCode();
                }
            }
        }
        return hash;  
    }
Guanxi
fonte
12
A implementação de GetHashCode () deve ser muito leve. Não sei se o reflexo é perceptível com o StopWatch em milhares de chamadas, mas certamente está em milhões (pense em preencher um dicionário de uma lista).
bohdan_trotsenko