title: How to implement Hash for HashSet<T>?
body: <p>I'm working through some problems on leetcode to get better at using Rust during interviews. As a first attempt to solve <a href="https://leetcode.com/problems/3sum/" rel="nofollow noreferrer">this problem</a>, I thought of representing triplet solutions <code>a + b + c = 0</code> by storing <code>a</code>, <code>b</code>, and <code>c</code> in a <code>solution: HashSet&lt;i32&gt;</code>, then storing that <code>solution: HashSet&lt;i32&gt;</code> in another collection <code>solution_set: HashSet&lt;HashSet&lt;i32&gt;&gt;</code>. Crazy, right?</p>
  
  <p>The exercise explicitly states that redundant triplets don't qualify, so rather than storing the triplets in <code>solution: Vec&lt;i32&gt;</code>s where order might change a <code>Vec</code>'s hash value, I thought I'd store the triplets in <code>solution: HashSet&lt;i32&gt;</code> so any ordering of <code>a</code>, <code>b</code>, and <code>c</code> resolves to the same <code>solution</code>.  Additionally, it would be <code>O(1)</code> time to verify that a triplet already exists in <code>solution_set: HashSet&lt;HashSet&lt;i32&gt;&gt;</code>, rather than <code>O(n)</code> to check if it exists in the alternative <code>solution_set: Vec&lt;HashSet&lt;i32&gt;&gt;</code>. Finally, I know the return value is <code>Vec&lt;Vec&lt;i32&gt;&gt;</code>, but that's solved by <code>drain()</code>ing the <code>solution: HashSet&lt;i32&gt;</code> into <code>Vec&lt;i32&gt;</code>, and then draining the resulting <code>Iter&lt;Vec&lt;i32&gt;&gt;</code> into a <code>Vec&lt;Vec&lt;i32&gt;&gt;</code>.</p>
  
  <p>I recognize that <code>HashSet&lt;T&gt;</code> does not implement <code>Hash</code>, so I decided to try to myself, and now I'm up a paddle without a creek.  I looked <a href="https://doc.rust-lang.org/std/hash/trait.Hash.html" rel="nofollow noreferrer">here</a> to learn about implementing <code>Hash</code> for a struct, and <a href="https://stackoverflow.com/questions/25413201/how-do-i-implement-a-trait-i-dont-own-for-a-type-i-dont-own">here</a> to learn how to implement a trait on a struct I don't own, but now I'm re-implementing all the functions handles I need from <code>HashSet</code> (<code>new()</code>, <code>drain()</code>, <code>insert()</code>, etc) on <code>HashSetWrapper</code>. The compiler is also compaining about other traits too like <code>PartialEq</code>, so I've really opened pandora's box on this one. I just feel like this isn't the most "Rusty" way to do this. </p>
  
  <p>Also, I know that implementing hashes correctly is not trivial, and as this is an effort in best practices I'd like some help figuring out the most "Rusty" way to implement my solution is.  I haven't actually gotten it to work yet, but here's the code I have so far:</p>
  
  <pre><code>use std::collections::HashSet;
  use std::hash::{Hash, Hasher};
  
  #[derive(PartialEq)]
  struct HashSetWrapper&lt;T&gt;(HashSet&lt;T&gt;);
  
  impl&lt;T: Hash&gt; HashSetWrapper&lt;T&gt; {
      fn new() -&gt; Self {
          HashSetWrapper(HashSet::&lt;T&gt;::new())
      }
  
      fn insert(&amp;self, value: T) {
          self.0.insert(value);
      }
  }
  
  impl&lt;T: Hash&gt; Hash for HashSetWrapper&lt;T&gt; {
      fn hash&lt;H: Hasher&gt;(&amp;self, state: &amp;mut H) {
          for value in &amp;self.0 {
              value.hash(state);
          }
      }
  }
  
  impl Solution {
      pub fn three_sum(nums: Vec&lt;i32&gt;) -&gt; Vec&lt;Vec&lt;i32&gt;&gt; {
  
          let mut solution_set: HashSetWrapper&lt;HashSet&lt;i32&gt;&gt; = HashSetWrapper::new();
  
          for (i, a) in nums[0..(nums.len() - 2)].iter().enumerate() {
              for (j, b) in nums[i..(nums.len() - 1)].iter().enumerate() {
                  for c in nums[j..].iter() {
                      if a + b + c == 0 { 
                          let mut temp = HashSet::&lt;i32&gt;::new();
                          temp.insert(*a);
                          temp.insert(*b);
                          temp.insert(*c);
                          solution_set.insert(temp); }
                  }
              }
          }
          solution_set.drain().map(|inner_set| inner_set.drain().collect::&lt;Vec&lt;_&gt;&gt;()).collect::&lt;Vec&lt;_&gt;&gt;()
      }
  }
  </code></pre>
  
  <p>I still need to implement a <code>drain()</code> for my wrapper class, but I'm not even sure I'm going in the right direction.  How would you solve this problem? How would you implement <code>Hash</code> on <code>HashSet</code>? I'd love to know!</p>
  
  <p>Below are the errors the compiler is giving me:</p>
  
  <pre><code>Line 5, Char 26: binary operation `==` cannot be applied to type `std::collections::HashSet&lt;T&gt;` (solution.rs)
    |
  5 | struct HashSetWrapper&lt;T&gt;(HashSet&lt;T&gt;);
    |                          ^^^^^^^^^^
    |
    = note: an implementation of `std::cmp::PartialEq` might be missing for `std::collections::HashSet&lt;T&gt;`
  Line 5, Char 26: binary operation `!=` cannot be applied to type `std::collections::HashSet&lt;T&gt;` (solution.rs)
    |
  5 | struct HashSetWrapper&lt;T&gt;(HashSet&lt;T&gt;);
    |                          ^^^^^^^^^^
    |
    = note: an implementation of `std::cmp::PartialEq` might be missing for `std::collections::HashSet&lt;T&gt;`
  Line 9, Char 38: no function or associated item named `new` found for type `std::collections::HashSet&lt;T&gt;` in the current scope (solution.rs)
     |
  9 |         HashSetWrapper(HashSet::&lt;T&gt;::new())
     |                                      ^^^ function or associated item not found in `std::collections::HashSet&lt;T&gt;`
     |
     = note: the method `new` exists but the following trait bounds were not satisfied:
             `T : std::cmp::Eq`
  Line 13, Char 16: no method named `insert` found for type `std::collections::HashSet&lt;T&gt;` in the current scope (solution.rs)
     |
  13 |         self.0.insert(value);
     |                ^^^^^^ method not found in `std::collections::HashSet&lt;T&gt;`
     |
     = note: the method `insert` exists but the following trait bounds were not satisfied:
             `T : std::cmp::Eq`
  Line 28, Char 62: the trait bound `std::collections::HashSet&lt;i32&gt;: std::hash::Hash` is not satisfied (solution.rs)
     |
  8  |     fn new() -&gt; Self {
     |     ---------------- required by `HashSetWrapper::&lt;T&gt;::new`
  ...
  28 |         let mut solution_set: HashSetWrapper&lt;HashSet&lt;i32&gt;&gt; = HashSetWrapper::new();
     |                                                              ^^^^^^^^^^^^^^^^^^^ the trait `std::hash::Hash` is not implemented for `std::collections::HashSet&lt;i32&gt;`
  Line 38, Char 38: no method named `insert` found for type `HashSetWrapper&lt;std::collections::HashSet&lt;i32&gt;&gt;` in the current scope (solution.rs)
     |
  5  | struct HashSetWrapper&lt;T&gt;(HashSet&lt;T&gt;);
     | ------------------------------------- method `insert` not found for this
  ...
  38 |                         solution_set.insert(temp); }
     |                                      ^^^^^^ method not found in `HashSetWrapper&lt;std::collections::HashSet&lt;i32&gt;&gt;`
     |
     = note: the method `insert` exists but the following trait bounds were not satisfied:
             `std::collections::HashSet&lt;i32&gt; : std::hash::Hash`
  Line 42, Char 22: no method named `drain` found for type `HashSetWrapper&lt;std::collections::HashSet&lt;i32&gt;&gt;` in the current scope (solution.rs)
     |
  5  | struct HashSetWrapper&lt;T&gt;(HashSet&lt;T&gt;);
     | ------------------------------------- method `drain` not found for this
  ...
  42 |         solution_set.drain().map(|inner_set| inner_set.drain().collect::&lt;Vec&lt;_&gt;&gt;()).collect::&lt;Vec&lt;_&gt;&gt;()
     |                      ^^^^^ method not found in `HashSetWrapper&lt;std::collections::HashSet&lt;i32&gt;&gt;`
  error: aborting due to 7 previous errors
  </code></pre>