floating point - How can I use a HashMap with f64 as key in Rust?

Question

I want to use a HashMap<f64, f64>, for saving the distances of a point with known x and key y to another point. f64 as value shouldn't matter here, the focus should be on key.

let mut map = HashMap<f64, f64>::new();
map.insert(0.4, f64::hypot(4.2, 50.0));
map.insert(1.8, f64::hypot(2.6, 50.0));
...
let a = map.get(&0.4).unwrap();

As f64 is neither Eq nor Hash, but only PartialEq, f64 is not sufficient as a key. I need to save the distances first, but also access the distances later by y. The type of y needs to be floating point precision, but if doesn't work with f64, I'll use an i64 with an known exponent.

I tried some hacks by using my own struct Dimension(f64) and then implementing Hash by converting the float into a String and then hashing it.

#[derive(PartialEq, Eq)]
struct DimensionKey(f64);

impl Hash for DimensionKey {
    fn hash<H: Hasher>(&self, state: &mut H) {
        format!("{}", self.0).hash(state);
    }
}

It seems very bad and both solutions, my own struct or float as integers with base and exponent seem to be pretty complicated for just a key.

Update: I can guarantee that my key never will be NaN, or an infinite value. Also, I won't calculate my keys, only iterating over them and using them. So there should no error with the known error with 0.1 + 0.2 ≠ 0.3. How to do a binary search on a Vec of floats? and this question have in common to implement total ordering and equality for a floating number, the difference lies only in the hashing or iterating.

Answer 1

You could split the f64 into the integral and fractional part and store them in a struct in the following manner:

#[derive(Hash, Eq, PartialEq)]
struct Distance {
    integral: u64,
    fractional: u64
}

The rest is straightforward:

use std::collections::HashMap;

#[derive(Hash, Eq, PartialEq)]
struct Distance {
    integral: u64,
    fractional: u64
}

impl Distance {
    fn new(i: u64, f: u64) -> Distance {
        Distance {
            integral: i,
            fractional: f
        }
    }
}

fn main() {
    let mut map: HashMap<Distance, f64> = HashMap::new();

    map.insert(Distance::new(0, 4), f64::hypot(4.2, 50.0));
    map.insert(Distance::new(1, 8), f64::hypot(2.6, 50.0));

    assert_eq!(map.get(&Distance::new(0, 4)), Some(&f64::hypot(4.2, 50.0)));
}

Edit: As Veedrac said, a more general and efficient option would be to deconstruct the f64 into a mantissa-exponent-sign triplet. The function that can do this, integer_decode(), is deprecated in std, but it can be easily found in Rust GitHub.

The integer_decode() function can be defined as follows:

use std::mem;

fn integer_decode(val: f64) -> (u64, i16, i8) {
    let bits: u64 = unsafe { mem::transmute(val) };
    let sign: i8 = if bits >> 63 == 0 { 1 } else { -1 };
    let mut exponent: i16 = ((bits >> 52) & 0x7ff) as i16;
    let mantissa = if exponent == 0 {
        (bits & 0xfffffffffffff) << 1
    } else {
        (bits & 0xfffffffffffff) | 0x10000000000000
    };

    exponent -= 1023 + 52;
    (mantissa, exponent, sign)
}

The definition of Distance could then be:

#[derive(Hash, Eq, PartialEq)]
struct Distance((u64, i16, i8));

impl Distance {
    fn new(val: f64) -> Distance {
        Distance(integer_decode(val))
    }
}

This variant is also easier to use:

fn main() {
    let mut map: HashMap<Distance, f64> = HashMap::new();

    map.insert(Distance::new(0.4), f64::hypot(4.2, 50.0));
    map.insert(Distance::new(1.8), f64::hypot(2.6, 50.0));

    assert_eq!(map.get(&Distance::new(0.4)), Some(&f64::hypot(4.2, 50.0)));
}