Is it possible to use a HashSet as the key to a HashMap?

Question

I would like to use a HashSet as the key to a HashMap. Is this possible?

use std::collections::{HashMap, HashSet};

fn main() {
    let hmap: HashMap<HashSet<usize>, String> = HashMap::new();
}

gives the following error:

error[E0277]: the trait bound `std::collections::HashSet<usize>: std::hash::Hash` is not satisfied
 --> src/main.rs:4:49
  |
4 |     let hmap: HashMap<HashSet<usize>, String> = HashMap::new();
  |                                                 ^^^^^^^^^^^^ the trait `std::hash::Hash` is not implemented for `std::collections::HashSet<usize>`
  |
  = note: required by `<std::collections::HashMap<K, V>>::new`

Answer 1

To make something the key of a HashMap, you need to satisfy 3 traits:

1. Hash — How do you calculate a hash value for the type?
2. PartialEq — How do you decide if two instances of a type are the same?
3. Eq — Can you guarantee that the equality is reflexive, symmetric, and transitive? This requires PartialEq.

This is based on the definition of HashMap:

impl<K: Hash + Eq, V> HashMap<K, V, RandomState> {
    pub fn new() -> HashMap<K, V, RandomState> { /* ... */ }
}

Checking out the docs for HashSet, you can see what traits it implements (listed at the bottom of the page).

There isn't an implementation of Hash for HashSet, so it cannot be used as a key in a HashMap. That being said, if you have a rational way of computing the hash of a HashSet, then you could create a "newtype" around the HashSet and implement these three traits on it.

Here's an example for the "newtype":

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

struct Wrapper<T>(HashSet<T>);

impl<T> PartialEq for Wrapper<T>
where
    T: Eq + Hash,
{
    fn eq(&self, other: &Wrapper<T>) -> bool {
        self.0 == other.0
    }
}

impl<T> Eq for Wrapper<T> where T: Eq + Hash {}

impl<T> Hash for Wrapper<T> {
    fn hash<H>(&self, _state: &mut H)
    where
        H: Hasher,
    {
        // do something smart here!!!
    }
}

fn main() {
    let hmap: HashMap<Wrapper<u32>, String> = HashMap::new();
}