Implementação padrão para Object.GetHashCode ()

Como funciona a implementação padrão para GetHashCode() ? E ele lida com estruturas, classs, matrizes, etc. de forma eficiente e bem o suficiente?

Eu estou tentando decidir em quais casos devo empacotar os meus e em quais casos posso confiar com segurança na implementação padrão para fazer o bem. Eu não quero reinventar a roda, se possível.

 namespace System { public class Object { [MethodImpl(MethodImplOptions.InternalCall)] internal static extern int InternalGetHashCode(object obj); public virtual int GetHashCode() { return InternalGetHashCode(this); } } } 

InternalGetHashCode é mapeado para uma function ObjectNative :: GetHashCode no CLR, que se parece com isto:

 FCIMPL1(INT32, ObjectNative::GetHashCode, Object* obj) { CONTRACTL { THROWS; DISABLED(GC_NOTRIGGER); INJECT_FAULT(FCThrow(kOutOfMemoryException);); MODE_COOPERATIVE; SO_TOLERANT; } CONTRACTL_END; VALIDATEOBJECTREF(obj); DWORD idx = 0; if (obj == 0) return 0; OBJECTREF objRef(obj); HELPER_METHOD_FRAME_BEGIN_RET_1(objRef); // Set up a frame idx = GetHashCodeEx(OBJECTREFToObject(objRef)); HELPER_METHOD_FRAME_END(); return idx; } FCIMPLEND 

A implementação completa do GetHashCodeEx é razoavelmente grande, portanto é mais fácil apenas vincular ao código-fonte do C ++ .

Para uma class, os padrões são essencialmente a igualdade de referência, e isso geralmente é bom. Se escrever uma estrutura, é mais comum ignorar a igualdade (não menos importante evitar o boxe), mas é muito raro você escrever uma estrutura de qualquer maneira!

Ao sobrescrever a igualdade, você deve sempre ter um Equals() e GetHashCode() Equals() ou seja, para dois valores, se Equals() retornar true eles devem retornar o mesmo hash-code, mas o inverso não é obrigatório) – e é comum para também fornecer operadores == / != , e frequentemente para implementar IEquatable também.

Para gerar o código hash, é comum usar uma sum fatorada, pois isso evita colisões em valores pareados – por exemplo, para um hash de campo básico de 2:

 unchecked // disable overflow, for the unlikely possibility that you { // are compiling with overflow-checking enabled int hash = 27; hash = (13 * hash) + field1.GetHashCode(); hash = (13 * hash) + field2.GetHashCode(); return hash; } 

Isso tem a vantagem de:

  • o hash de {1,2} não é o mesmo que o hash de {2,1}
  • o hash de {1,1} não é o mesmo que o hash de {2,2}

etc – que pode ser comum se apenas usar uma sum não ponderada, ou xor ( ^ ), etc.

A documentação para o método GetHashCode para Object diz que “a implementação padrão deste método não deve ser usada como um identificador de object exclusivo para propósitos de hashing”. e o de ValueType diz “Se você chamar o método GetHashCode do tipo derivado, o valor de retorno provavelmente não será adequado para uso como chave em uma tabela de hash.” .

Os tipos básicos de dados como byte , short , int , long , char e string implementam um bom método GetHashCode. Algumas outras classs e estruturas, como o Point por exemplo, implementam um método GetHashCode que pode ou não ser adequado às suas necessidades específicas. Você apenas tem que experimentá-lo para ver se é bom o suficiente.

A documentação de cada class ou estrutura pode informar se ela substitui a implementação padrão ou não. Se isso não for feito, você deverá usar sua própria implementação. Para qualquer class ou estrutura que você mesmo cria onde você precisa usar o método GetHashCode , você deve fazer sua própria implementação que use os membros apropriados para calcular o código hash.

De um modo geral, se você está substituindo Equals, você deseja replace GetHashCode. A razão para isso é porque ambos são usados ​​para comparar a igualdade de sua class / struct.

Equals é usado ao verificar Foo A, B;

if (A == B)

Como sabemos que o ponteiro provavelmente não corresponde, podemos comparar os membros internos.

 Equals(obj o) { if (o == null) return false; MyType Foo = o as MyType; if (Foo == null) return false; if (Foo.Prop1 != this.Prop1) return false; return Foo.Prop2 == this.Prop2; } 

