`HashMap::get` where key type owns string, but using a &str

I can easily get a value from a HashMap<String, String> by using a &str:

let map: HashMap<String, String> = HashMap::new();
map.get("key");

It makes sense - the map doesn't eat the key when you get from it.

But, when the key is not a String but a (usize, String):

let map: HashMap<(usize, String), String> = HashMap::new();
// how to avoid the allocation?
map.get(&(1, "key".to_string()));

I still have to pass the key as reference, but in there, I have to allocate! Is there a way to avoid that?

1 Like

You can avoid allocating with Cow:

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

fn main() {
    let map: HashMap<(usize, Cow<str>), String> = HashMap::new();
    // how to avoid the allocation?
    map.get(&(1, "key".into()));
}

Playground.

nice, but that involves a lifetime where I store the map with the cows, unless I'm doing it wrong.

To support string literals and owned strings as keys (which is more flexible than your current API that only allows owned strings as keys), Cow<'static, str> will be enough. So no need to add lifetime parameters to types that store such a hash map.

1 Like

I think the design of HashMap unfortunately doesn't allow this because the Borrow trait must return a reference to part of the key rather than another type that contains such references. I consider this a design flaw of Borrow.

2 Likes

If you use hashbrown::HashMap, which is the underlying implementation in the standard library, it will allow such look-ups using anything that implements Equivalent. That trait covers the normal Borrow+Eq relationship, but you can also extend it by implementing something like struct Query(usize, &str) to use in your get calls.

3 Likes

Yeah this is what I've done when I needed something like this.

Would that even be possible to express in the language?

impl<OI, BI> Borrow<(BI)> for (OI)
    where OI: Borrow<BI> {
    type Borrowed = (BI);
}

While thats technically possible with a good old impl! macro for tuples up to size N, it's not really expressing the relation. We'd need variadic generics or something like that.

'static doesn't suffice in the actual example.
We ended up using a different data structure, where the usize indexes a vector with maps.
But the hashbrown suggestion is very interesting!