Indexing a `HashMap<&String, V>` with `&str`

What is the proper way to index into a HashMap<&String, V> with a &str? Rust reports that &String is not Borrow<str>, which is required for indexing. (This seems a bit silly to me; if T: Borrow<U> then surely &T: Borrow<U> should also hold?)

use std::collections::HashMap;

fn main() {
    let strings = vec!["x".to_owned(), "y".to_owned(), "z".to_owned()];
    let m = [0, 1, 2]
        .into_iter()
        .map(|i| (&strings[i], i))
        .collect::<HashMap<&String, usize>>();
    let zero = m["x"];
}

error[E0277]: the trait bound `&String: Borrow<str>` is not satisfied
 --> src/main.rs:9:18
  |
9 |     let zero = m["x"];
  |                  ^^^ the trait `Borrow<str>` is not implemented for `&String`, which is required by `HashMap<&String, usize>: Index<&_>`
  |
  = help: the trait `Borrow<str>` is implemented for `String`
  = help: for that trait implementation, expected `String`, found `&String`
  = note: required for `HashMap<&String, usize>` to implement `Index<&str>`

Obviously, because I constructed this particular HashMap, I could go back and change its key type to &str instead. But supposing I'm handed a HashMap<&String, V>, what is the proper way to index it? Constructing a whole String just to take a reference to it seems wasteful.

Solution

There is a way around this if you are willing to dip into unsafe waters.

This solution takes advantage of the fact that if you have a struct S marked #[repr(transparent)] and containing a single field of type T, you can safely transmute from &'a T to &'b S where 'a: 'b. (This is why you can borrow a &Path from a PathBuf even though no Path ever actually exists, for example.)

So, let's build a newtype that we can borrow from String, and with a positively bikesheddable name.

#[derive(Hash, PartialEq, Eq)]
#[repr(transparent)]
struct StrRef(str);

This definition allows us to safely transmute from &str to &StrRef, so we'll wrap that bit of unsafe code up in a From implementation:

impl<'a> From<&'a str> for &'a StrRef {
    fn from(value: &'a str) -> &'a StrRef {
        // SAFETY: StrRef is repr(transparent) and contains only a str.
        unsafe { &*(value as *const str as *const StrRef) }
    }
}

Now we can implement Borrow<StrRef> on any type from which we can get a &str.

// Not actually needed, just for example.
impl Borrow<StrRef> for String {
    fn borrow(&self) -> &StrRef {
        self.as_str().into()
    }
}

// This is the impl you need in this case.
impl Borrow<StrRef> for &String {
    fn borrow(&self) -> &StrRef {
        self.as_str().into()
    }
}

Finally, this allows us to write the following function, which accomplishes your goal of fetching from the map using a &str without converting it to an owned String:

fn get_from_map<'a, T>(map: &'a HashMap<&String, T>, key: &str) -> Option<&'a T> {
    map.get(<&StrRef>::from(key))
}

(Playground)

Obviously, if you can change the map's key type to &str then you should prefer that, but if you don't have control over where the map comes from then this is a viable workaround (in a -- hopefully -- very limited scope within your program).