Efficient multi-string HashMap keys

I would like to have a hash map with an owned multi-string key that I can query efficiently. For single-string keys, the K: Borrow<Q> bounds on get() make it so that I can query String keys with &str values, but I'm struggling to figure out to make this work for 2-string keys.

The problem I'm running into is that while the invariants for Borrow (Eq, Ord and Hash equivalence) should be good enough, the definition of Borrow requires that borrow() returns a reference into self. So while I think (&str, &str) (or a tuple struct verion of this) technically fits all the requirements for being used to query (String, String), I can't see a way to make this work.

I've also tried defining my own Cow-like enum, which runs into trouble when I want to define impl Borrow<Key<'a>> for Key<'static> because this conflicts with an std implementation.

An alternative solution would be concatenating the key's strings together into a single string, but this would require an allocation per query at least in the general case.

Am I missing something? What's the best way to do this?

The solution suggested here is indeed to use Cow, but use it for all fields of the Key, so you can cheaply construct an "owned" Key for lookup.

You can't implement Borrow<(&str, &str)> for (String, String) since it would have to return a &(&str, &str), but the (&str, &str) can't live anywhere, and as such you can't return a reference to it.

Using (Cow<'static, str>, Cow<'static, str>) for the key type should work for get, but not for get_mut (due to &mut T being invariant).
A workaround for this would be wrapping it in a newtype and manually implement Borrow for it. Note that it borrows as the wrapped type, this way it avoids conflicting with impl<T> Borrow<T> for T

use std::borrow::{Borrow, Cow};

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

impl<'a, 'b: 'a> Borrow<(Cow<'a, str>, Cow<'a, str>)> for Key<'b> {
    fn borrow(&self) -> &(Cow<'a, str>, Cow<'a, str>) {
        &self.0
    }
}

Another way would be using the unstable HashMap::raw_entry and then RawEntryBuilder::from_hash.

2 Likes

There's a clever workaround suggested here using trait objects:

1 Like