rust - 为什么 BTreeMap 是可散列的，而不是 HashMap？

Question

此处来自 Python。

我想知道为什么 BTreeMap 是可散列的。我并不惊讶 Hashmap 不是，但我不明白为什么 BTreeMap 是。

例如，我可以这样做:

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

但我不能那样做:

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

因为我得到:

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`

在 Python 中，我不能将字典放入集合中，因此 BTreeMap 的行为令我感到惊讶。

有人可以在这里提供解释吗？

Answer 1

原因是BTreeMap有一个确定的迭代顺序而HashMap没有。引用 Hash 中的文档特质，

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.

没有办法保证这种行为，因为 HashMap 的迭代顺序是不确定的，所以数据将以不同的顺序提供给 Hasher输入不同的 HashMap，即使它们包含相同的元素，也会破坏 Hash 的约定，并在 HashSet 中使用时导致错误的事情发生或 HashMap。

但是，BTreeMap 的全部要点在于它是一个有序映射，这意味着对它的迭代按排序顺序发生，这是完全确定的，这意味着 Hash 的契约code> 可以满足，所以提供一个实现。

请注意，这两种行为都不同于 Python 的 Dict，后者按插入顺序遍历内容。