Module hash

Stable wrappers around the stdlib Hash collections.

The stdlib Hash collections (i.e., std::collections::HashMap and std::collections::HashSet) don’t guarantee a stable iteration order. That is, the order in which elements are returned by methods like iter or keys, or in which elements are visited by methods like retain, is undefined and can differ between program executions. This property leads to non-determinism, which in turn can be the cause of bugs in logic that relies on deterministic execution.

Since bugs caused by unstable iteration order are hard to spot, and it is not always easy to determine which parts of our code require determinism, we resort to banning the use of the stdlib Hash collections in general. Alternatives are available:

1. In most cases, you can simply switch to using the equivalent BTree collection type (i.e., std::collections::BTreeMap or std::collections::BTreeSet) as a drop-in replacement. The BTree collections guarantee a stable iteration order, based on the Ord relation.
2. If the types you want to store don’t (and shouldn’t) implement Ord, or if profiling reveals that the BTree collections are not suitable, use the wrappers provided in this module instead.

The Hash collection wrappers provided in this module only re-export methods that don’t expose iteration order, and are therefore safe to use in code that relies on determinism.

There are cases where the above mentioned alternatives are not sufficient, for example, if a third-party API requires you to pass a HashMap value. In this case, you can disable the clippy lint for the affected piece of code. Note that the onus is on you then to verify that doing so is sound and does not introduce bugs.

Structs

HashMap

A wrapper around std::collections::HashMap that hides methods that expose unstable iteration order.

HashSet

A wrapper around std::collections::HashSet that hides methods that expose unstable iteration order.