Skip to content

Rework HashMap internals and add RNG support

Yorick Peterse requested to merge rework-hashing into master

The internals of HashMap, and in particular the hashing logic, were broken. Internally the VM reused Rust's DefaultHasher type for hashing values. This type is mutable. When storing a HashMap in a constant, concurrent access to this HashMap could result in wrong hashes being produced, as all threads use the same DefaultHasher.

To solve this, Inko takes a similar approach as Rust: we provide a RandomState type, which can be used to create a DefaultHasher. A DefaultHasher now takes two keys as arguments, used for seeding the hasher. The RandomState type generates two keys randomly, similar to Rust. The hash seeds are generated by taking a thread-local randomly generated number, then incrementing it (wrapping around on overflow). This ensures that it is very unlikely for two different HashMaps to use the same seeds, making certain hash attacks [1] more difficult.

Random number generation is provided by the std::random module. This module provides methods for randomly generating integers, floats, and bytes. Integers and floats can also be generated in a given range, for example:

import std::random

random.integer_between(min: 0, max: 10)

[1]: https://github.com/rust-lang/rust/issues/36481 and https://internals.rust-lang.org/t/help-harden-hashmap-in-libstd/4138/18

Merge request reports