如何在 HashSet 或 HashMap 中使用自定义哈希函数？

Question

由于 SipHasher 对于我的用例来说太慢，因此我尝试实现自定义哈希函数。我找到了一个示例，将其用作编译所有内容的基础。

我当前的代码如下所示：

use std::collections::hash_state::{DefaultState};
use std::collections::{HashMap, HashSet};
use std::default::Default;
use std::hash::{Hash, Hasher, SipHasher};
use std::marker;

pub struct FnvHasher(u64);

impl Default for FnvHasher {
    fn default() -> FnvHasher { FnvHasher(0xcbf29ce484222325) }
}

impl Hasher for FnvHasher {
    fn write(&mut self, bytes: &[u8]) {
        let FnvHasher(mut hash) = *self;
        for byte in bytes {
            hash = hash ^ (*byte as u64);
            hash = hash * 0x100000001b3;
        }
        *self = FnvHasher(hash);
    }
    fn finish(&self) -> u64 { self.0 }
}

fn main() {
    let mut set:HashSet<i64, DefaultState<FnvHasher>> = HashSet::with_hash_state(DefaultState::<FnvHasher>);
}

当我编译时，我收到以下错误消息：

$ rustc -V
rustc 1.0.0-nightly (522d09dfe 2015-02-19) (built 2015-02-19)

$ rustc hash.rs
hash.rs:26:86: 26:111 error: mismatched types:
 expected `std::collections::hash::state::DefaultState<FnvHasher>`,
    found `fn(core::marker::PhantomData<FnvHasher>) -> std::collections::hash::state::DefaultState<FnvHasher> {std::collections::hash::state::DefaultState}`
(expected struct `std::collections::hash::state::DefaultState`,
    found fn item) [E0308]
hash.rs:26         let mut set:HashSet<i64, DefaultState<FnvHasher>> = HashSet::with_hash_state(DefaultState::<FnvHasher>);
                                                                                                ^~~~~~~~~~~~~~~~~~~~~~~~~
error: aborting due to previous error

如何让上面的示例在 HashSet/HashMap 中编译或使用自定义哈希函数？

Answer 1

Rust 1.7稳定了自定义哈希器的使用。例如，您可以使用fnv板条箱FnvHasher中的

extern crate fnv;

use std::collections::HashMap;
use std::hash::BuildHasherDefault;
use fnv::FnvHasher;

type HashMapFnv<K, V> = HashMap<K, V, BuildHasherDefault<FnvHasher>>;

fn main() {
    let mut map = HashMapFnv::default();
    map.insert(1, "Hello");
    map.insert(2, ", world!");
    println!("{:?}", map);
}

Answer 2

看一下 的定义DefaultState：

\n\n

pub struct DefaultState<H>(marker::PhantomData<H>);\n

\n\n

你对待它就好像它以前一样：

\n\n

pub struct DefaultState<H>;\n

\n\n

此更改是最近发生的；现在必须明确使用通用参数。

\n\n

为此，您现在必须使用Default::default()，因为该字段是私有的，从而防止写入文字表达式。因此，DefaultState::<FnvHasher>变为Default::default().

\n\n

一旦你使用了\xe2\x80\x99 Default::default()，你不妨全力以赴并替换HashSet::with_hash_state(Default::default())为Default::default()：

\n\n

let mut set: HashSet<i64, DefaultState<FnvHasher>> = Default::default();\n

\n