Hacker News new | ask | show | jobs
by thinkpad20 2545 days ago
> In Rust 1.36.0, the HashMap<K, V> implementation has been replaced with the one in the hashbrown crate which is based on the SwissTable design. While the interface is the same, the HashMap<K, V> implementation is now faster on average and has lower memory overhead. Note that unlike the hashbrown crate, the implementation in std still defaults to the SipHash 1-3 hashing algorithm.

The wording here confuses me. They say they took the implementation from hashbrown, but then finish by saying that the implementation is different. What am I missing?
3 comments
dathinab 2545 days ago
HashMap implementation and the hasher used in it are not the same. You can use the std hash map with any hash implementing Hash, and I think you can do so with hashbrown, too. The different is what hasher is used by default if you don't explicitly specify one.

Hasher => Takes the key and turns it into a hash (in this case a 64bit hash).

HashMap => Takes (key, value) pairs + a hasher and then does "magic" to get a fast lookup based on key+hasher.

The "magic" part is what changes. (which include thinks like which datastructures are used to store keys/values, how deletion is handled, how hash collisions are handled, how the given hash is used to lookup keys, etc.).

link
xyzzyz 2545 days ago
The hash table implementation (the data structure) is changed, but the hash function (the one which generates the hashes) is kept the same.
link
Twirrim 2545 days ago
Maybe I misunderstood the speed complaints about HashMap in Rust. I thought it was the hash function that was the slow bit? What is the anticipated improvements from using SwissTable?
link
steveklabnik 2545 days ago
We do choose a hash function not designed for speed by default, but that doesn’t mean that the implementation of the table can’t be improved. This is effectively the third re-write of it.
link
oconnor663 2544 days ago
I think the bottleneck depends on the size of your table and the size of your keys. A large table with small keys will bottleneck on memory IO, but a small table with large keys will bottleneck on hashing the keys. But I definitely haven't benchmarked any of this.
link
devit 2545 days ago
The hashtable implementation is taken from hashbrown but the default hash is still the same and not taken from hashbrown.
link