What's the idiomatic way to make a lookup tabl

Question

I have a collection of Foo.

struct Foo {
    k: String,
    v: String,
}

I want a HashMap which has the key &foo.k and the value foo.

Apparently, it is not possible without redesigning Foo by introducing Rc or clone/copy the k.

fn t1() {
    let foo = Foo { k: "k".to_string(), v: "v".to_string() };
    let mut a: HashMap<&str, Foo> = HashMap::new();
    a.insert(&foo.k, foo); // Error
}

There seems to be a workaround by abusing get() from HashSet (Playground):

use std::collections::{HashMap, HashSet};
use std::hash::{Hash, Hasher, BuildHasher};
use std::collections::hash_map::Entry::*;

struct Foo {
    k: String,
    v: String,
}

impl PartialEq for Foo {
    fn eq(&self, other: &Self) -> bool { self.k == other.k }
}

impl Eq for Foo {}

impl Hash for Foo {
    fn hash<H: Hasher>(&self, h: &mut H) { self.k.hash(h); }
}

impl ::std::borrow::Borrow<str> for Foo {
    fn borrow(&self) -> &str {
        self.k.as_str()
    }
}

fn t2() {
    let foo = Foo { k: "k".to_string(), v: "v".to_string() };
    let mut a: HashSet<Foo> = HashSet::new();
    a.insert(foo);
    let bar = Foo { k: "k".to_string(), v: "v".to_string() };
    let foo = a.get("k").unwrap();
    println!("{}", foo.v);
}

This is pretty tedious. What if a Foo has multiple fields and different collections of Foo to key on different fields?

Answer 1

You can introduce a wrapper type for the item stored in the set.

struct FooByK(Foo);

Then implement the various traits needed for the set for this struct instead. This lets you choose a different wrapper type if you need a set that indexes by a different member.

Answer 2

Apparently, it is not possible without redesigning Foo by introducing Rc or clone/copy the k.

That's correct, it is not possible to have HashMap<&K, V> where the key points to some component of the value.

The HashMap owns the key and the value, conceptually storing both in big vectors. When a new value is added to the HashMap, these existing values might need to be moved around due to hash collisions or the vectors might need to be reallocated to hold more items. Both of these operations would invalidate the address of any existing key, leaving it pointing at invalid memory. This would break Rust's safety guarantees, thus it is disallowed.

Read Why can't I store a value and a reference to that value in the same struct? for a thorough discussion.

Additionally, trentcl points out that HashMap::get_mut would allow you to get a mutable reference to the key, which would allow you to change the key without the map knowing. As the documentation states:

It is a logic error for a key to be modified in such a way that the key's hash, as determined by the Hash trait, or its equality, as determined by the Eq trait, changes while it is in the map.

---

Workarounds include:

• Remove the key from the struct and store it separately. Instead of HashMap<&K, V> where V is (K, Data), store HashMap<K, Data>. You can return a struct which glues references to the key and value together (example)

• Share ownership of the key using Rc (example)

• Create duplicate keys using Clone or Copy.

• Use a HashSet as you have done, enhanced by Sebastian Redl's suggestion. A HashSet<K> is actually just a HashMap<K, ()>, so this works by transferring all ownership to the key.