Hacker News Reader

Comment by thinkpad20 | Hacker News Reader

> 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?

View on HN

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.).

The hash table implementation (the data structure) is changed, but the hash function (the one which generates the hashes) is kept the same.

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?

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.

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.

The hashtable implementation is taken from hashbrown but the default hash is still the same and not taken from hashbrown.

Reply on news.ycombinator.com