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

xnifntxz 于 5个月前发布在其他

关注(0)|答案(5)|浏览(69)

我想使用HashMap<f64, f64>，用于保存一个已知x和key y的点到另一个点的距离。f64作为值在这里不重要，重点应该是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();

字符串
由于f64既不是Eq也不是Hash，而只是PartialEq，所以f64不足以作为密钥。我需要先保存距离，但稍后还要通过y访问距离。y的类型需要是浮点精度，但如果不适用于f64，我将使用具有已知指数的i64。
我尝试了一些技巧，使用我自己的struct Dimension(f64)，然后通过将浮点数转换为String并对其进行哈希来实现Hash。

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

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

型
这似乎非常糟糕，两种解决方案，我自己的结构或浮点数作为整数与基地和指数似乎是相当复杂的只是一个键。
更新：我可以保证我的key永远不会是NaN，或者是一个无穷大的值。而且，我不会计算我的key，只会迭代它们并使用它们。所以0.1 + 0.2 ≠ 0.3 . How to do a binary search on a Vec of floats?的已知错误应该没有错误，这个问题与实现浮点数的全排序和相等是一样的，区别只在于哈希或迭代。

rust

来源：https://stackoverflow.com/questions/39638363/how-can-i-use-a-hashmap-with-f64-as-key-in-rust

5条答案

按热度按时间

am46iovg1#

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

型

赞(0）回复(0）举报 6个月前

pengsaosao2#

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

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当作一组没有意义的比特，那么，我们可以把它们当作一个大小相等的比特包，知道如何进行哈希和逐位比较。
不要惊讶，当其中一个16 million NaN values doesn't equal another one。

赞(0）回复(0）举报 6个月前

ltqd579y3#

不幸的是，浮点类型的相等性是hard and counter-intuitive：

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作为哈希Map中的键：

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）动态范围事先已知，因为因子是静态的。幸运的是，这适用于许多常见问题，但它需要记录和测试。

赞(0）回复(0）举报 6个月前

pengsaosao4#

您可以使用ordered_float crate来完成此操作。

赞(0）回复(0）举报 6个月前

uqzxnwby5#

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

型

赞(0）回复(0）举报 6个月前

我来回答

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

5条答案

相关问题

热门标签

最新问答