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

by

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

More Related Contents:

  1. How to lookup from and insert into a HashMap efficiently?
  2. How to implement HashMap with two keys?
  3. How do I create a HashMap literal?
  4. How can I update a value in a mutable HashMap?
  5. How can I mutate other elements of a HashMap when using the entry pattern?
  6. How to iterate through a Hashmap, print the key/value and remove the value in Rust?
  7. How do I use the Entry API with an expensive key that is only constructed if the Entry is Vacant?
  8. Swagger complex response model with dynamic key value hash maps
  9. How can I use a HashMap with f64 as key in Rust?
  10. How do I create a HashMap with type erased keys?
  11. Traits and Rust
  12. Why do try!() and ? not compile when used in a function that doesn’t return Option or Result?
  13. How do I collect into an array?
  14. Cannot borrow as mutable more than once at a time in one code – but can in another very similar
  15. How do I conditionally return different types of futures?
  16. Why there is no ConcurrentHashSet against ConcurrentHashMap
  17. Is it considered a bad practice to implement Deref for newtypes?
  18. Implementing a trait for multiple types at once
  19. How to declare a higher-ranked lifetime for a closure argument?
  20. How do I get an owned value out of a `Box`?
  21. Is hash_map part of the STL?
  22. How does Rust implement reflection?
  23. How can I deserialize JSON with a top-level array using Serde?
  24. How do you use parent module imports in Rust?
  25. What is the best way to use a HashMap in C++?
  26. Memory overhead of Java HashMap compared to ArrayList
  27. How to take ownership of T from Arc?
  28. Is it possible to make a recursive closure in Rust?
  29. Is there any trait that specifies numeric functionality?
  30. How to escape curly braces in a format string in Rust

Leave a Comment