hash - 如何为 HashSet<T> 实现哈希？

Question

这个问题在这里已经有了答案:





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

(1 个回答)


去年关闭。




我正在解决 leetcode 上的一些问题，以便在面试中更好地使用 Rust。作为第一次尝试解决this problem ，我想到了代表三重解a + b + c = 0通过存储 a , b , 和 c在 solution: HashSet<i32> ，然后存储 solution: HashSet<i32>在另一个系列中 solution_set: HashSet<HashSet<i32>> .疯了吧？

该练习明确指出冗余三元组不符合条件，因此不要将三元组存储在 solution: Vec<i32> 中。 s 订单可能会更改 Vec的哈希值，我想我会将三元组存储在 solution: HashSet<i32> 中所以任何 a 的顺序, b , 和 c解析为相同的 solution .此外，它将是 O(1)是时候验证 solution_set: HashSet<HashSet<i32>> 中已经存在三元组了, 而不是 O(n)检查它是否存在于替代 solution_set: Vec<HashSet<i32>> .最后，我知道返回值是 Vec<Vec<i32>> ，但这已由 drain() 解决正在solution: HashSet<i32>进入 Vec<i32> ，然后排空产生的 Iter<Vec<i32>>成Vec<Vec<i32>> .

我承认 HashSet<T>不实现 Hash ，所以我决定尝试自己，现在我在没有小溪的情况下划桨。 🚣我看了here了解实现 Hash对于结构，和 here学习如何在我不拥有的结构上实现特征，但现在我正在重新实现我需要的所有函数句柄 HashSet ( new() 、 drain() 、 insert() 等)在 HashSetWrapper 上.编译器也在提示其他特性，比如 PartialEq ，所以我真的打开了这个潘多拉的盒子。我只是觉得这不是最“使用rust ”的方式来做到这一点。

此外，我知道正确实现哈希值并非易事，而且由于这是最佳实践中的一项努力，我需要一些帮助来找出实现我的解决方案的最“使用rust ”的方式。我还没有真正让它工作，但这是我到目前为止的代码:

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

我仍然需要实现一个 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