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.

Answer 1

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);
    }
}