Querying HashMap when Borrow<T> can't be satisfied

If the keys of my HashMap are String, I can query the HashMap using a &str because String implements Borrow<str>. This allows me to avoid allocating a new String for every get.

How can I avoid allocating when my key is an Option<String>, which can't implement Borrow<str> because of the None case?

use std::collections::HashMap;

fn main() {
  let mut map: HashMap<Option<String>, usize> = HashMap::new();
  map.insert(Some("foo".to_string()), 100);
  map.insert(Some("bar".to_string()), 200);
  map.insert(Some("baz".to_string()), 300);
  
  // How can I run this query without allocating?
  let value = map.get("foo").unwrap();
}

The solutions of which I'm aware are:

  • Use a library like indexmap that provides its own equivalence/querying trait that's easier to satisfy.
  • Make a wrapper for Option<String> that implements Borrow<&dyn SomeTrait> that gives me more flexibility.

I'm interested to know if there's a way to achieve this that avoids a new dependency and/or dynamic dispatch.

You could make a key wrapper for Option<String> that implements Borrow<Option<&str>>, and then lookups can use .get(&Some("foo")) -- a little clunky, but still not allocating.

(edit: nevermind, there's no way to tie the lifetime in that Option<&str>...)

OK, here's one that I actually tried first. :sweat_smile:

  • Use a key type Option<Cow<'static, str>>
  • Lookup with .get(&Some(Cow::from(my_str)))
    • Note that the lookup doesn't have to be 'static, thanks to variance.
3 Likes

Instead of HashMap<Option<String>, T>, you can have (HashMap<String, T>, Option<T>) or similar struct where the second field represent the entry for the None key.

2 Likes

Thanks, @cuviper! I think I can make this work.

I can't help but wonder if there's a way to make Borrow<T> (and/or HashMap) more flexible for this sort of use case. Borrow's requirement that the output value have the same lifetime as &self seems unnecessarily restrictive. The fact that indexmap was able to work around this with a custom trait (and a blanket impl for T: Borrow) seems to suggest it's possible.

Or perhaps now that GATs are landing the Borrow trait could (someday) leverage that and specify a default lifetime?

It isn't. Without this requirement, Borrow couldn't be usefully implemented for owning types. (If you borrow a String, where should the output lifetime come from, it not from &self?)

The Equivalent trait you are referring to doesn't substitute Borrow, it's more like a more general version of PartialEq.

In the context of maps, it's a substitute for both. The standard library uses K: Borrow<Q>, Q: Hash + Eq, while indexmap uses only Q: Hash + Equivalent<K>. There's a blanket impl that makes it behave the same way for types that do borrow, but you can also impl Equivalent separately for your own Q and K without any borrowing (as long as that doesn't overlap).

1 Like

In the context of maps, it's a substitute for both.

Exactly this. Borrow isn't overly restrictive for its stated purpose, its stated purpose is overly restrictive for HashMap::get.

Using raw_entry and from_hash would be the best choice, but it's still nightly.

1 Like