Rust: Set of Sets

user_13349653 0
Viewed 324

How does one create a set of sets in Rust? Is it necessary to write an impl block for every concrete type satisfying HashSet<HashSet<_>>?

Minimal failing example:

fn main () {
    let a: HashSet<u32> = HashSet::new();
    let c: HashSet<HashSet<u32>> = HashSet::new();
    c.insert(a);
}

Error:

"insert" method cannot be called on `std::collections::HashSet<std::collections::HashSet<u32>>` due to unsatisfied trait bounds
HashSet doesn't satisfy `std::collections::HashSet<u32>: Hash

Is it possible to override the fact that HashSet is unhashable? I'd like to use a HashSet and need my contents to be unique by actual (memory) equality; I don't need to unique by contents.

rust
2 Answers

I'd like to have a set of sets and want them to be unique by "actual" (memory) equality, not by contents.

To do so you first need to box the hashset so that it has a stable memory address. For example:

struct Set<T>(Box<HashSet<T>>);

To make your Set hashable, you'll need to implement Hash and Eq:

impl<T> Set<T> {
    fn as_addr(&self) -> usize {
        // as_ref() gives the reference to the heap-allocated contents
        // inside the Box, which is stable; convert that reference to a
        // pointer and then to usize, and use it for hashing and equality.
        self.0.as_ref() as *const _ as usize
    }
}

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

impl<T> Eq for Set<T> {}

impl<T> PartialEq for Set<T> {
    fn eq(&self, other: &Self) -> bool {
        self.as_addr() == other.as_addr()
    }
}

Finally, you'll need to add some set-like methods and a constructor to make it usable:

impl<T: Hash + Eq> Set<T> {
    pub fn new() -> Self {
        Set(Box::new(HashSet::new()))
    }

    pub fn insert(&mut self, value: T) {
        self.0.insert(value);
    }

    pub fn contains(&mut self, value: &T) -> bool {
        self.0.contains(value)
    }
}

Now your code will work, with the additional use of Rc so that you have the original Set available for lookup after you insert it:

fn main() {
    let mut a: Set<u32> = Set::new();
    a.insert(1);
    let a = Rc::new(a);
    let mut c: HashSet<_> = HashSet::new();
    c.insert(Rc::clone(&a));
    assert!(c.contains(&a));
}

Playground

user_16008980

As pointed out helpfully in the comments, it's not possible to hash sets because they have no fixed address. An effective, if inelegant, solution, is to wrap them in a specialized struct:

struct HashableHashSet<T> {
    hash: ...
    hashset: HashSet<T>
}

And then hash the struct by memory equality.

user_133496530
Related