Diretrizes GetHashCode em C #

136

Eu li no livro Essential C # 3.0 e .NET 3.5 que:

Os retornos de GetHashCode () durante a vida útil de um objeto específico devem ser constantes (o mesmo valor), mesmo que os dados do objeto sejam alterados. Em muitos casos, você deve armazenar em cache o retorno do método para impor isso.

Esta é uma diretriz válida?

Eu tentei alguns tipos internos no .NET e eles não se comportaram assim.

Joan Venge
fonte
Você pode considerar alterar a resposta aceita, se possível.
Giffyguy 23/09

Respostas:

93

A resposta é principalmente: é uma diretriz válida, mas talvez não seja uma regra válida. Também não conta a história toda.

O ponto importante é que, para tipos mutáveis, não é possível basear o código hash nos dados mutáveis, porque dois objetos iguais devem retornar o mesmo código hash e o código hash deve ser válido durante toda a vida útil do objeto. Se o código de hash for alterado, você acabará com um objeto que se perde em uma coleção de hash, porque ele não fica mais no hash bin correto.

Por exemplo, o objeto A retorna um hash de 1. Portanto, ele entra no compartimento 1 da tabela de hash. Em seguida, você altera o objeto A para que ele retorne um hash de 2. Quando uma tabela de hash vai procurá-lo, ele olha no bin 2 e não consegue encontrá-lo - o objeto fica órfão no bin 1. É por isso que o código de hash deve não muda durante a vida útil do objeto , e apenas um motivo para escrever implementações GetHashCode é um problema.

Atualização
Eric Lippert postou um blog que fornece informações excelentes sobre GetHashCode.

Atualização adicional
Fiz algumas alterações acima:

  1. Eu fiz uma distinção entre diretriz e regra.
  2. Eu percebi "durante toda a vida útil do objeto".

Uma diretriz é apenas um guia, não uma regra. Na realidade, GetHashCodesomente é necessário seguir essas diretrizes quando as coisas esperam que o objeto siga as diretrizes, como quando está sendo armazenado em uma tabela de hash. Se você nunca pretende usar seus objetos em tabelas de hash (ou qualquer outra coisa que dependa das regras de GetHashCode), sua implementação não precisará seguir as diretrizes.

Quando vir "durante toda a vida útil do objeto", leia "durante o tempo em que o objeto precisar cooperar com tabelas de hash" ou similar. Como a maioria das coisas, GetHashCodeé sobre saber quando quebrar as regras.

Jeff Yates
fonte
1
Como você determina a igualdade entre tipos mutáveis?
Jon B
9
Você não deve usar GetHashCode para determinar a igualdade.
JSB # 20/01/09
4
@ Bang Bang - Do MSDN: Classes derivadas que substituem GetHashCode também devem substituir Equals para garantir que dois objetos considerados iguais tenham o mesmo código de hash; caso contrário, o tipo Hashtable pode não funcionar corretamente.
Jon B
3
@ Joan Venge: Duas coisas. Primeiro, nem a Microsoft tem o GetHashCode certo em todas as implementações. Segundo, os tipos de valor geralmente são imutáveis, sendo cada valor uma nova instância, e não uma modificação de uma instância existente.
1011 Jeff Yates
17
Como a.Equals (b) deve significar que a.GetHashCode () == b.GetHashCode (), o código de hash geralmente deve ser alterado se os dados usados ​​para comparação de igualdade forem alterados. Eu diria que o problema não é GetHashCode ser baseado em dados mutáveis. O problema é usar objetos mutáveis ​​como chaves de tabela de hash (e realmente modificá-los). Estou errado?
Niklas
120

Já faz muito tempo, mas, no entanto, acho que ainda é necessário dar uma resposta correta a essa pergunta, incluindo explicações sobre os porquês e os comos. A melhor resposta até agora é a que cita exaustivamente o MSDN - não tente criar suas próprias regras, os funcionários da MS sabiam o que estavam fazendo.

