Author Topic: Creating a Hash Code for a Point3d based on Tolerance  (Read 1446 times)

0 Members and 1 Guest are viewing this topic.

zoltan

  • Newt
  • Posts: 188
Creating a Hash Code for a Point3d based on Tolerance
« on: November 30, 2012, 12:12:39 PM »
I have created an IEqualityComparer<Point3d> to allow me to use the Geometry.Point3d structure in dictionaries and hashtables and allow the equality to be determined by a Tolerance value.

I need to come up with a good, fast, and reliable way to get the Hash Code of the Point3d with respect to the tolerance.  The Point3d's GetHashCode() method only returns the base ValueType.GetHashCode(), so it may not even be a good implementation given what the docs say here:

Quote
The GetHashCode method applies to types derived from ValueType. One or more fields of the derived type is used to calculate the return value. If you call the derived type's GetHashCode method, the return value is not likely to be suitable for use as a key in a hash table. Additionally, if the value of one or more of those fields changes, the return value might become unsuitable for use as a key in a hash table. In either case, consider writing your own implementation of the GetHashCode method that more closely represents the concept of a hash code for the type.

Here is what I have come up with:
Code - C#: [Select]
  1. internal class Point3dEqualityComparer : IEqualityComparer<Point3d>
  2.     {
  3.         private Tolerance tolerance;
  4.  
  5.         public Point3dEqualityComparer()
  6.         {
  7.             this.tolerance = new Tolerance(1e-6, 1e-6);
  8.         }
  9.  
  10.         public Point3dEqualityComparer(Tolerance tolerance)
  11.         {
  12.             this.tolerance = tolerance;
  13.         }
  14.  
  15.         public bool Equals(Point3d x, Point3d y)
  16.         {
  17.             return x.IsEqualTo(y, this.tolerance);
  18.         }
  19.  
  20.         public int GetHashCode(Point3d point)
  21.         {
  22.             return (int)(point.X / this.tolerance.EqualPoint) ^
  23.                    (int)(point.Y / this.tolerance.EqualPoint) ^
  24.                    (int)(point.Z / this.tolerance.EqualPoint);
  25.         }
  26.     }
  27.  

I think this might be ok, but I'm not sure if it is the best way.

The requirements for a good Hash Code, as stated in the docs are as follows:
Quote
A hash function must have the following properties:
  • If two objects compare as equal, the GetHashCode method for each object must return the same value. However, if two objects do not compare as equal, the GetHashCode methods for the two object do not have to return different values.
  • The GetHashCode method for an object must consistently return the same hash code as long as there is no modification to the object state that determines the return value of the object's Equals method. Note that this is true only for the current execution of an application, and that a different hash code can be returned if the application is run again.
  • For the best performance, a hash function must generate a random distribution for all input.

Does anyone have any good ideas?