Hashbrown Hashmap vs Std HashMap (trait Equivalent is not implemented for ...)

help
1

Consider the following code:

use hashbrown::HashMap as HBHMap;
use std::collections::HashMap as StdHMap;

#[derive(Hash, Eq, PartialEq)]
struct Foo {
    x: i32,
}

fn main() {
    // std HashMap
    let x = Foo { x: 0 };
    let mut hm1 = StdHMap::new();
    hm1.insert(x, 100);
    let y = &Foo { x: 0 };
    hm1.get(y);
    hm1.get(&y);  // <-- works fine

    // hashbrown HashMap
    let x = Foo { x: 0 };
    let mut hm2 = HBHMap::new();
    hm2.insert(x, 100);
    let y = &Foo { x: 0 };
    hm2.get(y);
    hm2.get(&y);   // <-- error here
}

I know the example is contrived, but I am having a hard time understanding why the std hasmap example works whereas th hashbrown's hashmap example doesnt?

I checked the trait bound requirements:

std hashmap:

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

hashbrown hashmap:

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


impl<Q, K> Equivalent<K> for Q
where
    Q: Eq + ?Sized,
    K: Borrow<Q> + ?Sized,

What kind of cooercion / auto-deref / auto-borrow is in play here such that the std Hashmap example works but the hashbrown hashmap one gives the following error:

❯ cargo b
   Compiling hashbrown-vs-hashmap v0.1.0 (/home/shank/code/tmp/hashbrown-vs-hashmap)
error[E0277]: the trait bound `&Foo: Equivalent<Foo>` is not satisfied
    --> src/main.rs:24:13
     |
24   |     hm2.get(&y);
     |         --- ^^ the trait `Borrow<&Foo>` is not implemented for `Foo`
     |         |
     |         required by a bound introduced by this call
     |
     = note: required for `&Foo` to implement `Equivalent<Foo>`
note: required by a bound in `hashbrown::HashMap::<K, V, S, A>::get`
    --> /home/shank/.cargo/registry/src/index.crates.io-1949cf8c6b5b557f/hashbrown-0.15.4/src/map.rs:1306:19
     |
1304 |     pub fn get<Q>(&self, k: &Q) -> Option<&V>
     |            --- required by a bound in this associated function
1305 |     where
1306 |         Q: Hash + Equivalent<K> + ?Sized,
     |                   ^^^^^^^^^^^^^ required by this bound in `HashMap::<K, V, S, A>::get`

For more information about this error, try `rustc --explain E0277`.
error: could not compile `hashbrown-vs-hashmap` (bin "hashbrown-vs-hashmap") due to 1 previous error
2

TLDR: type inference when only a single applicable trait implementation.

this is a special case indeed, but it's a special type inference rule. after the type is inferred, then the regular auto deref follows.

in other words, substitue Foo for K, the bound K: Borrow<Q> became Foo: Borrow<Q>, and since there's only one Borrow implementation for Foo, namely the (blanket) reflexive implementation, the type Q must be Foo.

if you add another Borrow implementation, you'll find the first case gives compile error too, e.g.:

// adding this ...
impl Borrow<i32> for Foo {
    fn borrow(&self) -> &i32 {
        &self.x
    }
}
// ... causes compile error here:
// error: `Foo: Borrow<&Foo>` not satisified
hm1.get(&y);

this inference logic cannot be applied to Equivalent, since the position of K and Q is reversed, which means finding all Q that implements Equivalent<K> needs non-local information.

for example, suppose I have a crate where I can define a type Bar that cannot be borrowed from Foo:

struct Bar {
    x: i32,
    s: String,
}

// must be hashing like `Foo`
impl Hash for Bar {
    //...
}

impl Equivalent<Foo> for Bar {
    //...
}

so that I can use Bar to lookup a hashmap with key of Foo.

note, this use case is not supported by the standard library.

3 Likes