如何实现HashSet<T>的哈希？

Question

我正在解决 leetcode 上的一些问题，以便在面试中更好地使用 Rust。作为解决这个问题的第一次尝试，我想到a + b + c = 0通过将a、b、 和存储c在 a 中solution: HashSet<i32>，然后将其存储solution: HashSet<i32>在另一个集合中来表示三元组解决方案solution_set: HashSet<HashSet<i32>>。疯了，对吧？

该练习明确指出冗余三元组不符合条件，因此我不会将三元组存储在solution: Vec<i32>s 中，其中顺序可能会更改 aVec的哈希值，而是将三元组存储在solution: HashSet<i32>so中a，因此b、 和 的任何顺序c都会解析为相同的solution。此外，是O(1)时候验证三元组是否已存在于 中solution_set: HashSet<HashSet<i32>>，而不是O(n)检查它是否存在于替代方案 中solution_set: Vec<HashSet<i32>>。最后，我知道返回值是Vec<Vec<i32>>，但这可以通过drain()ing solution: HashSet<i32>into Vec<i32>，然后将结果排入Iter<Vec<i32>>来解决Vec<Vec<i32>>。

我认识到这并HashSet<T>不能实现Hash，所以我决定自己尝试一下，现在我已经无缘无故了。我在这里学习如何实现Hash结构体，在这里学习如何在我不拥有的结构体上实现特征，但现在我正在重新实现我需要的所有函数句柄HashSet( new()、drain()、insert()等)在HashSetWrapper。编译器还抱怨其他特征，例如PartialEq，所以我真的在这个问题上打开了潘多拉魔盒。我只是觉得这不是最“生锈”的方法。

另外，我知道正确实现哈希值并不是微不足道的，因为这是最佳实践中的一项努力，我希望有人帮助找出实现我的解决方案的最“生锈”的方法。我实际上还没有让它工作，但这是我到目前为止的代码：

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

#[derive(PartialEq)]
struct HashSetWrapper<T>(HashSet<T>);

impl<T: Hash> HashSetWrapper<T> {
    fn new() -> Self {
        HashSetWrapper(HashSet::<T>::new())
    }

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

impl<T: Hash> Hash for HashSetWrapper<T> {
    fn hash<H: Hasher>(&self, state: &mut H) {
        for value in &self.0 {
            value.hash(state);
        }
    }
}

impl Solution {
    pub fn three_sum(nums: Vec<i32>) -> Vec<Vec<i32>> {

        let mut solution_set: HashSetWrapper<HashSet<i32>> = 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::<i32>::new();
                        temp.insert(*a);
                        temp.insert(*b);
                        temp.insert(*c);
                        solution_set.insert(temp); }
                }
            }
        }
        solution_set.drain().map(|inner_set| inner_set.drain().collect::<Vec<_>>()).collect::<Vec<_>>()
    }
}

我仍然需要为我的包装类实现 a drain()，但我什至不确定我是否朝着正确的方向前进。你会如何解决这个问题？您将如何Hash实施HashSet？我很想知道！

以下是编译器给我的错误：

Line 5, Char 26: binary operation `==` cannot be applied to type `std::collections::HashSet<T>` (solution.rs)
  |
5 | struct HashSetWrapper<T>(HashSet<T>);
  |                          ^^^^^^^^^^
  |
  = note: an implementation of `std::cmp::PartialEq` might be missing for `std::collections::HashSet<T>`
Line 5, Char 26: binary operation `!=` cannot be applied to type `std::collections::HashSet<T>` (solution.rs)
  |
5 | struct HashSetWrapper<T>(HashSet<T>);
  |                          ^^^^^^^^^^
  |
  = note: an implementation of `std::cmp::PartialEq` might be missing for `std::collections::HashSet<T>`
Line 9, Char 38: no function or associated item named `new` found for type `std::collections::HashSet<T>` in the current scope (solution.rs)
   |
