为什么 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 中，我无法将 dict 放入集合中，因此 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 的迭代顺序是 non-deterministic，因此只要不同的 HashMap 被输入，即使它们包含相同的元素，也会破坏 Hash 的约定，并在 HashSet 或 HashMap.[=25= 中使用时导致不好的事情发生]

然而，BTreeMap 的全部要点在于它是一个有序映射，这意味着对它的迭代按排序顺序进行，这是完全确定的，这意味着 Hash 的契约可以是满意，所以提供了一个实现。

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

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

Why is BTreeMap hashable, and not HashMap?

rust

hashmap