时间戳

首页 > 解决方案 > HashSet如何实现Hash?

hash - HashSet如何实现Hash?

问题描述

我正在解决 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 中 order 可能会更改 aVec的哈希值的位置，我想我会将三元组存储在solution: HashSet<i32>任何排序中，以便解析a为相同的. 此外，是时候验证三元组已经存在于 中，而不是检查它是否存在于替代中。最后，我知道返回值是，但这可以通过输入into ，然后将结果排入 a来解决。bcsolutionO(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，所以我决定自己尝试一下，现在我在没有小溪的情况下上岸。我在这里学习了如何实现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<_>>()
    }
}

我仍然需要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

标签： hashrusttraitshashset

解决方案

我刚刚浏览了您的代码和人们的评论。我认为您对 . 过于复杂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

推荐阅读