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.
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));
}
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.
