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

问题描述 投票：0回答：5

我想使用 

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
。

我尝试了一些技巧，使用我自己的

struct Dimension(f64)
，然后通过将浮点数转换为
Hash
然后对其进行散列来实现
String
。

#[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 进行二分查找？ 这个问题的共同点是实现浮点数的全序和相等，区别仅在于散列或迭代。

floating-point hashmap rust
5个回答
16
投票

您可以将 

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)));
}
15
投票

除此之外没有任何评论阅读所有其他评论和答案以了解为什么您可能不想这样做：

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
值之一不等于另一个值时，请不要感到惊讶。

6
投票
不幸的是，浮点类型相等是

困难且违反直觉的：

fn main() { println!("{} {} {}", 0.1 + 0.2, 0.3, 0.1 + 0.2 == 0.3); } // Prints: 0.30000000000000004 0.3 false
因此散列也很困难，因为相等值的散列应该是相等的。

在您的情况下，如果您的范围足够小，可以将您的数字放入

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) 值的动态范围足够小，可以在 i64

（19 位）中捕获，并且 (b) 动态范围提前已知为因子是静态的。幸运的是，这适用于许多常见问题，但需要记录和测试......

6
投票
您可以使用

ordered_float 板条箱来为您完成此操作。

0
投票
对@Veedrac 和@ljedraz 已经说过的内容进行了很小的补充

有

rust_decimal crate 提供 struct Decimal

，这是一个
Copy
（因此创建许多副本是高效的）。

添加到

Cargo.toml

后：

[dependencies] rust_decimal = "1.33" rust_decimal_macros = "1.33" 
你的
DimensionKey
可能会变成这样：


#[derive(Debug, Eq, Hash, PartialEq, Copy, Clone)]
pub struct DimensionKey {
    pub value: Decimal
}

impl DimensionKey {
    pub fn from_f64(raw: f64) -> Option<DimensionKey> {
        let value = Decimal::from_f64(raw)?;
        Some(DimensionKey { value })
    }
}

    



      

      
    

  

  

    
最新问题


  





  

    © www.soinside.com 2019 - 2024. All rights reserved.