Mas primeiro as primeiras coisas: a diretriz citada na pergunta está errada.

Agora os porquês - há dois deles

Primeiro, por que : Se o código de hash for calculado de alguma maneira, ele não será alterado durante a vida útil de um objeto, mesmo que o próprio objeto seja alterado, isso quebraria o contrato de igual.

Lembre-se: "Se dois objetos forem comparados como iguais, o método GetHashCode para cada objeto deverá retornar o mesmo valor. No entanto, se dois objetos não forem comparados como iguais, os métodos GetHashCode para os dois objetos não precisarão retornar valores diferentes."

A segunda frase geralmente é mal interpretada como "A única regra é que, no momento da criação do objeto, o código hash de objetos iguais deve ser igual". Realmente não sei o porquê, mas essa é também a essência da maioria das respostas aqui.

Pense em dois objetos que contêm um nome, onde o nome é usado no método equals: Mesmo nome -> mesma coisa. Criar instância A: Nome = Joe Criar instância B: Nome = Peter

Hashcode A e Hashcode B provavelmente não serão os mesmos. O que aconteceria agora, quando o Nome da instância B for alterado para Joe?

De acordo com a diretriz da pergunta, o código de hash de B não mudaria. O resultado seria: A.Equals (B) ==> true Mas, ao mesmo tempo: A.GetHashCode () == B.GetHashCode () ==> false.

Mas exatamente esse comportamento é proibido explicitamente pelo equals & hashcode-contract.

Segundo por que : Embora seja verdade que as alterações no código hash possam quebrar listas de hash e outros objetos usando o código hash, o inverso também é verdadeiro. Se você não alterar o código de hash, no pior dos casos, obterá listas de hash, onde muitos objetos diferentes terão o mesmo código de hash e, portanto, o mesmo hash bin - acontece quando objetos são inicializados com um valor padrão, por exemplo.


Agora, chegando aos comos Bem, à primeira vista, parece haver uma contradição - de qualquer forma, o código irá quebrar. Mas nenhum problema vem de código hash alterado ou inalterado.

A fonte dos problemas está bem descrita no MSDN:

Na entrada da tabela de hash do MSDN:

Os objetos-chave devem ser imutáveis ​​desde que sejam utilizados como chaves no Hashtable.

Isso significa:

Qualquer objeto que cria um valor hash deve alterar o valor hash, quando o objeto muda, mas não deve - absolutamente não deve - permitir alterações a si próprio, quando é usado dentro de um Hashtable (ou qualquer outro objeto que use Hash, é claro) .

Primeiro, como a maneira mais fácil seria, obviamente, projetar objetos imutáveis ​​apenas para uso em hashtables, que serão criados como cópias dos objetos normais e mutáveis, quando necessário. Dentro dos objetos imutáveis, é óbvio que é bom armazenar em cache o código hash, pois é imutável.

Segundo como: Ou dê ao objeto uma bandeira "você está com hash agora", verifique se todos os dados do objeto são privados, verifique o sinalizador em todas as funções que podem alterar os dados dos objetos e ative uma exceção se a alteração não for permitida (ou seja, o sinalizador está definido ) Agora, quando você colocar o objeto em qualquer área com hash, certifique-se de definir o sinalizador e - também - desative o sinalizador quando ele não for mais necessário. Para facilitar o uso, aconselho definir o sinalizador automaticamente dentro do método "GetHashCode" - desta forma, não pode ser esquecido. E a chamada explícita de um método "ResetHashFlag" garantirá que o programador tenha que pensar se é ou não permitido alterar os dados dos objetos agora.

Ok, o que deve ser dito também: Há casos em que é possível ter objetos com dados mutáveis, em que o código hash permanece inalterado, quando os dados dos objetos são alterados, sem violar os contratos iguais e hashcode.