9 |         HashSetWrapper(HashSet::<T>::new())
   |                                      ^^^ function or associated item not found in `std::collections::HashSet<T>`
   |
   = 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<T>` in the current scope (solution.rs)
   |
13 |         self.0.insert(value);
   |                ^^^^^^ method not found in `std::collections::HashSet<T>`
   |
   = 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<i32>: std::hash::Hash` is not satisfied (solution.rs)
   |
8  |     fn new() -> Self {
   |     ---------------- required by `HashSetWrapper::<T>::new`
...
28 |         let mut solution_set: HashSetWrapper<HashSet<i32>> = HashSetWrapper::new();
   |                                                              ^^^^^^^^^^^^^^^^^^^ the trait `std::hash::Hash` is not implemented for `std::collections::HashSet<i32>`
Line 38, Char 38: no method named `insert` found for type `HashSetWrapper<std::collections::HashSet<i32>>` in the current scope (solution.rs)
   |
5  | struct HashSetWrapper<T>(HashSet<T>);
   | ------------------------------------- method `insert` not found for this
...
38 |                         solution_set.insert(temp); }
   |                                      ^^^^^^ method not found in `HashSetWrapper<std::collections::HashSet<i32>>`
   |
   = note: the method `insert` exists but the following trait bounds were not satisfied:
           `std::collections::HashSet<i32> : std::hash::Hash`
Line 42, Char 22: no method named `drain` found for type `HashSetWrapper<std::collections::HashSet<i32>>` in the current scope (solution.rs)
   |
5  | struct HashSetWrapper<T>(HashSet<T>);
   | ------------------------------------- method `drain` not found for this
...
42 |         solution_set.drain().map(|inner_set| inner_set.drain().collect::<Vec<_>>()).collect::<Vec<_>>()
   |                      ^^^^^ method not found in `HashSetWrapper<std::collections::HashSet<i32>>`
error: aborting due to 7 previous errors

Answer 1

我刚刚浏览了您的代码和人们的评论。我认为您对 过于复杂HashSet<i32>，然后必须为您的 实现所有特征函数HashSetWrapper。一个更简单的版本只是有一个简单的结构来保存您的三元组，并让它派生自Hash,Eq并PartialEq使用宏。为了使重复数据删除自动工作，我们可以将三元组排序为较早的注释。

以下是我的代码，它仍然大致遵循您的实现逻辑three_sum（顺便说一句，它有一个错误），并提出了这个建议。

#[derive(Hash, Eq, PartialEq, Debug)]
pub struct Triplet {
    x: i32,
    y: i32,
    z: i32,
}

impl Triplet {
    pub fn new(x: i32, y: i32, z: i32) -> Triplet {
        let mut v = vec![x, y, z];
        v.sort();
        Triplet {
            x: v[0],
            y: v[1],
            z: v[2],
        }
    }

    pub fn to_vec(&self) -> Vec<i32> {
        vec![self.x, self.y, self.z]
    }
}

pub fn three_sum(nums: Vec<i32>) -> Vec<Vec<i32>> {
    let mut res: HashSet<Triplet> = HashSet::new();
    for (i, a) in nums[0..(nums.len() - 2)].iter().enumerate() {
        for (j, b) in nums[i+1..(nums.len() - 1)].iter().enumerate() {
            for c in nums[j+1..].iter() {
                if a + b + c == 0 {
                    let triplet = Triplet::new(*a, *b, *c);
                    res.insert(triplet);
                }
            }
        }
    }
    res.into_iter().map(|t| t.to_vec()).collect()
}

测试代码：

    #[test]
    fn test_three_sum() {
        let result = vec![vec![-1, -1, 2], vec![-1, 0, 1]];
        assert_eq!(three_sum(vec![-1, 0, 1, 2, -1, -4]), result)
    }

结果：

running 1 test
test tests::test_three_sum ... ok