3 ms·

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

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

xyzzyz 7y ago
The hash table implementation (the data structure) is changed, but the hash function (the one which generates the hashes) is kept the same.
- Twirrim 7y 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?
  - steveklabnik 7y 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.
  - oconnor663 7y 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.
devit 7y ago
The hashtable implementation is taken from hashbrown but the default hash is still the same and not taken from hashbrown.
dathinab 7y 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.).

xyzzyz 7y ago

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

Twirrim 7y 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?
- steveklabnik 7y 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.
- oconnor663 7y 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.

devit 7y ago

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

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