No entanto, isso exige que o método dos iguais também não seja baseado nos dados mutáveis. Portanto, se eu escrever um objeto e criar um método GetHashCode que calcule um valor apenas uma vez e o armazene dentro do objeto para retorná-lo em chamadas posteriores, devo: novamente: absolutamente preciso, criar um método Equals, que usará valores armazenados para a comparação, para que A.Equals (B) nunca mude de falso para verdadeiro também. Caso contrário, o contrato seria quebrado. O resultado disso geralmente será que o método Equals não faz sentido - não é a referência original igual, mas também não é um valor igual. Às vezes, esse pode ser o comportamento pretendido (ou seja, registros de clientes), mas geralmente não é.

Portanto, basta alterar o resultado de GetHashCode, quando os dados do objeto forem alterados e se o uso do objeto dentro de hash usando listas ou objetos for pretendido (ou apenas possível), tornar o objeto imutável ou criar um sinalizador somente leitura para usar no vida útil de uma lista de hash que contém o objeto.

(A propósito: Tudo isso não é C # ou específico do .NET - é da natureza de todas as implementações de hashtable, ou mais geralmente de qualquer lista indexada, que os dados de identificação dos objetos nunca devem mudar, enquanto o objeto está na lista Comportamento inesperado e imprevisível ocorrerá, se essa regra for violada. Em algum lugar, pode haver implementações de lista que monitoram todos os elementos da lista e reindexam a lista automaticamente - mas o desempenho desses certamente será horrível, na melhor das hipóteses.

Alex
fonte
23
+ 1 para esta explicação detalhada (daria mais se eu pudesse) #
Oliver
5
+1, esta é definitivamente a melhor resposta, devido à explicação detalhada! :)
Joe
9

Do MSDN

Se dois objetos forem comparados como iguais, o método GetHashCode para cada objeto deverá retornar o mesmo valor. No entanto, se dois objetos não forem comparados como iguais, os métodos GetHashCode para os dois objetos não precisarão retornar valores diferentes.

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. Observe que isso é verdadeiro apenas para a execução atual de um aplicativo e que um código de hash diferente pode ser retornado se o aplicativo for executado novamente.

Para o melhor desempenho, uma função de hash deve gerar uma distribuição aleatória para todas as entradas.

Isso significa que, se os valores do objeto mudarem, o código de hash deve mudar. Por exemplo, uma classe "Pessoa" com a propriedade "Nome" definida como "Tom" deve ter um código de hash e um código diferente se você alterar o nome para "Jerry". Caso contrário, Tom == Jerry, que provavelmente não é o que você pretendia.


Editar :

Também do MSDN:

Classes derivadas que substituem GetHashCode também devem substituir Equals para garantir que dois objetos considerados iguais tenham o mesmo código de hash; caso contrário, o tipo Hashtable pode não funcionar corretamente.

Da entrada da tabela de hash do MSDN :

Os objetos-chave devem ser imutáveis ​​desde que sejam usados ​​como chaves no Hashtable.

A maneira como li isso é que objetos mutáveis devem retornar códigos de hash diferentes conforme seus valores mudam, a menos que sejam projetados para uso em uma hashtable.

No exemplo de System.Drawing.Point, o objecto é mutável, e faz retornar uma hashcode diferente quando o x ou y alterações de valor. Isso tornaria um candidato ruim para ser usado como está em uma hashtable.

Jon B
fonte
GetHashCode () foi projetado para uso em uma hashtable, esse é o único ponto dessa função.
Skolima
@skolima - a documentação do MSDN é inconsistente com isso. Objetos mutáveis ​​podem implementar GetHashCode () e devem retornar valores diferentes conforme o valor do objeto é alterado. As tabelas de hash devem usar chaves imutáveis. Portanto, você pode usar GetHashCode () para algo diferente de uma hashtable.
Jon B
9

Eu acho que a documentação referente ao GetHashcode é um pouco confusa.

