Timeline for How to implement float hashing with approximate equality
Current License: CC BY-SA 4.0
6 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 30, 2019 at 23:50 | comment | added | Kain0_0 | @CarstenS Yes, my statement that 99% of the range hashes to a single hash does not actually cover the whole float range. There are many high range values who are separated by more than epsilon that will hash to their own unique buckets. | |
| Apr 30, 2019 at 9:43 | comment | added | Carsten S | While you are right in spirit, not everything will collapse. With a fixed small epsilon, most numbers will only equal themselves. Of course, for those the epsilon will be useless, so again, in spirit you are correct. | |
| Apr 29, 2019 at 15:26 | comment | added | Doc Brown | The bucket approach can be modified by checking not only the bucket with the exact hash key, but also the two neighboured buckets (or at least one of them) for their content as well. That elimininates the problem of those edge cases for the cost of increasing the running time by a factor of at most two (when implemented correctly). However, it does not change the general running time order. | |
| Apr 29, 2019 at 8:59 | comment | added | JF Meier | @DocBrown The "not possible" part is correct. If epsilon based equality should imply that the hash codes are equal, then you automatically have all hash codes equal, so the hash function is not useful anymore. The buckets approach can be fruitful, but you will have numbers with different hash codes that are arbitrarily close to each other. | |
| Apr 29, 2019 at 6:35 | comment | added | Neil | I agree that the granular approach here would probably be best, if that fits OP's requirements. Though I'm afraid OP has like +/- 0.1% type requirements, meaning it can't be granular. | |
| Apr 29, 2019 at 2:13 | history | answered | Kain0_0 | CC BY-SA 4.0 |