Is there any way to look up in HashSet by only the value the type is hashed on?

Question

I have a struct that has, among other data, a unique id:

struct Foo {
    id: u32,
    other_data: u32,
}

I want to use the id as the key and keep it inside of the struct:

use std::collections::HashSet;
use std::hash::{Hash, Hasher};
impl PartialEq for Foo {
    fn eq(&self, other: &Foo) -> bool {
        self.id == other.id
    }
}
impl Eq for Foo {}
impl Hash for Foo {
    fn hash<H: Hasher>(&self, state: &mut H) {
        self.id.hash(state);
    }
}

This works:

pub fn bar() {
    let mut baz: HashSet<Foo> = HashSet::new();
    baz.insert(Foo {
        id: 1,
        other_data: 2,
    });
    let other_data = baz.get(&Foo {
        id: 1,
        other_data: 0,
    }).unwrap()
        .other_data;
    println!("other_data: {}", other_data);
}

Is there any way to write baz.get(1).unwrap().other_data; instead of baz.get(&Foo { id: 1, other_data: 0 }).unwrap().other_data;?

An alternative might be a HashMap where the key is contained inside the struct. However, I can't have the id inside the struct and a duplicate id used for the key.

I don't know Rust very well. In reference-based languages (like Java) when this problem comes up, you'd use a boxed key (which you get whether you like it or not in Java) with a reference to it in the HashMap entry key field and another inside the corresponding value object. In a language like C or Ada that allows references/pointers to unboxed types, you can store the value in either place and a reference to it in the other. Afaik Rust collections allow the first solution for sure and maybe the second as well. — Gene, Jul 29 '17 at 03:51
maybe use an enum {Key(u32), KeyAndData(u32,u32)} and implement hash/eq so you can query by key and get keyanddata? That way you won't have to construct the tail of your `Foo`. Anyway, you didn't say why you actually need this, since your toy example already works without modification. — the8472, Jul 29 '17 at 09:45
@Gene Your first point works (see [How can I keep a reference to a key after it has been inserted into a HashMap?](https://stackoverflow.com/a/32403439/155423)), but you can't have a reference to the key because that solution is not memory-safe (and Rust will tell you so) — the address of the key can change as things are added/removed, so you'd have a dangling pointer. Rust is actually not smart enough to tell that the boxed case is fine, either. See [What's the idiomatic way to make a lookup table which uses field of the item as the key?](https://stackoverflow.com/q/43695527/155423) for more. — Shepmaster, Jul 29 '17 at 15:45
Thanks. I appreciate your response. I've only read through the docs of Rust, but it seems to have many ideas I've wished for in a language for a long time. — Gene, Jul 29 '17 at 16:10

Shepmaster · Accepted Answer · 2017-07-29T15:40:08.817

When you check out the signature for HashSet::get, you'll note that it's slightly more complicated than you might expect:

fn get<Q: ?Sized>(&self, value: &Q) -> Option<&T> 
where
    T: Borrow<Q>,
    Q: Hash + Eq,

This is done precisely to solve your problem. get accepts a reference to any type (&Q) that can be borrowed from the type in the set (T: Borrow<Q>). T should be read as "my type" and Q should be read as "the query type".

Thus, you need to implement Borrow for your type:

use std::borrow::Borrow;
use std::collections::HashSet;
use std::hash::{Hash, Hasher};

type Id = u32;

#[derive(Debug, Eq)]
struct Foo {
    id: Id,
    other_data: u32,
}

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

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

impl Borrow<Id> for Foo {
    fn borrow(&self) -> &Id {
        &self.id
    }
}

fn main() {
    let mut baz = HashSet::new();
    baz.insert(Foo {
        id: 1,
        other_data: 2,
    });

    let other_data = baz.get(&1).unwrap().other_data;
    println!("other_data: {}", other_data);
}

Is there any way to look up in HashSet by only the value the type is hashed on?

1 Answers1

Linked