Por um lado, o MSDN afirma que o código de hash de um objeto nunca deve mudar e é constante. Por outro lado, o MSDN também afirma que o valor de retorno do GetHashcode deve ser igual para 2 objetos, se esses 2 objetos forem considerados iguais.

MSDN:

Uma função de hash deve ter as seguintes propriedades:

  • Se dois objetos forem comparados como iguais, o método GetHashCode para cada objeto deverá retornar o mesmo valor. No entanto, se dois objetos não forem comparados como iguais, os métodos GetHashCode para os dois objetos não precisarão retornar valores diferentes.
  • 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. Observe que isso é verdadeiro apenas para a execução atual de um aplicativo e que um código de hash diferente pode ser retornado se o aplicativo for executado novamente.
  • Para o melhor desempenho, uma função de hash deve gerar uma distribuição aleatória para todas as entradas.

Então, isso significa que todos os seus objetos devem ser imutáveis ​​ou o método GetHashcode deve ser baseado nas propriedades imutáveis ​​do seu objeto. Suponha, por exemplo, que você tenha esta classe (implementação ingênua):

public class SomeThing
{
      public string Name {get; set;}

      public override GetHashCode()
      {
          return Name.GetHashcode();
      }

      public override Equals(object other)
      {
           SomeThing = other as Something;
           if( other == null ) return false;
           return this.Name == other.Name;
      }
}

Esta implementação já viola as regras que podem ser encontradas no MSDN. Suponha que você tenha 2 instâncias dessa classe; a propriedade Name da instância1 está definida como 'Pol' e a propriedade Name da instância2 está definida como 'Piet'. Ambas as instâncias retornam um código de hash diferente e também não são iguais. Agora, suponha que eu mude o Nome da instância2 para 'Pol'; então, de acordo com meu método Equals, ambas as instâncias devem ser iguais e, de acordo com uma das regras do MSDN, elas devem retornar o mesmo código hash.
No entanto, isso não pode ser feito, pois o código de hash da instância2 será alterado e o MSDN declara que isso não é permitido.

Então, se você tiver uma entidade, talvez possa implementar o código hash para que ele use o 'identificador primário' dessa entidade, que talvez seja idealmente uma chave substituta ou uma propriedade imutável. Se você tiver um objeto de valor, poderá implementar o Hashcode para que ele use as 'propriedades' desse objeto de valor. Essas propriedades compõem a 'definição' do objeto de valor. É claro que essa é a natureza de um objeto de valor; você não está interessado em sua identidade, mas em seu valor.
E, portanto, objetos de valor devem ser imutáveis. (Assim como eles estão no framework .NET, string, Date, etc ... são todos objetos imutáveis).

Outra coisa que vem à mente:
durante a qual 'sessão' (não sei realmente como devo chamar isso) 'GetHashCode' deve retornar um valor constante. Suponha que você abra seu aplicativo, carregue uma instância de um objeto fora do banco de dados (uma entidade) e obtenha seu código de hash. Retornará um certo número. Feche o aplicativo e carregue a mesma entidade. É necessário que o código de hash desta vez tenha o mesmo valor de quando você carregou a entidade pela primeira vez? IMHO, não.

Frederik Gheysels
fonte
1
Seu exemplo é por que Jeff Yates diz que você não pode basear o código hash nos dados mutáveis. Você não pode colar um objeto mutável em um dicionário e espera que funcione bem se o código hash for baseado nos valores mutáveis ​​desse objeto.
Ogre Psalm33
3
Não consigo ver onde a regra do MSDN foi violada? A regra diz claramente: 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 . Isto significa que hashcode de instance2 é permitido ser alterado quando altera o nome de instance2 para Pol
chikak
8

Este é um bom conselho. Aqui está o que Brian Pepin tem a dizer sobre o assunto:

