How can I lookup in a HashMap using a reference type without cloning my data members?

I'm trying to use a HashMap<(Graph, usize), bool> to memoize answers for a given Graph and node. I'm trying to write

// Extract the corresponding bool from the HashMap without copying an
// entire Graph.
fn get(
  m: HashMap<(Graph, usize), bool>,
  graph: &Graph,
  pos: usize,
) -> Option<bool> {
  // Error: expected struct `Graph`, found `&Graph`
  m.get(&(graph, pos))

I could "solve" this problem by making Graph implement Clone and calling graph.clone() here, but that's not really a solution I'm okay with :sweat_smile: Similarly, if the map were just a HashMap<Graph, bool>, indexing into it with a &Graph would be easy. But it's not - I need the key to represent both the graph and a position.

I've read the docs on Borrow, which describe the problem and the motivation to declare HashMap::get()'s signature in terms of Q: Borrow<K>, but the docs don't give an example of a successful value-type / reference-type pair used to store and retrieve values from the map.

Here's a minimal repro where I try to declare the tuple as an owning Key struct and describe its relationship to a borrowed KeyRef struct. It doesn't compile because Key::borrow() should return a reference, but I don't know how to tell Rust that a KeyRef struct is a reference.

You can't, because it isn't one. This isn't really a problem that is easily solvable with HashMap and Borrow at this point.

1 Like

This is a known limitation of the Borrow trait: it requires there to already be an instance of the borrowed type in order to return a reference to it. There are some crates with an alternative HashMap implementation that works around this (I don’t know the names, unfortunately). It’s also possible to use a trait object to get around the limitation.


The indexmap crate has an Equivalent trait for this purpose.


This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.