为什么 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特征的文档，

在实现 Hash 和 Eq 时，保持以下属性非常重要：

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

换句话说，如果两个键相等，那么它们的哈希值也必须相等。HashMap 和 HashSet 都依赖于这种行为。

无法保证这种行为，因为 的迭代顺序是不确定的，因此每当输入不同的数据时，即使它们包含相同的元素，HashMap数据也会以不同的顺序馈送到，从而破坏了 的契约并导致不良后果用于 a或时要发生的事情。HasherHashMapHashHashSetHashMap

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

请注意，这两种行为都与 Python 不同Dict，Python 按插入顺序迭代事物。