How to write a hashcode generator for this class?

Question

I have a class which holds a position in three floats. I have overridden Equals like so:

return Math.Abs(this.X - that.X) < TOLERANCE
    && Math.Abs(this.Y - that.Y) < TOLERANCE
    && Math.Abs(this.Z - that.Z) < TOLERANCE;

This is all very well, but now I need to write a GetHashCode implementation for these vertices, and I'm stuck. simply taking the hashcode of the three values and xoring them together isn't good enough, because two objects with slightly different positions may be considered the same.

So, how can I build a GetHashCode implementation for this class which will always return the same value for instances which would be considered equal by the above method?

Answer 1

This "Equals" implementation doesn't satisfy the transitive property of being equal (that if X equals Y, and Y equals Z, then X equals Z).

Given that you've already got a non-conforming implementation of Equals, I wouldn't worry too much about your hashing code.

Answer 2

I recommend that you rethink your implementation of Equals. It violates the transitive property, and that's going to give you headaches down the road. See How to: Define Value Equality for a Type, and specifically this line:

if (x.Equals(y) && y.Equals(z)) returns true, then x.Equals(z) returns true. This is called the transitive property.

Answer 3

Is this possible? In your equality implementation, there's effectively a sliding window within which equality is considered true, however if you have to "bucketize" (or quantize) for a hash, then it's likely that two items that are "equal" might lie on either side of the hash "boundary".

Answer 4

There's only one way to satisfy the requirements of GetHashCode with an Equals like this.

Say you have these objects (the arrows indicate the limits of the tolerance, and I'm simplifying this to 1-D):

     a                c
<----|---->      <----|---->
        <----|---->
             b

By your implementation of Equals, we have:

a.Equals(b) == true
b.Equals(c) == true

a.Equals(c) == false

(This is the loss of transitivity mentioned...)

However, the requirements of GetHashCode are that Equals being true implies that the hash codes are the same. Thus, we have:

hash(a) = hash(b)
hash(b) = hash(c)

∴ hash(a) = hash(c)

By extension, we can cover any part of the 1-D space with this (imagine d, e, f, ...), and all the hashes will have to be the same!

int GetHashCode()
{
    return some_constant_integer;
}

I would say don't bother with .NET's GetHashCode. It doesn't make sense for your application. ;)

If you needed some form of hash for quick lookup for your data type, you should start looking at some kind of spatial index.