Borrow Trait is enough for HashMap?

help
1

That is how HashMap::get declared:

pub fn get<Q>(&self, k: &Q) -> Option<&V>
where
    K: Borrow<Q>,
    Q: Hash + Eq + ?Sized,

The Borrow trait document says

In particular Eq , Ord and Hash must be equivalent for borrowed and owned values: x.borrow() == y.borrow() should give the same result as x == y .

Well, I think that is not enough for HashMap.

Does not it need require, for example, Hash(x.borrow()) == Hash(y)?

2

Yes, I believe you are correct!

And in fact that requirement is documented for HashMap::get:

The key may be any borrowed form of the map’s key type, but Hash and Eq on the borrowed form must match those for the key type.

I think the documentation for Borrow could be more clear. It does say the same thing:

In particular Eq, Ord and Hash must be equivalent for borrowed and owned values

But it only gives a formula for Eq, not for Ord or Hash:

x.borrow() == y.borrow() should give the same result as x == y

This is a little misleading and would be more clear if it gave formulas for Ord and Hash as well.

3

Example of it not working for HashSet: Rust Playground

use std::collections::HashSet;

#[derive(Debug, Eq, PartialEq)]
struct BadHash(i32);

use std::hash::Hash;
impl Hash for BadHash {
    fn hash<H: std::hash::Hasher>(&self, state: &mut H) {
        // Hash is negated
        (-self.0).hash(state);
    }
}

use std::borrow::Borrow;
impl Borrow<i32> for BadHash {
    fn borrow(&self) -> &i32 {
        &self.0
    }
}

fn main() {
    let mut set = HashSet::new();
    set.insert(BadHash(5));
    dbg!(set.contains(&5)); // false
}
4

I mis-read the get document.
I will prefer the get is unsafe though

Is it better

x.borrow() == y.borrow() should give the same result as x == y

to be

x.borrow() == y.borrow() should give the same result as x == y && x.borrow() == y?

5

I think you’re misinterpreting what can merely be an example of the kind of equivalencies that “Eq , Ord and Hash must be equivalent for borrowed and owned values” is supposed to imply, with the whole deal.

A more complete picture would, besides the already stated

  • (x == y) == (x.borrow() == y.borrow()),

also need to list

  • x.cmp(&y) == x.borrow().cmp(y.borrow()),
  • x.hash(&mut hasher) makes the same sequence of calls to hasher as x.borrow().hash(&mut hasher).

And furthermore it should probably need to qualify these conditions each by something like “if Self and Borrowed implements [Eq/Hash/Ord] correctly” (which is supposed to mean both “if it implements the trait at all”, otherwise there’s no restriction, and furthermore doesn’t blame consequences of logic errors from bad impls of Ord/Eq/Hash on the Borrow implementation[1]).

  1. for example it should be fine to base your x.borrow() == y.borrow() based on the result of x.cmp(&y) or x != y and assume no logic errors for the conclusion x == y to hold… also no side effects / consistent results is a useful assumption without which all these properties make little sense ↩︎

1 Like
6

No, this is wrong and (in general) doesn’t even compile. x.borrow() has a different type from y. It’s not the values of x and x.borrow() (let alone y and x.borrow()) that must be the same, but just the behavior of corresponding values under trait operations that must be the same.

Mathematically, we are essentially specifying .borrow() to be somewhat of a homomorphism[1].

  1. it’s likely challenging – or almost impossible – to understand the (highly abstract) general definition of “homomorphism” that is stated on that Wikipedia page, without at least somewhat of a background in formal logic or abstract algebra ↩︎

1 Like
7

HashMap requires

(x == y) == (x.borrow() == y.borrow())
&& if x == y { hash(x) == hash(y.borrow()) } else { true }

to be true for any x and y. It never does x.borrow() == x (Eq cannot do this comparison).

8

For context, this would be a consequence of both

I listed above, which could be abbreviated as hash(x) == hash(x.borrow())

[even though no such thing as “hash(…)” actually exists, and what matters is the sequence of calls to hasher to produce the hash value[1]]

together with the documented property of Hash interacting with Eq:

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

where L -> R is the sort of “implies” relation @drewtato wrote as if L { R } else { true } and one could also write as (!L) || R.

The consequence

x == y -> hash(x) == hash(y.borrow())

does follow from

hash(y) == hash(y.borrow())

and

x == y -> hash(x) == hash(y)

because in case of x == y being true, you can just chain equalities hash(x) == hash(y) == hash(y.borrow() to arrive at hash(x) == hash(y.borrow()) transitively.

  1. see the docs of Hasher saying “to produce the same hash value, Hash implementations must ensure for equivalent items that exactly the same sequence of calls is made – the same methods with the same parameters in the same order” ↩︎

9

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.