Why is BTreeMap hashable, and not HashMap?

Question

Coming from Python here.

I'm wondering why a BTreeMap is hashable. I'm not surprised a Hashmap isn't, but I don't understand why the BTreeMap is.

For example, I can do that:

let mut seen_comb: HashSet<BTreeMap<u8, u8>> = HashSet::new();
seen_comb.insert(BTreeMap::new());

But I can't do that:

let mut seen: HashSet<HashMap<u8, u8>> = HashSet::new();
seen.insert(HashMap::new());

Because I'm getting:

error[E0599]: the method `insert` exists for struct `HashSet<HashMap<u8, u8>>`, but its trait bounds were not satisfied
   --> src/main.rs:14:10
    |
14  |     seen.insert(HashMap::new());
    |          ^^^^^^ method cannot be called on `HashSet<HashMap<u8, u8>>` due to unsatisfied trait bounds
    |
   ::: /home/djipey/.rustup/toolchains/stable-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/collections/hash/map.rs:209:1
    |
209 | pub struct HashMap<K, V, S = RandomState> {
    | ----------------------------------------- doesn't satisfy `HashMap<u8, u8>: Hash`
    |
    = note: the following trait bounds were not satisfied:
            `HashMap<u8, u8>: Hash`

In Python, I can't put a dict inside a set, so the BTreeMap behaviour is surprising to me.

Could someone provide an explanation here?

Answer 1

The reason is that BTreeMap has a deterministic iteration order and HashMap does not. To quote the docs from the Hash trait,

When implementing both Hash and Eq, it is important that the following property holds:

k1 == k2 -> hash(k1) == hash(k2)

In other words, if two keys are equal, their hashes must also be equal. HashMap and HashSet both rely on this behavior.

There is no way to guarantee this behavior since the iteration order of HashMap is non-deterministic, so data would be fed to the Hasher in a different order whenever a different HashMap is inputted, even if they contain the same elements, breaking the contract of Hash and causing bad things to happen when used in a HashSet or HashMap.

However, the entire point of the BTreeMap is that it is an ordered map, meaning iteration over it occurs in sorted order, which is fully deterministic, meaning the contract of Hash can be satisfied, so an implementation is provided.

Note that both of these behaviors are different than Python's Dict, which iterates over things in order of insertion.