GetHashCode é geralmente usado por tabelas de hash. O hashcode gerado por sua class deve sempre ser o mesmo para um estado de classs.

Eu costumo fazer

 GetHashCode() { int HashCode = this.GetType().ToString().GetHashCode(); HashCode ^= this.Prop1.GetHashCode(); etc. return HashCode; } 

Alguns dirão que o hashcode só deve ser calculado uma vez por vida útil do object, mas eu não concordo com isso (e provavelmente estou errado).

Usando a implementação padrão fornecida pelo object, a menos que você tenha a mesma referência a uma de suas classs, elas não serão iguais entre si. Substituindo Equals e GetHashCode, você pode relatar a igualdade com base nos valores internos em vez da referência de objects.

Como não consegui encontrar uma resposta que explica por que devemos replace GetHashCode e Equals para estruturas personalizadas e por que a implementação padrão “provavelmente não é adequada para uso como chave em uma tabela de hash”, deixarei um link para este post , o que explica por que com um exemplo real de um problema que aconteceu.

Eu recomendo a leitura de todo o post, mas aqui está um resumo (ênfase e esclarecimentos adicionados).

Motivo o hash padrão para estruturas é lento e não muito bom:

A forma como o CLR é projetado, cada chamada para um membro definido em System.ValueType ou System.Enum tipos [pode] causar uma alocação de boxe […]

Um implementador de uma function hash enfrenta um dilema: fazer uma boa distribuição da function hash ou torná-la rápida. Em alguns casos, é possível alcançar ambos, mas é difícil fazer isso genericamente em ValueType.GetHashCode .

A function hash canônica de uma estrutura “combina” códigos hash de todos os campos. Mas a única maneira de obter um código hash de um campo em um método ValueType é usar reflection . Assim, os autores do CLR decidiram negociar a velocidade sobre a distribuição e a versão padrão do GetHashCode apenas retorna um código hash de um primeiro campo não-nulo e “munges” com um ID de tipo […] Este é um comportamento razoável a menos que seja não. Por exemplo, se você for infeliz o suficiente e o primeiro campo de sua estrutura tiver o mesmo valor para a maioria das instâncias, uma function hash fornecerá o mesmo resultado o tempo todo. E, como você pode imaginar, isso causará um impacto drástico no desempenho se essas instâncias forem armazenadas em um conjunto de hash ou em uma tabela de hash.

[…] A implementação baseada em reflection é lenta . Muito devagar.

[…] Tanto ValueType.Equals quanto ValueType.GetHashCode possuem uma otimização especial. Se um tipo não tem “pointers” e é apropriadamente […] empacotado, versões mais otimizadas são usadas: GetHashCode itera sobre uma instância e blocos XOR de 4 bytes e o método Equals compara duas instâncias usando memcmp . […] Mas a otimização é muito complicada. Primeiro, é difícil saber quando a otimização está habilitada […] Segundo, uma comparação de memory não necessariamente lhe dará os resultados corretos . Aqui está um exemplo simples: […] -0.0 e -0.0 são iguais, mas têm diferentes representações binárias.

Problema do mundo real descrito no post:

 private readonly HashSet< (ErrorLocation, int)> _locationsWithHitCount; readonly struct ErrorLocation { // Empty almost all the time public string OptionalDescription { get; } public string Path { get; } public int Position { get; } } 

Usamos uma tupla que continha uma estrutura personalizada com implementação de igualdade padrão. E , infelizmente, a estrutura tinha um primeiro campo opcional que quase sempre era igual a [string vazia] . O desempenho foi OK até que o número de elementos no conjunto aumentasse significativamente, causando um problema real de desempenho, levando minutos para inicializar uma coleção com dezenas de milhares de itens.

Portanto, para responder à pergunta “em quais casos devo empacotar os meus e em quais casos posso confiar na implementação padrão”, pelo menos no caso de estruturas , você deve replace Equals e GetHashCode sempre que sua struct personalizada puder ser usada como chave em uma tabela de hash ou Dictionary .
Eu também recomendaria implementar IEquatable neste caso, para evitar o boxe.

Como as outras respostas disseram, se você está escrevendo uma class , o hash padrão usando igualdade de referência geralmente é bom, então eu não me incomodaria nesse caso, a menos que você precise replace Equals (então você teria que replace GetHashCode acordo) .