GetHashCode () problema usando xor

Question

O meu entendimento é que você está normalmente deveria usar xor com GetHashCode () para produzir um int para identificar os seus dados pelo seu valor (em oposição a por sua referência). Aqui está um exemplo simples:

class Foo
{
    int m_a;
    int m_b;

    public int A
    {
        get { return m_a; }
        set { m_a = value; }
    }

    public int B
    {
        get { return m_b; }
        set { m_b = value; }
    }

    public Foo(int a, int b)
    {
        m_a = a;
        m_b = b;
    }

    public override int GetHashCode()
    {
        return A ^ B;
    }

    public override bool Equals(object obj)
    {
        return this.GetHashCode() == obj.GetHashCode();
    }
}

Sendo a idéia, eu quero comparar uma instância de Foo para outro com base no valor das propriedades A e B. Se Foo1.A == Foo2.A e Foo1.B == Foo2.B, então temos a igualdade .

Aqui está o problema:

Foo one = new Foo(1, 2);
Foo two = new Foo(2, 1);

if (one.Equals(two)) { ... }  // This is true!

Estes ambos produzem um valor de 3 para GetHashCode (), causando Equals () para retornar verdadeiro. Obviamente, este é um exemplo trivial, e com apenas duas propriedades I poderia simplesmente comparar as propriedades individuais nas Iguais () method. No entanto, com uma classe mais complexa isso iria sair da mão rapidamente.

Eu sei que às vezes faz sentido para definir o código de hash apenas uma vez, e sempre retornar o mesmo valor. No entanto, para objetos mutáveis, onde é necessária uma avaliação da igualdade, eu não acho que isso é razoável.

Qual é a melhor maneira de valores de propriedade punho que poderiam ser facilmente trocados ao implementar GetHashCode ()?

Consulte também

O que é o melhor algoritmo para uma System.Object.GetHashCode substituído?

Answer 1

Primeiro - não implementar Equals () só em termos de GetHashCode () -. Hashcodes às vezes colidem, mesmo quando os objetos não são iguais

O contrato para GetHashCode () inclui o seguinte:

• diferentes hashcodes significa que os objetos não são definitivamente igual
• mesmos hashcodes, os objectos pode ser igual (mas possivelmente não)

Andrew Hare sugeriu que eu incorporar sua resposta:

Eu recomendo que você leia este solução (por nossa própria Jon Skeet , por sinal) de uma forma "melhor" para calcular um hashcode.

Não, o acima é relativamente lento e não ajuda muito. Algumas pessoas usam XOR (por exemplo, uma ^ b ^ c), mas prefere o tipo de processo apresentado em Js Bloch "Effective Java":

public override int GetHashCode()
{
    int hash = 23;
    hash = hash*37 + craneCounterweightID;
    hash = hash*37 + trailerID;
    hash = hash*37 + craneConfigurationTypeCode.GetHashCode();
    return hash;
}

O 23 e 37 são números arbitrários que são co-prime.

O benefício do acima sobre o XOR método é que se você tem um tipo que tem dois valores que são frequentemente o mesmo, XORing aqueles valores sempre vai dar o mesmo Resultado (0), enquanto que a vontade acima diferenciar entre elas, a menos você está muito azarado.

Como mencionado no trecho acima, você também pode querer olhar para o livro de Joshua Bloch , Effective Java, que contém um tratamento agradável do sujeito (a discussão hashcode se aplica a NET também).

Answer 2

Andrew postou um bom exemplo para gerar um melhor código de hash, mas também ter em mente que você não deve usar códigos de hash como uma verificação de igualdade, uma vez que eles não são garantidos para ser único.

Para um exemplo trivial de por que isso é considerar um objeto duplo. Tem mais valores possíveis de um int por isso é impossível ter um int exclusivo para cada dupla. Hashes são realmente apenas uma primeira passagem, usado em situações como um dicionário quando você precisa encontrar a chave rapidamente, pela primeira hashes comparando uma grande porcentagem das chaves possíveis podem ser descartadas e apenas as teclas com hashes correspondentes precisa ter a despesa de um cheque plena igualdade (ou outro href="http://en.wikipedia.org/wiki/Hash_table#Collision_resolution" rel="nofollow resolução colisão métodos).

Answer 3

Hashing sempre envolve colisões e você tem que lidar com isso (F. E., comparar valores de hash e se eles são iguais, comparar exatamente os valores dentro das classes para ter certeza as classes são iguais).

Usando um simples XOR, você vai ter muitas colisões. Se você quiser menos, usar algumas funções matemáticas que distribuem valores em diferentes bits (turnos bit, multiplicando com primos etc.).

Answer 4

Leia Overriding GetHashCode para objetos mutáveis? C # e pensar sobre a implementação IEquatable<T>

Answer 5

A geração rápida e boa distribuição de haxixe

public override int GetHashCode()
{
    return A.GetHashCode() ^ B.GetHashCode();         // XOR
}

Answer 6

Por curiosidade desde hashcodes são tipicamente uma má idéia para comparação, não seria melhor apenas fazer o seguinte código, ou estou faltando alguma coisa?

public override bool Equals(object obj)
{
    bool isEqual = false;
    Foo otherFoo = obj as Foo;
    if (otherFoo != null)
    {
        isEqual = (this.A == otherFoo.A) && (this.B == otherFoo.B);
    }
    return isEqual;
}

Answer 7

Existem várias melhores implementações de hash. FNV de hash por exemplo.