13 releases (3 stable)
2.0.0 | Jul 17, 2022 |
---|---|
1.1.0 | Jun 11, 2022 |
0.8.0 | Jun 9, 2022 |
0.7.1 | Dec 1, 2021 |
0.2.1 | Dec 13, 2016 |
#222 in Data structures
45,128 downloads per month
Used in 33 crates
(18 directly)
26KB
515 lines
rust-intmap
Specialized hashmap for u64 keys
Might be missing some functionality but you can remove, add, get and clear for now.
Be aware that no effort is made against DoS attacks.
Performace compared to the standard 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)
Breaking Changes
2.0.0 - Changed behavior of insert
to match std::HashMap. The old behavior is renamed to insert_checked
.
How to use
Simple example.
extern crate intmap;
use intmap::IntMap;
let mut map = IntMap::new();
for i in 0..20_000 {
map.insert(i, format!("item: {:?}", i));
}
How can it be so much faster?
I use a specialized hash function for u64 it multiplies the key with the largest prime for u64. By keeping the internal cache a power 2 you can avoid the expensive modulus operator as per 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
}
Dependencies
~165KB