Isso provocou-me mais de uma vez: Verifique se GetHashCode sempre retorna o mesmo valor ao longo da vida útil de uma instância. Lembre-se de que códigos de hash são usados ​​para identificar "buckets" na maioria das implementações de hashtable. Se o "bloco" de um objeto for alterado, talvez uma hashtable não consiga encontrá-lo. Esses erros podem ser muito difíceis de encontrar, portanto, faça a correção da primeira vez.

Justin R.
fonte
Não votei negativamente, mas acho que outros o fizeram porque é uma citação que não cobre todo o problema. Finja que as strings eram mutáveis, mas não alteraram códigos de hash. Você cria "bob", usa-o como uma chave em uma hashtable e altera seu valor para "phil". Em seguida, crie uma nova string "phil". se você procurar uma entrada de tabela de hash com a chave "phil", o item inserido originalmente não será encontrado. Se alguém pesquisasse "bob", seria encontrado, mas você obteria um valor que talvez não esteja mais correto. Seja diligente para não usar chaves que sejam mutáveis ​​ou esteja ciente dos perigos.
Eric Tuttleman
@ EricTuttleman: Se eu estivesse escrevendo as regras para uma estrutura, teria especificado que, para qualquer par de objetos Xe Y, uma vez X.Equals(Y)ou Y.Equals(X)tenha sido chamado, todas as chamadas futuras deverão produzir o mesmo resultado. Se alguém quiser usar alguma outra definição de igualdade, use um EqualityComparer<T>.
Supercat 21/13
5

Não estou respondendo diretamente à sua pergunta, mas - se você usa o Resharper, não esqueça que ele possui um recurso que gera uma implementação razoável de GetHashCode (assim como o método Equals) para você. É claro que você pode especificar quais membros da classe serão levados em consideração ao calcular o código hash.

petr k.
fonte
Obrigado, na verdade, eu nunca usei o Resharper, mas continuo vendo isso sendo mencionado com bastante frequência, então devo tentar.
22611 Joan Venge
+1 Reaharper, se houver, gera uma boa implementação GetHashCode.
ΩmegaMan
5

Confira esta postagem do blog de Marc Brooks:

VTOs, RTOs e GetHashCode () - oh, que coisa!

E, em seguida, confira o post de acompanhamento (não é possível vincular porque sou novo, mas há um link no artigo inicial) que discute mais e cobre alguns pontos fracos da implementação inicial.

Isso era tudo que eu precisava saber sobre a criação de uma implementação GetHashCode (), ele até fornece um download de seu método junto com alguns outros utilitários, em resumo.

Shaun
fonte
4

O hashcode nunca muda, mas também é importante entender de onde vem o Hashcode.

Se seu objeto estiver usando semântica de valores, ou seja, a identidade do objeto é definida por seus valores (como String, Color, todas as estruturas). Se a identidade do seu objeto for independente de todos os seus valores, o Hashcode será identificado por um subconjunto de seus valores. Por exemplo, sua entrada StackOverflow é armazenada em um banco de dados em algum lugar. Se você alterar seu nome ou e-mail, sua entrada de cliente permanecerá a mesma, embora alguns valores tenham sido alterados (em última análise, você geralmente é identificado por algum número de ID de cliente longo).

Então, resumindo:

Semântica do tipo de valor - o código de hash é definido por valores Semântica do tipo de referência - o código de hash é definido por algum id

Eu sugiro que você leia Domain Driven Design, de Eric Evans, onde ele entra em entidades versus tipos de valor (que é mais ou menos o que eu tentei fazer acima) se isso ainda não faz sentido.

DavidN
fonte
Isso não está realmente correto. O código hash deve permanecer constante para uma instância específica. No caso de tipos de valor, geralmente é o caso de que cada valor é uma instância única e, portanto, o hash parece mudar, mas na verdade é uma nova instância.
911 Jeff Yates
Você está certo, os tipos de valor são imutáveis ​​e impedem a alteração. Boa pegada.
DavidN