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

Como funciona a implementação padrão GetHashCode()? E ele lida com estruturas, classes, matrizes etc. de maneira eficiente e suficientemente boa?

Estou tentando decidir em quais casos devo embalar o meu e em quais casos posso confiar com segurança na implementação padrão para fazer o bem. 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 função ObjectNative :: GetHashCode no CLR, que se parece com isso:

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 é bastante grande, portanto, é mais fácil vincular apenas ao código-fonte C ++ .

Para uma classe, os padrões são essencialmente a igualdade de referência, e isso geralmente é bom. Ao escrever uma estrutura, é mais comum substituir a igualdade (principalmente para evitar o boxe), mas é muito raro você escrever uma estrutura de qualquer maneira!

Ao substituir a igualdade, você deve sempre ter uma correspondência Equals()e GetHashCode()(por exemplo, para dois valores, se Equals()retorna true, eles devem retornar o mesmo código hash, mas o inverso não é necessário) - e é comum também fornecer ==/ !=operadores e, frequentemente, implementar IEquatable<T>também.

Para gerar o código hash, é comum usar uma soma fatorada, pois isso evita colisões em valores emparelhados - por exemplo, para um hash básico de 2 campos:

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 que:

• 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 - o que pode ser comum se você estiver usando uma soma não ponderada, ou xor ( ^), etc.

A documentação do GetHashCodemétodo para Object diz que "a implementação padrão deste método não deve ser usada como um identificador de objeto exclusivo para fins de hash". e o valor de ValueType diz "Se você chamar o método GetHashCode do tipo derivado, é provável que o valor de retorno não seja adequado para uso como chave em uma tabela de hash". .

Os tipos de dados básicos, como byte, short, int, long, chare stringimplementar um método bom GetHashCode. Algumas outras classes e estruturas, como Pointpor exemplo, implementam um GetHashCodemétodo que pode ou não ser adequado às suas necessidades específicas. Você só precisa experimentá-lo para ver se é bom o suficiente.

A documentação para cada classe ou estrutura pode dizer se substitui a implementação padrão ou não. Se não o substituir, você deve usar sua própria implementação. Para quaisquer classes ou estruturas criadas por você, nas quais é necessário usar o GetHashCodemétodo, você deve fazer sua própria implementação que usa os membros apropriados para calcular o código de hash.

Como não consegui encontrar uma resposta que explique por que devemos substituir GetHashCodee Equalspara 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 blog. post , o que explica por que, com um exemplo real de um problema que aconteceu.

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

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

A maneira como o CLR é projetado, toda chamada para um membro definido System.ValueTypeou System.Enumdigita [pode] causar uma alocação de boxe [...]

Um implementador de uma função hash enfrenta um dilema: faça uma boa distribuição da função hash ou agilize-a. Em alguns casos, é possível alcançar os dois, mas é difícil fazer isso genericamente no ValueType.GetHashCode.

A função de hash canônico de uma estrutura "combina" códigos de hash de todos os campos. Mas a única maneira de obter um código de hash de um campo em um ValueTypemétodo é usar a reflexão . Assim, os autores do CLR decidiram negociar a velocidade pela distribuição e a GetHashCodeversão padrão apenas retorna um código de hash de um primeiro campo não nulo e o "mescla" com uma identificação de tipo. [...] Esse é um comportamento razoável, a menos que não seja . Por exemplo, se você não tiver o suficiente e o primeiro campo da sua estrutura tiver o mesmo valor para a maioria das instâncias, uma função 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 tabela de hash.

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

[...] Ambos ValueType.Equalse ValueType.GetHashCodetem uma otimização especial. Se um tipo não possui "ponteiros" e está devidamente compactado, [...] são utilizadas versões mais ideais: GetHashCodeitera sobre uma instância e blocos XORs de 4 bytes e o Equalsmétodo compara duas instâncias usando memcmp. [...] Mas a otimização é muito complicada. Primeiro, é difícil saber quando a otimização está ativada. [...] Segundo, uma comparação de memória não fornecerá necessariamente os resultados certos . Aqui está um exemplo simples: [...] -0.0e +0.0sã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 teve um primeiro campo opcional quase sempre igual a [string vazia] . O desempenho foi bom até o número de elementos no conjunto aumentar significativamente, causando um problema real de desempenho, levando alguns minutos para inicializar uma coleção com dezenas de milhares de itens.

Portanto, para responder à pergunta "em quais casos eu devo compactar minha conta e em quais casos posso confiar com segurança na implementação padrão", pelo menos no caso de estruturas , você deve substituir Equalse GetHashCodesempre que sua estrutura personalizada puder ser usada como um digite uma tabela de hash ou Dictionary.
Eu também recomendaria implementar IEquatable<T>neste caso, para evitar o boxe.

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

De um modo geral, se você estiver substituindo Igual, você deseja substituir GetHashCode. A razão para isso é porque ambos são usados ​​para comparar a igualdade de sua classe / estrutura.

Igual é usado ao verificar Foo A, B;

se (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 código hash gerado por sua classe deve sempre ser o mesmo para um estado de classe.

Eu normalmente faço,

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

    return HashCode;
}

Alguns dirão que o código hash deve ser calculado apenas uma vez por vida útil do objeto, mas não concordo com isso (e provavelmente estou errado).

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

Se você está apenas lidando com POCOs, pode usar este utilitário para simplificar um pouco sua vida:

var hash = HashCodeUtil.GetHashCode(
           poco.Field1,
           poco.Field2,
           ...,
           poco.FieldN);

...

public static class HashCodeUtil
{
    public static int GetHashCode(params object[] objects)
    {
        int hash = 13;

        foreach (var obj in objects)
        {
            hash = (hash * 7) + (!ReferenceEquals(null, obj) ? obj.GetHashCode() : 0);
        }

        return hash;
    }
}