Traps of hashing floats

6, Oct, 2018

A common way to compare two floats is something like:

float_cmp(float a, float b) { 
    return fabsf(a-b) < eps; 
}

and the common way of hashing these is something like:

unsigned float_hsh(float a, unsigned sz) {
    return (unsigned)(a * p) % sz; 
}
where p is some big prime. But there is non-trivial problem with these formulations when used together. The float_hsh has non-constant window in which two distinct but very close floating numbers will generate the same hash value. It is not bad at itself (just a little non-uniformity in hashing). But look at float_cmp. It will return true for range of floats - not single floats. This may result in two equal numbers with differnt hashes (and yes, it will happen, if you do some non-trivial algorithms with these numbers with hardly predictable rounding issues). This is a violation of one of the hashing invariants (that the same numbers will have same hash index). You may think:
unsigned float_hsh(float a, unsigned sz) { 
    return (unsigned)(roundto(a, eps) * p) % sz; 
}
will solve this. But apparently also not entirely. This because float_cmp() measures epsilon in relative space (starting at a and going to b), but float_hsh() has error correction in absolute space (starting at origin - 0). So float equality also must be appended:
float_cmp(float a, float b) { 
    return roundto(a, eps) - roundto(b, eps); 
}
This also may have some issues with precision (as it converts floating point number to a fixed one). But, this is another story…