How to get the hash which would be used for a value in a BTreeMap

Question

I'm currently using BTreeMap because I need the stable ordering.

Is there a Rust Map structure which would allow me to tentatively add a new key/value to an ordered Map and see what the hash would be?

Currently I have to clone the whole BTreeMap, add the key/value, take the hash and drop the clone. This seems very wasteful.

I changed the title, mainly to change the vague "map" into the specific BTreeMap. Some map types provide a method to query the hash_builder so the answer wouldn't be the same for HashMap for example. — Denys Séguret, May 19 '21 at 06:14
If different insertion orders would yield different hashes, then you just need to update the current hash with a new digest. If insertion order shouldn't matter then it's the same thing but you have to make sure your hash update function is *commutative*. — kmdreko, May 19 '21 at 06:23
A problem with this question is it looks like a XY question. The reason why you'd want to see the hash isn't clear and might be based on false premises. — Denys Séguret, May 19 '21 at 06:25
The question is very confusing, BTreeMap is not hash-based, what hash are you talking about? For a `HashMap`, you can [get a reference to the map's `BuildHasher`](https://doc.rust-lang.org/std/collections/hash_map/struct.HashMap.html#method.hasher), from that you can create a `Hasher` instance, then `hash` your key using that hasher. Not sure what you'd expect *that* to tell you either tho. — Masklinn, May 19 '21 at 06:57

score 3 · Accepted Answer · edited May 19 '21 at 07:54

Assuming you are talking about the hash of the whole tree as returned by its Hash::hash method, then you can see that it is implemented like this:

fn hash<H: Hasher>(&self, state: &mut H) {
    for elt in self {
        elt.hash(state);
    }
}

which can be trivially adapted to insert an element virtually:

fn hash_with_extra<H: Hasher>(map: &BTreeMap<i32, i32>, state: &mut H, extra: &(i32, i32)) {
    let mut it = map.iter();
    let mut done = false;
    while let Some (elt) = it.next() {
        if extra.0 == elt.0 {
            extra.hash (state);
            done = true;
            break;
        } else if extra.0 < elt.0 {
            extra.hash (state);
            elt.hash (state);
            done = true;
            break;
        } else {
            elt.hash (state);
        }
    }
    if done {
        while let Some (elt) = it.next() { elt.hash (state); }
    } else {
        extra.hash (state);
    }
}

Or using itertools::merge and std::iter::once:

fn hash_with_extra<H: Hasher>(map: &BTreeMap<i32, i32>, state: &mut H, extra: &(i32, i32)) {
    for elt in merge (map.iter(), once (extra)) {
        elt.hash (state);
    }
}

@kmdreko thanks, added an example with `merge()` – Jmb May 19 '21 at 07:15 — Jmb, May 19 '21 at 07:15

How to get the hash which would be used for a value in a BTreeMap

1 Answers1