rust-intmap

针对u64键的特殊化HashMap

可能缺少一些功能，但现在可以删除、添加、获取和清除。

请注意，没有针对DoS攻击的努力。

与标准HashMap的性能比较

test tests::u64_get_built_in    ... bench:      22,320 ns/iter (+/- 446)
test tests::u64_get_intmap      ... bench:       2,959 ns/iter (+/- 148)
test tests::u64_insert_built_in ... bench:      27,666 ns/iter (+/- 1,230)
test tests::u64_insert_intmap   ... bench:      14,047 ns/iter (+/- 1,461)

重大变更

2.0.0 - 将 insert 的行为更改为与 std::HashMap 匹配。旧的行为被重命名为 insert_checked。

如何使用

简单示例。

extern crate intmap;

use intmap::IntMap;

let mut map = IntMap::new();

for i in 0..20_000 {
    map.insert(i, format!("item: {:?}", i));
}

它为什么会这么快？

我使用了一个针对u64的特殊化哈希函数，它将键与u64的最大素数相乘。通过保持内部缓存为2的幂，可以避免昂贵的模运算符，如http://stackoverflow.com/questions/6670715/mod-of-power-2-on-bitwise-operators所述。

#[inline]
fn hash_u64(seed: u64) -> u64 {
    let a = 11400714819323198549u64;
    let val = a.wrapping_mul(seed);
    val
}