hashbrown
hashbrown copied to clipboard
rust-lang
Improve Readme comparison std and FNV
From the readme:
Since Rust 1.36, this is now the HashMap implementation for the Rust standard library. However you may still want to use this crate instead since it works in environments without std, such as embedded systems and kernels.
This paragraph implies that std is the same as hashbrown, but this omits that fact that std still uses SipHash and hashbrown uses AHash. Is this not a significant difference? (I'm asking since I don't fully understand these terms.)
Also, I can't find any guidance on choosing between hashbrown and FNV. Can we add this as well? Is FNV still generally the best choice when working with small keys? FNV is mentioned in the std docs so it seems warranted that this guidance should be available.
This paragraph implies that std is the same as hashbrown, but this omits that fact that std still uses SipHash and hashbrown uses AHash. Is this not a significant difference? (I'm asking since I don't fully understand these terms.)
Yes but the hash function can easily be changed using the S parameter on HashMap<K, V, S>.
Also, I can't find any guidance on choosing between hashbrown and FNV. Can we add this as well? Is FNV still generally the best choice when working with small keys? FNV is mentioned in the std docs so it seems warranted that this guidance should be available.
AHash or FxHash will be much faster for small keys than FNV or SipHash.
@camsteffen You can see my benchmarks of just the hasher here: https://github.com/tkaitchuck/aHash/blob/master/compare/readme.md#speed There is also some more qualitative comparison on that same page if you scroll up. FNV is only an alternative to aHash. The rest of HashBrown's code should perform the same regardless of which hasher is used.
I think I found your speed comparison after I posted this. It's very helpful, thanks. Also thanks for updating the rust std docs. 👍
Stumbled across this after some searching - I didn't realize that std::Collections::HashMap is literally a wrapper around HashBrown with a different default hasher. Knowing that helps clear some confusion up
https://github.com/rust-lang/rust/blob/2c3f284003d4bbedb9f0212c8f37c726124fa0ab/library/std/src/collections/hash/map.rs#L6 https://github.com/rust-lang/rust/blob/2c3f284003d4bbedb9f0212c8f37c726124fa0ab/library/std/Cargo.toml#L22
This should probably be clarified in the standard library docs for HashMap.