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

Question

我想使用一个 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();

由于既不是也不是，但只是，因此作为键值不足够。我需要先保存距离，然后通过y访问这些距离。y的类型需要具有浮点精度，但如果使用无法处理，则将使用已知指数的。

我尝试过一些hack，通过使用自己的，然后通过将浮点数转换为<字符串>再进行哈希。

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

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

对于一个仅仅是键的数据结构来说，我的自定义结构和将浮点数表示为基数和指数都显得非常复杂。

更新： 我可以保证我的键永远不会是NaN或无限大的值。另外，我不会计算我的键值，只会遍历它们并使用它们。因此，已知的0.1+0.2≠0.3误差不会出现问题。 如何在Vec中进行二分搜索浮点数？和这个问题共同实现了浮点数的全序和相等性，区别在于哈希或者遍历。

- pixunil

---

你真的需要按照精确距离获取对象吗？使用浮点数作为键和测试两个值是否相等一样都不是一个好主意（因为会发生舍入误差）。 - E net4

重复的问题：https://dev59.com/OV4c5IYBdhLWcg3wLXga - Shepmaster

可能存在 f64 没有实现 Eq 的问题，但我认为问题更深层次 => 即使你排除了 NaN，比较两个浮点数的相等性也会引起麻烦。 - Matthieu M.

你是否期望你的键会有重复的值？它们是否需要被哈希映射去重？ - Veedrac

Answer 1

在没有其他评论和答案的情况下，建议阅读所有其他评论和答案，以了解为什么您可能不想这样做。

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

基本上，如果你想将 f64 视为一组没有意义的二进制位，那么我们可以将它们视为相同大小的二进制位袋子，这些袋子知道如何进行哈希和按位比较。

当其中之一1600万个NaN值中出现不相等的情况时，请不要感到惊讶。

- Shepmaster

---

请注意，如果使用 NaN 产生的奇怪结果是一个问题，您可以在构造函数中过滤它们。 - Veedrac

Answer 2

您可以将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)));
}

- ljedrz

---

这似乎比无损（且更节省空间）的符号-指数-尾数三元组更糟糕。 - Veedrac

当 Distance(f64) 也像 f64 一样存在 0.3 不等于 0.1 + 0.2 的问题时，为什么还要使用“符号-指数-尾数”拆分版本，而不是简单地通过实现 Eq 和 Hash 来解决这个问题？ - John

我不确定；如果你尝试，你会得到 error: no method named assert_receiver_is_total_eq found for type f64 in the current scope in this expansion of #[derive(Eq)]. - ljedrz

@John MattieuM的回答涉及四舍五入和不精确性，并且需要对每个比较进行算术运算。相比之下，这个是无损的。 - Veedrac

@John f64 没有哈希实现的唯一原因是 NaN 不等于自身，因此不能具有哈希值。使用 Shepmaster 的解决方案而不是这个也可以（尽管那个破坏了 Hash 的契约，并且更难以保证安全），但我不明白为什么人们认为四舍五入会解决问题。没有对域进行分析的情况下进行四舍五入只会使问题变得更糟。 - Veedrac

Answer 3

你可以使用ordered_float crate来帮助你完成这个操作。

- optevo

Answer 4

不幸的是，浮点类型的相等性很难理解:

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

// Prints: 0.30000000000000004 0.3 false

因此，哈希也很难，因为相等值的哈希应该是相等的。

---

如果您的情况下，数字范围足够小，可以将数字适配到 i64 中，并且可以接受精度损失，那么一个简单的解决方案是先进行规范化，然后再根据规范化的值定义相等/哈希。

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) 值的动态范围足够小，可以被i64(19 位数字)捕获；(b) 动态范围已知，因为因子是静态的。幸运的是，这适用于许多常见问题，但需要记录和测试...

- Matthieu M.

---

最好将数值转换为f32，而不是乘以一个常数并强制转换为整型。因为在当前计算方案中，1e-12和2e-15都会映射到0，但在f32中它们是不同的值。此外，这样做可以解决精度问题，因为类型转换只是在比较时进行。 - John

@John：也许是，也许不是。这完全取决于你想要考虑什么是相等的。对于以米为单位的距离测量，“1e-12”就是1皮米：如果1皮米的差异对于任何类型的地理跟踪（例如）都很重要，我会非常惊讶。这确实是一个领域建模决策。如果您希望保留更多的精度，那么哈希映射查找就有缺陷，您将需要类似边界体积、KD树等的东西... - Matthieu M.

我不喜欢这个解决方案；它增加了不必要的不精确性，似乎也无法很好地映射到任何领域。如果这样舍入就足够了，那么一开始就不应该使用浮点数。 - Veedrac

@Veedrac 好的，这只是为了查找而完成的。所以我猜这取决于你想要什么，就像MatthieuM.所说的那样...（将1024*1024仅作为占位符表示感兴趣的范围。） - John

我不认为以下推理相关：如果"f32"加法没有产生精确的期望结果，则哈希应以任何方式受到影响。毕竟，并没有“法律”规定“x1 + x2 == x3”-> “x1.hash() + x2.hash() == x3.hash()”。如果舍入误差是应用程序的问题，那么请不要使用浮点数，但不要声明由于舍入而无法对浮点值进行哈希。使用bignums或rust在此部门提供的任何其他东西。这里唯一可接受的论据是“NaN”问题。 - BitTickler

@BitTickler：对浮点数进行哈希很容易，你可以将它们重新解释为整数并哈希整数。这满足了两个浮点数相等时它们的哈希值相等的要求（因为NaN不等于任何东西）。然而，这里提出的问题是，这种方案依赖于精确相等（按位相等），而浮点数本质上具有舍入误差，因此在容差阈值内是相等的。这就是哈希失败的地方：它无法处理这个容差阈值。 - Matthieu M.