如何在Rust中创建自定义哈希函数

bjg7j2ky 于 11个月前发布在其他

关注(0)|答案(1)|浏览(116)

如何创建一个可以在HashMap和HashSet中使用的自定义哈希函数？我想使用Szudzik的配对函数，但我读过的所有文档都指出Hasher使用任意字节流。
_hash_瓦尔是我希望使用的哈希值
参考：https://en.wikipedia.org/wiki/Pairing_function#Other_pairing_functions

use std::hash::{Hash, Hasher};

#[derive(Copy, Clone)]
pub struct Position {
    pub x: i32,
    pub y: i32,
}

impl Position {
    // Constructor will pass in x and y
    pub fn new(x: i32, y: i32) -> Self {
        Self { x: x, y: y }
    }

}

impl PartialEq for Position {
    fn eq(&self, other: &Self) -> bool {
        self.x == other.x && self.y == other.y
    }
}

impl Eq for Position {}

impl Hash for Position {
    fn hash<H: Hasher>(&self, _state: &mut H) {
        let x: u64 = self.x.abs() as u64;
        let y: u64 = self.y.abs() as u64;
        let mut _hash_val: u64 = 0;

        /* szudziks function */
        if x >= y {
            _hash_val = x * x + x + y;
        } else {
            _hash_val = x + y * y;
        }
    }
}

字符串
我读到的所有文档都指出我需要实现std：：hash：：Hasher，但是the documentation指出：A trait for hashing an arbitrary stream of bytes.有没有一种方法可以创建一个不使用任意字节流的自定义哈希函数？
编辑：
在阅读了文档的第一行后，我没有再进一步看，因为我假设一个字节是8位，这就是它所能操作的。但是正如cdhowie指出的，这有点误导，因为你可以使用write_u64（）方法。
https://doc.rust-lang.org/std/hash/trait.Hasher.html#method.write_u64
使用这个方法修改上面的Hash实现：

impl Hash for Position {
    fn hash<H: Hasher>(&self, state: &mut H) {
        assert!(self.x >= 0);
        assert!(self.y >= 0);
    
        let x: u64 = self.x as u64;
        let y: u64 = self.y as u64;
    
        /* szudzik's pairing function */
        let hash_val: u64 = if x >= y {
            x * x + x + y
        } else {
            x + y * y
        };
    
        state.write_u64(hash_val);
    }
}

型

rust

来源：https://stackoverflow.com/questions/77588838/how-to-create-a-custom-hash-function-in-rust

1条答案

按热度按时间

ou6hu8tu1#

用于Rust哈希表集合的哈希是一个三步过程，由三个trait管理。
Hash trait是你想要散列的元素需要实现的。它所做的就是向散列器提供字节。你几乎完成了它;你只需要将值写入散列器。

fn hash<H: Hasher>(&self, state: &mut H) {
    let x = self.x.unsigned_abs() as u64;
    let y = self.y.unsigned_abs() as u64;

    /* szudziks function */
    let hash_val = if x >= y { x * x + x + y } else { x + y * y };
    state.write_u64(hash_val);
}

字符串
我已经把你的abs改成了unsigned_abs来避免溢出。你也应该决定如何处理乘法和加法中的溢出。
这个Hash impl适用于任何Hasher，所以你可以立即使用它，但是由于大多数Hasher类型不假设输入是均匀分布的（包括HashMap/HashSet的默认类型），它们将通过实际的哈希函数运行字节以获得最终的哈希。
如果你觉得你的值对于你的用例来说已经足够分布良好了，那么你可以做一个自定义的散列器，它不加修改地传递u64。如果你不能确保值是分布良好的，你会发现你的集合的性能很糟糕。

#[derive(Default, Clone, Copy)]
pub struct IdentityHash(u64);

impl Hasher for IdentityHash {
    fn finish(&self) -> u64 {
        self.0
    }
    
    fn write(&mut self, _bytes: &[u8]) {
        panic!("This hasher only takes u64");
    }

    fn write_u64(&mut self, i: u64) {
        self.0 = i;
    }
}

型
如果hasher用于不是单个u64的类型，根据您希望发生的情况，有许多方法可以做到这一点，但我已经做了一个最简单的例子。
最后一部分是BuildHasher，这是哈希表集合如何在使用之间重置散列器。在这种情况下，由于IdentityHash没有太多的状态，您可以在同一类型上实现它并让它复制自己。

impl BuildHasher for IdentityHash {
    type Hasher = Self;

    fn build_hasher(&self) -> Self::Hasher {
        *self
    }
}

型
现在您可以使用这些类型创建集合。

fn main() {
    let pos = Position::new(1, 2);
    let mut hasher = IdentityHash::default();
    pos.hash(&mut hasher);
    assert_eq!(hasher.finish(), 5);

    let mut set = std::collections::HashSet::with_hasher(IdentityHash::default());
    set.insert(Position::new(1, 2));
    assert!(set.contains(&Position::new(1, 2)));
}

型
Playground

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

我来回答

如何在Rust中创建自定义哈希函数

1条答案

相关问题

热门标签

最新问答