How to lookup a value in HashMap with a composite key containing a String without allocating

help
1 
use std::collections::HashMap;

fn main() {
    let mut map: HashMap<String, u32> = HashMap::new();
    map.insert("a".into(), 1);
    assert!(map.contains_key("a")); // ok
    assert!(map.get("a").is_some()); // ok

    let mut map2: HashMap<(String, u32), u32> = HashMap::new();
    map2.insert(("a".into(), 0), 1);
    // map2.contains_key(&("a", 0)); // error
    // map2.contains_key(&(&"a", 0)); // error
    // map2.contains_key(("a", 0)); // error
    // map2.contains_key((&"a", 0)); // error
    let s = "a".to_string();
    map2.contains_key(&(s, 0)); // ok, but required allocation
}

Is there any way at all?

2

You can use a newtype for the key which stores a Cow:

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

#[derive(Clone, Debug, Eq, PartialEq, Hash)]
struct Key<'a>(Cow<'a, str>, u32);

fn main() {
    let mut map2: HashMap<Key<'static>, u32> = HashMap::new();
    map2.insert(Key(Cow::Owned("a".to_string()), 0), 1);
    map2.contains_key(&Key(Cow::Borrowed("a"), 0));
}
3

for the hashbrown api, which uses the Equivalent trait to mark the lookup key types, this is easy to do, but the standard library hashmap api uses the Borrow trait, and you need an extra level of indirection to make it work.

the trick is to make both the stored key and the lookup key to borrow and delegate their Hash to some common type, and this common type can be a dyn Trait. read this article for details:

4

My use case is essentially building reverse lookup tables based on combinations of different properties (many of which are String) of a bunch of different item types so having to make a new type for each key is definitely tedious. Thankfully macros will make it easier to manage and encapsulating the conversions using traits will make the public API seamless. I will go with this approach, thank you very much.

5

That was an interesting read and although it could work I think the solution above is simpler for my case. Anyway I have been wanting to write more flexible public APIs using standard traits so this might come in handy in the future. Thank you, bookmarked :+1: