Gfyuki

Let's say we have the following python class (the problem exists in java just the same with equals and hashCode)

class Temperature:

    def __init__(self, degrees):

        self.degrees = degrees

where degrees is the temperature in Kelvin as a float. Now, I would like to implement equality testing and hashing for Temperature in a way that

• compares floats up to an epsilon difference instead of direct equality testing,


• and honors the contract that a == b implies hash(a) == hash(b).

def __eq__(self, other):

    return abs(self.degrees - other.degrees) < EPSILON



def __hash__(self):

    return # What goes here?

The python documentation talks a bit about hashing numbers to ensure that hash(2) == hash(2.0) but this is not quite the same problem.

Am I even on the right track? And if so, what is the standard way to implement hashing in this situation?

Update: Now I understand that this type of equality testing for floats eliminates the transitivity of == and equals. But how does that go together with the "common knowledge" that floats should not be compared directly? If you implement an equality operator by comparing floats, static analysis tools will complain. Are they right to do so?

implement equality testing and hashing for Temperature in a way that compares floats up to an epsilon difference instead of direct equality testing,

Fuzzy equality violates the requirements that Java places on the equals method, namely transitivity, i.e. that if x == y and y == z, then x == z. But if you do an fuzzy equality with, for example, an epsilon of 0.1, then 0.1 == 0.2 and 0.2 == 0.3, but 0.1 == 0.3 does not hold.

While Python does not document such a requirement, still the implications of having a non-transitive equality make it a very bad idea; reasoning about such types is headache-inducing.

So I strongly recommend you don't do that.

Either provide exact equality and base your hash on that in the obvious way, and provide a separate method to do the fuzzy matching, or go with the equivalence class approach suggested by Kain. Though in the latter case, I recommend you fix your value to a representative member of the equivalence class in the constructor, and then go with simple exact equality and hashing for the rest; it's much easier to reason about the types this way.

(But if you do that, you might as well use a fixed point representation instead of floating point, i.e. you use an integer to count thousandths of a degree, or whatever precision you require.)

Good Luck

You are not going to be able to achieve that, without being stupid with hashes, or sacrificing the epsilon.

Example:

Assume that each point hashes to its own unique hash value.

As floating point numbers are sequential there will be up to k numbers prior to a given floating point value, and up to k numbers after a given floating point value which are within some epsilon of the given point.

1. 
   

   For each two points within epsilon of each other that do not share the same hash value.

   
   
   
   
   
   • Adjust the hashing scheme so that these two points hash to the same value.
   
   
   
   


2. Inducting for all such pairs the entire sequence of floating point numbers will collapse toward a single has value.

There are a few cases where this will not hold true:

• Positive/Negative Infinity


• NaN


• A few De-normalised ranges that may not be linkable to the main range for a given epsilon.


• perhaps a few other format specific instances

However >=99% of the floating point range will hash to a single value for any value of epsilon that includes at least one floating point value above or below some given floating point value.

Outcome

Either >= 99% entire floating point range hashes to a single value seriously comprimising the intent of a hash value (and any device/container relying on a fairly distributed low-collision hash).

Or the epsilon is such that only exact matches are permitted.

Granular

You could of course go for a granular approach instead.

Under this approach you define exact buckets down to a particular resolution. ie:

[0.001, 0.002)

[0.002, 0.003)

[0.003, 0.004)

...

[122.999, 123.000)

...

Each bucket has a unique hash, and any floating point within the bucket compares equal to any other float in the same bucket.

Unfortunately it is still possible for two floats to be epsilon distance away, and have two separate hashes.