Почему BTreeMap хешируется, а не HashMap?
Исходя из 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 меня удивляет.
Может ли кто-нибудь дать объяснение здесь?
Ответы 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 может быть выполнен, поэтому предоставляется реализация.
Обратите внимание, что оба эти поведения отличаются от Python Dict, который выполняет итерацию по порядку вставки.
Ок, понятно, спасибо. Я чуть было не спросил, почему тогда Python dicts не хэшируется (хешируемый объект в python должен соответствовать тем же критериям), но ваш комментарий к порядку вставки прояснил это. В Python, поскольку словари упорядочены по порядку вставки, у меня может быть 2 словаря с одинаковым содержимым, но с другим порядком итерации.
Это всего лишь предположение, но порядок хэширования элементов влияет на результаты, а
HashMapне имеет детерминированного порядка. Даже если у двухHashMapодинаковые элементы, порядок может быть разным.