此处来自 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 的行为令我感到惊讶。
有人可以在这里提供解释吗?
最佳答案
原因是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
,后者按插入顺序遍历内容。
关于rust - 为什么 BTreeMap 是可散列的,而不是 HashMap?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/71532357/