IEquatable within a tolerance, how to implement GetHashCode()

Question

I have a Point3d struct which implements IEquatable<Point3d> in the following manner:

public override bool Equals(object obj) {
    return obj is Point3d p && Equals(p);
}

public bool Equals(Point3d other) {
    return Equals(other, Tolerance.ToleranceDecimal);
}

public bool Equals(Point3d other, double tolerance) {
    if (tolerance < 0) throw new ArgumentOutOfRangeException(nameof(tolerance), tolerance, "Expected a tolerance greater than or equal to 0");
    return Math.Abs(X - other.X) <= tolerance && Math.Abs(Y - other.Y) <= tolerance && Math.Abs(Z - other.Z) <= tolerance;
}

public override int GetHashCode() {
    var hash = 17;
    hash = hash * 23 + X.GetHashCode();
    hash = hash * 23 + Y.GetHashCode();
    hash = hash * 23 + Z.GetHashCode();
    return hash;
}

public static bool operator ==(Point3d firstPoint, Point3d secondPoint) {
    return firstPoint.Equals(secondPoint);
}

public static bool operator !=(Point3d firstPoint, Point3d secondPoint) {
    return !(firstPoint == secondPoint);
}

This is already heavily used within an application with the expectation that checking equality between two points allows for a tolerance (which is necessary for the implementation to work correctly).

If has come to my attention that the Equals and GetHashCode methods are not consistent, and indeed it is not possible to write GetHashCode in a form that would produce good and consistent results. This issue is particularly problematic in situations where a Linq query is used, such as points.Distinct() as the resulting points may be considered Equal if comparing directly, such as points[0] == points[1]

Personally I believe the best option would be to change Equals as follows, such that it's behaviour is consistent with GetHashCode:

public bool Equals(Point3d other) {
    return Equals(other, 0);
}

However, as this is already heavily utilised within an application this would be a significant breaking change. I believe it is the wrong thing to do, but I'm considering changing GetHashCode to:

public override int GetHashCode() {
    return 0;
}

My understanding is that the above would force the Equals method to be utilised which would result in a performance hit, but also allow for points within a tolerance to be considered equal within Linq queries. I would like to know if this opens me up to any other potential pitfalls.

I'm unsure as to what other avenues may be available to me, so am very much looking for advice as to the best approach to resolve this issue.

Thanks in advance!

Answer 1

The bitter truth is that you can't implement correct Equals with arbitrary tolerance. Equals (see https://msdn.microsoft.com/en-us/library/336aedhh(v=vs.100).aspx for details) must be transitive i.e. (x.Equals(y) && y.Equals(z)) returns true if and only if x.Equals(z) returns true.

And here we can create a counter example for given Tolerance.ToleranceDecimal:

 Point3d x = new Point3d(-Tolerance.ToleranceDecimal * 2.0 / 3.0, 0, 0);
 Point3d y = new Point3d(0, 0, 0);
 Point3d z = new Point3d(Tolerance.ToleranceDecimal * 2.0 / 3.0, 0, 0);

As you can see

 x.Equals(y) == true
 y.Equals(z) == true

But

 x.Equals(z) == false

Since Equals implementation is incorrect we can't create corresponding GetHashCode, except degenerated (and useless)

 public override int GetHashCode() {
   return 0;
 }

because GetHashCode must return the same value for x and y if x.Equals(y) == true. In our case: let x < y and y = x + N * tolerance

 x equals to 
 x + tolerance / 2.0 equals to
 x + tolerance / 2.0 * 2 equals to
 x + tolerance / 2.0 * 3 equals to
 ...
 x + tolerance / 2.0 * 2 * N equals to
 y

which means that for any arbitrary x and y and non-zero tolerance GetHashCode must return the same value for any argument.