GetHashCode() problem using xor

Question

My understanding is that you're typically supposed to use xor with GetHashCode() to produce an int to identify your data by its value (as opposed to by its reference). Here's a simple example:

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

The idea being, I want to compare one instance of Foo to another based on the value of properties A and B. If Foo1.A == Foo2.A and Foo1.B == Foo2.B, then we have equality.

Here's the problem:

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

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

These both produce a value of 3 for GetHashCode(), causing Equals() to return true. Obviously, this is a trivial example, and with only two properties I could simply compare the individual properties in the Equals() method. However, with a more complex class this would get out of hand quickly.

I know that sometimes it makes good sense to set the hash code only once, and always return the same value. However, for mutable objects where an evaluation of equality is necessary, I don't think this is reasonable.

What's the best way to handle property values that could easily be interchanged when implementing GetHashCode()?

See Also

What is the best algorithm for an overridden System.Object.GetHashCode?

Cruce

Answer 1

First off - Do not implement Equals() only in terms of GetHashCode() - hashcodes will sometimes collide even when objects are not equal.

The contract for GetHashCode() includes the following:

• different hashcodes means that objects are definitely not equal
• same hashcodes means objects might be equal (but possibly might not)

Andrew Hare suggested I incorporate his answer:

I would recommend that you read this solution (by our very own Jon Skeet, by the way) for a "better" way to calculate a hashcode.

No, the above is relatively slow and doesn't help a lot. Some people use XOR (eg a ^ b ^ c) but I prefer the kind of method shown in Josh Bloch's "Effective Java":

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

The 23 and 37 are arbitrary numbers which are co-prime.

The benefit of the above over the XOR method is that if you have a type which has two values which are frequently the same, XORing those values will always give the same result (0) whereas the above will differentiate between them unless you're very unlucky.

As mentioned in the above snippet, you might also want to look at Joshua Bloch's book, Effective Java, which contains a nice treatment of the subject (the hashcode discussion applies to .NET as well).

Lezley

This is a very good answer and highlights some important points. however it is lacking an example. If you wish, please edit your answer to include my example (or something similar) and I will delete my answer. (+1, by the way). – Fao

Done - and wiki'ed the answer as a result. – Lezley

the link to 'this solution' is dead, here is the new link – Confabulate

Does this need to be in an unchecked block? – Valkyrie

@ja72: yes, it probably should be in an unchecked block. The default is unchecked, but a compiler option (or runtime environment setting?) can change that default. – Lezley

So it does not need, but it would be good for code clarity. – Valkyrie

Also would it work with ^ (xor) in place of + (add). Like 37*x ^ y .. – Valkyrie

Answer 2

Andrew has posted a good example for generating a better hash code, but also bear in mind that you shouldn't use hash codes as an equality check, since they are not guaranteed to be unique.

For a trivial example of why this is consider a double object. It has more possible values than an int so it is impossible to have a unique int for each double. Hashes are really just a first pass, used in situations like a dictionary when you need to find the key quickly, by first comparing hashes a large percentage of the possible keys can be ruled out and only the keys with matching hashes need to have the expense of a full equality check (or other collision resolution methods).

Impolite

Answer 3

Hashing always involves collisions and you have to deal with it (f.e., compare hash values and if they are equal, exactly compare the values inside the classes to be sure the classes are equal).

Using a simple XOR, you'll get many collisions. If you want less, use some mathematical functions that distribute values across different bits (bit shifts, multiplying with primes etc.).

Birdhouse

Answer 4

Read Overriding GetHashCode for mutable objects? C# and think about implementing IEquatable<T>

Ot

Answer 5

There are several better hash implementations. FNV hash for example.

Funereal

Answer 6

Out of curiosity since hashcodes are typically a bad idea for comparison, wouldn't it be better to just do the following code, or am I missing something?

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

Vanhomrigh

Yes, but if I had 50 properties I was trying to compare, this would get pretty ugly. I was hoping to just implement GetHashCode() and then leave Equals() nice and simple. It appears this might be a pipe dream. – Cruce

Answer 7

A quick generate and good distribution of hash

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

Clip