如何在Rust中使用带有f64的HashMap作为键？

Question

我想使用a HashMap<f64, f64>,用于将已知x和y的点的距离保存到另一个点.f64因为价值在这里无关紧要,重点应放在关键上.

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();

由于f64既不是Eq也不是Hash,只是PartialEq,f64不足以作为重点.我需要先保存距离,但也要稍后通过y访问距离.y的类型需要是浮点精度,但如果不起作用f64,我将使用i64带有已知指数的.

我通过使用自己的方法尝试了一些hacks struct Dimension(f64),然后Hash通过将float转换为a String然后对其进行哈希来实现.

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

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

这似乎非常糟糕,两个解决方案,我自己的struct或float作为带有base和exponent的整数似乎对于一个键来说非常复杂.

更新:我可以保证我的密钥永远不会是NaN,或者是无限的价值.此外,我不会计算我的密钥,只是迭代它们并使用它们.因此,已知错误应该没有错误0.1 + 0.2 ? 0.3. 如何在Vec of Floats上进行二进制搜索？并且这个问题的共同点是实现浮点数的总排序和相等,不同之处仅在于散列或迭代.

Answer 1

您可以将 拆分f64为整数部分和小数部分，并按以下方式将它们存储在结构中：

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

剩下的很简单：

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)));
}

编辑：正如 Veedrac 所说，更通用和有效的选择是将 解构f64为尾数-指数-符号三元组。可以执行此操作的函数在 中integer_decode()已弃用std，但可以在Rust GitHub 中轻松找到。

该integer_decode()函数可以定义如下：

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)
}

的定义Distance可以是：

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

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

此变体也更易于使用：

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)));
}

Answer 2

不幸的是，浮点类型相等是困难且违反直觉的：

fn main() {
    println!("{} {} {}", 0.1 + 0.2, 0.3, 0.1 + 0.2 == 0.3);
}

// Prints: 0.30000000000000004 0.3 false

因此散列也很困难，因为相等值的散列应该相等。

如果在你的情况下，你有一个足够小的范围来适应 a 中的数字，i64 并且你可以接受精度的损失，那么一个简单的解决方案是首先规范化，然后根据规范值定义 equal/hash ：

use std::cmp::Eq;

#[derive(Debug)]
struct Distance(f64);

impl Distance {
    fn canonicalize(&self) -> i64 {
        (self.0 * 1024.0 * 1024.0).round() as i64
    }
}

impl PartialEq for Distance {
    fn eq(&self, other: &Distance) -> bool {
        self.canonicalize() == other.canonicalize()
    }
}

impl Eq for Distance {}

fn main() {
    let d = Distance(0.1 + 0.2);
    let e = Distance(0.3);

    println!("{:?} {:?} {:?}", d, e, d == e);
}

// Prints: Distance(0.30000000000000004) Distance(0.3) true

Hash如下所示，从那时起您就可以用作Distance哈希映射中的键：

impl Hash for Distance {
    fn hash<H>(&self, state: &mut H) where H: Hasher {
        self.canonicalize().hash(state);
    }
}

fn main() {
    let d = Distance(0.1 + 0.2);
    let e = Distance(0.3);

    let mut m = HashMap::new();
    m.insert(d, "Hello");

    println!("{:?}", m.get(&e));
}

// Prints: Some("Hello")

警告：重申一下，此策略仅在以下情况下才有效：(a) 值的动态范围足够小，可以在 a i64（19 位）中捕获，并且 (b) 由于因子是静态的，动态范围提前已知。幸运的是，这适用于许多常见问题，但需要记录和测试......

Answer 3

您可以使用ordered_float板条箱来为您完成此操作。

Answer 4

除了阅读所有其他评论和答案之外，没有任何评论以了解您可能不想这样做的原因：

use std::{collections::HashMap, hash};

#[derive(Debug, Copy, Clone)]
struct DontUseThisUnlessYouUnderstandTheDangers(f64);

impl DontUseThisUnlessYouUnderstandTheDangers {
    fn key(&self) -> u64 {
        self.0.to_bits()
    }
}

impl hash::Hash for DontUseThisUnlessYouUnderstandTheDangers {
    fn hash<H>(&self, state: &mut H)
    where
        H: hash::Hasher,
    {
        self.key().hash(state)
    }
}

impl PartialEq for DontUseThisUnlessYouUnderstandTheDangers {
    fn eq(&self, other: &DontUseThisUnlessYouUnderstandTheDangers) -> bool {
        self.key() == other.key()
    }
}

impl Eq for DontUseThisUnlessYouUnderstandTheDangers {}

fn main() {
    let a = DontUseThisUnlessYouUnderstandTheDangers(0.1);
    let b = DontUseThisUnlessYouUnderstandTheDangers(0.2);
    let c = DontUseThisUnlessYouUnderstandTheDangers(0.3);

    let mut map = HashMap::new();
    map.insert(a, 1);
    map.insert(b, 2);

    println!("{:?}", map.get(&a));
    println!("{:?}", map.get(&b));
    println!("{:?}", map.get(&c));
}

基本上，如果您想将 af64视为一组没有意义的位，那么我们可以将它们视为知道如何进行散列和按位比较的等效大小的位包。

当1600 万个NaN值之一不等于另一个值时，请不要感到惊讶。