HashMap with lookup by key variant that has references?

help
1

Say I want to create a cache using a HashMap. My keys are structs that contain a font name and size, something like:

#[derive(Hash, Eq, PartialEq, Debug)]
struct FontKey { 
    font_name: String, 
    font_size: NotNan<f32> 
}

I don't want to have to allocate that String to look something up. For a lookup, I'd prefer something like:

struct FontKey2 { font_name: &'a str, font_size: NotNan<f32> }

But I can’t put those in my HashMap field. I thought maybe I could Borrow, but I guess not. Don’t see how to fill in the todo!() here. (playground link).

Is there a way to do this? Another path: maybe I can intern the font names and use something like a struct FontNameId(u32) in the cache keys.

use std::collections::HashMap;
use std::borrow::Borrow;

#[derive(Eq, PartialEq, Hash, Debug)]
struct Key {
    font_name: String,
    font_size: u32,
}
#[derive(Eq, PartialEq, Hash, Debug)]
struct Key2<'a> {
    font_name: &'a str,
    font_size: u32,
}
impl<'a> Borrow<Key2<'a>> for Key {
    fn borrow(&self) -> &Key2<'a> {
        todo!()
    }
}
fn main() {
    let mut cache: HashMap<Key, i32> = HashMap::new();
    let font_name: String = "Roboto".to_owned();
    cache.insert(Key { font_name: font_name.clone(), font_size: 14 }, 123);
    let k2 = Key2 { font_name: font_name.as_str(), font_size: 14 };
    let val = cache.get(&k2);
    println!("val = {:?}", val);
}
2

Indeed, Borrow can only be used to return references to something stored in Self. You can't create a completely new Key2 instance inside of Borrow::borrow and return that, as Borrow::borrow's signature doesn't allow it.

Have you looked at Cow as a possible solution for your problem?

1 Like
3

You may be interested in hashbrown's Equivalent trait. You just need to implement Equivalent<FontKey2> for FontKey and then you can use the hashbrown::HashMap API as you would with std::collections::HashMap.

2 Likes
4

I had not, but just looked into it because of your comment. I think that would put a lifetime parameter on my cache: HashMap<…> field, so it’s too confusing (or impossible) for me here. But good to know about that Cow type.

5

It would add a lifetime to the Key type but not to the cache because the cache can make it 'static.

use std::borrow::Cow;
use std::collections::HashMap;

#[derive(Eq, PartialEq, Hash, Debug)]
struct Key<'a> {
    font_name: Cow<'a, str>,
    font_size: u32,
}

fn main() {
    let mut cache: HashMap<Key<'static>, i32> = HashMap::new();
    let font_name: String = "Roboto".to_owned();
    cache.insert(Key { font_name: Cow::Owned(font_name.clone()), font_size: 14 }, 123);
    let k2 = Key { font_name: Cow::Borrowed(font_name.as_str()), font_size: 14 };
    let val = cache.get(&k2);
    println!("val = {:?}", val);
}

That said, hashbrown is a slightly more efficient option because it means that no run-time checks of the Cow variant are needed.

3 Likes
6

there's a trick to work around the limitation, the short sumamry is, you delegate your Hash implementation, both for the owned key type, and for the lookup key type, to a intermediate thingy, and both can Borrow the common intermediate type. and because Borrow<T> has a relaxed T: ?Sized bound, you can borrow as a dyn Trait.

read the details in this "tricking the hashmap" blog post:

EDIT: forgot to mention, this article was published for early version of rust in which trait objects were written without the dyn keyword. the idea is still valid in current versions, just syntax changed. keep this difference in mind and don't get confused when reading the code snippets.

7

The code in that article

  1. Predates dyn so may be confusing: here's an updated playground.
  2. Relies on the implementation details of String's Hash implementation: Better to use a newtype.

Here's my walkthrough of the same basic approach...

...but it may be overkill for the OP.

2 Likes
8

Hashbrown has no advantage over HashMap here, because HashMap::{get,entry,..} already supports this through the Borrow, Hash, and Eq traits.

Afaik Cow avoids checking the variant when drreferencing, so no performance hit in Cow either. If you want both owned and borrowed keys in the same type of hashmap, then HashMap<Cow<'static,K>,V> works nicely. Also we've enough Froms for Cow so you could probably just call .into() everywhere.

9

The signature of Borrow::borrow makes this somewhat awkward because it wants you to return a &Borrowed from a &Self. In the general case there is no Borrowed contained within Self that you can produce a reference to.

The advantage of hashbrown is that Equivalent::equivalent only needs to return a bool, and so doesn't require you to conjure up a value out of thin air just for the purpose of an equality check.