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

Question

Como é que a implementação padrão para o trabalho GetHashCode()? E isso lidar com estruturas, classes, arrays, etc. de forma eficiente e bem o suficiente?

Eu estou tentando decidir em que casos devo embalar minha própria e em que casos eu posso seguramente contar com a implementação padrão para fazer bem. Eu não quero reinventar a roda, se possível.

Answer 1

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 um ObjectNative :: GetHashCode função no CLR, que tem esta aparência:

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, por isso é mais fácil simplesmente link para do C ++ código-fonte .

Answer 2

Para uma classe, os padrões são essencialmente igualdade de referência, e que é geralmente bem. Se escrever um struct, é mais comum para substituir a igualdade (não menos importante para o boxe evitar), mas é muito raro você escreve um struct de qualquer maneira!

Ao substituir a igualdade, você deve sempre ter um Equals() correspondência e GetHashCode() (ou seja, para dois valores, se Equals() retornos verdade que eles deve retornar o mesmo hash-código, mas o inverso é não obrigatório) -. e é comum também fornecem == / !=operators, e muitas vezes para implementar IEquatable<T> demasiado

Para gerar o código de hash, é comum o uso de uma soma consignado, como isso evita colisões em valores emparelhados - por exemplo, para um hash básica 2 campo:

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;
}

Isto tem a vantagem 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 -. Que pode ser comum, se utilizando apenas uma soma não ponderada, ou xor (^), etc

Answer 3

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

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

A documentação para cada classe ou estrutura pode dizer se ela substitui a implementação padrão ou não. Se ele não substituí-lo você deve usar sua própria implementação. Para todas as classes ou estruturas que você cria a si mesmo onde você precisa usar o método GetHashCode, você deve fazer a sua própria implementação que usa os membros apropriados para calcular o código hash.

Answer 4

Uma vez que eu não poderia encontrar uma resposta que explica por que deve substituir GetHashCode e Equals para estruturas personalizadas e por a implementação padrão "não é provável que seja apropriado para o uso como uma chave em uma tabela hash", eu vou deixar um link para este post , o que explica com um exemplo do caso real de um problema que aconteceu.

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

Razão o hash padrão para estruturas é lento e não muito boa:

A forma como o CLR é projetado, cada chamada para um membro definido na System.ValueType ou System.Enum tipos [Maio] causa uma alocação boxe [...]

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

A função hash canônica de um struct "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 método ValueType é uso reflexão . Assim, os autores CLR decidiu velocidade comercial sobre a distribuição ea versão GetHashCode padrão apenas retorna um código hash de um primeiro campo não nulo e "munges-lo" com um ID de tipo [...] este é um comportamento razoável, a menos que não é. Por exemplo, Se você é bastante sorte e o primeiro campo de sua estrutura tem o mesmo valor para a maioria dos casos, em seguida, uma função hash irá fornecer o mesmo resultado o tempo todo. E, como você pode imaginar, isso vai causar um impacto no desempenho drástica se estes casos são armazenados em um conjunto de hash ou uma tabela hash.

[...] implementação baseada em reflexão é lento . Muito lento.

[...] Tanto ValueType.Equals e ValueType.GetHashCode tem uma otimização especial. Se um tipo não tem "ponteiros" e está devidamente embalado [...], em seguida, versões mais ideais são usados: itera GetHashCode mais de uma instância e XORs blocos de 4 bytes e método Equals compara duas instâncias usando memcmp. [...] Mas a otimização é muito complicado. Primeiro, é difícil saber quando a otimização está habilitado [...] Em segundo lugar, a comparação de memória não vai necessariamente dar-lhe os resultados da direita . 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; }
}

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

Assim, para responder à pergunta "Em que casos devo embalar minha própria e em que casos eu posso confiar com segurança na implementação padrão", pelo menos no caso de estruturas , você deve substituir Equals e GetHashCode sempre que o seu struct personalizado pode ser usado como uma chave em uma tabela hash ou Dictionary.
Também gostaria de recomendar a implementação IEquatable<T> neste caso, para o boxe evitar.

Como as outras respostas disse, se você está escrevendo um class , o hash padrão usando igualdade de referência é geralmente bem, então eu não me incomoda neste caso, menos você precisará substituir Equals (então você teria que substituir GetHashCode em conformidade).

Answer 5

De um modo geral, se você está substituindo Equals, que pretende substituir GetHashCode. A razão para isso é porque ambos são usados ??para comparar a igualdade de sua classe / struct.

Igual é usado para verificar Foo A, B;

Se (A == B)

Uma vez que sabemos o ponteiro não é susceptível de corresponder, 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 utilizado por tabelas de hash. O hashcode gerado pela sua classe deve ser sempre o mesmo para algumas classes dar estado.

Eu normalmente faço,

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

    return HashCode;
}

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

Usando a implementação padrão fornecido pelo objeto, a menos que você tem a mesma referência a uma das suas classes, eles não serão iguais entre si. Substituindo Equals e GetHashCode, pode comunicar a igualdade com base nos valores internos em vez da referência a objetos.

Answer 6

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

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;
    }
}