HashSet<T>如何实现Hash？
How to implement Hash for HashSet<T>?
我正在解决 leetcode 上的一些问题，以便在面试中更好地使用 Rust。作为解决 this problem 的第一次尝试，我想到通过将 a、b 和 c 存储在 solution: HashSet<i32> 中来表示三元组解决方案 a + b + c = 0 ，然后将 solution: HashSet<i32> 存储在另一个集合 solution_set: HashSet<HashSet<i32>> 中。疯了吧？
该练习明确指出冗余三元组不符合条件，因此与其将三元组存储在顺序可能会更改 Vec 的哈希值的 solution: Vec<i32> 中，我想我会将三元组存储在 solution: HashSet<i32> 中，因此 a、b 和 c 的任何排序都会解析为相同的 solution。此外，需要 O(1) 时间来验证 solution_set: HashSet<HashSet<i32>> 中是否已经存在一个三元组，而不是 O(n) 来检查它是否存在于替代 solution_set: Vec<HashSet<i32>> 中。最后，我知道 return 的值是 Vec<Vec<i32>>，但这可以通过 drain() 将 solution: HashSet<i32> 转换为 Vec<i32>，然后排出结果 Iter<Vec<i32>> 来解决] 变成 Vec<Vec<i32>>.
我认识到 HashSet<T> 没有实现 Hash，所以我决定自己尝试，现在我是在没有小溪的情况下划桨。我查看 here to learn about implementing Hash for a struct, and here 以了解如何在我不拥有的结构上实现特征，但现在我正在重新实现我需要的所有函数句柄 HashSet （new()， drain()、insert()，等等）在 HashSetWrapper 上。编译器也在抱怨其他特征，比如 PartialEq，所以我真的打开了潘多拉魔盒。我只是觉得这不是最 "Rusty" 的方法。
此外，我知道正确实施哈希并非易事，因为这是最佳实践中的一项工作，所以我希望得到一些帮助，找出实施我的解决方案的最 "Rusty" 方式。我还没有真正让它工作，但这是我到目前为止的代码：
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<_>>()
}
}
我仍然需要为我的包装器 class 实现 drain()，但我什至不确定我的方向是否正确。你会如何解决这个问题？您将如何在 HashSet 上实施 Hash？我很想知道！
以下是编译器给我的错误：
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
我刚刚浏览了您的代码和人们的评论。我认为您对 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
我正在解决 leetcode 上的一些问题，以便在面试中更好地使用 Rust。作为解决 this problem 的第一次尝试，我想到通过将 a、b 和 c 存储在 solution: HashSet<i32> 中来表示三元组解决方案 a + b + c = 0 ，然后将 solution: HashSet<i32> 存储在另一个集合 solution_set: HashSet<HashSet<i32>> 中。疯了吧？
该练习明确指出冗余三元组不符合条件，因此与其将三元组存储在顺序可能会更改 Vec 的哈希值的 solution: Vec<i32> 中，我想我会将三元组存储在 solution: HashSet<i32> 中，因此 a、b 和 c 的任何排序都会解析为相同的 solution。此外，需要 O(1) 时间来验证 solution_set: HashSet<HashSet<i32>> 中是否已经存在一个三元组，而不是 O(n) 来检查它是否存在于替代 solution_set: Vec<HashSet<i32>> 中。最后，我知道 return 的值是 Vec<Vec<i32>>，但这可以通过 drain() 将 solution: HashSet<i32> 转换为 Vec<i32>，然后排出结果 Iter<Vec<i32>> 来解决] 变成 Vec<Vec<i32>>.
我认识到 HashSet<T> 没有实现 Hash，所以我决定自己尝试，现在我是在没有小溪的情况下划桨。我查看 here to learn about implementing Hash for a struct, and here 以了解如何在我不拥有的结构上实现特征，但现在我正在重新实现我需要的所有函数句柄 HashSet （new()， drain()、insert()，等等）在 HashSetWrapper 上。编译器也在抱怨其他特征，比如 PartialEq，所以我真的打开了潘多拉魔盒。我只是觉得这不是最 "Rusty" 的方法。
此外，我知道正确实施哈希并非易事，因为这是最佳实践中的一项工作，所以我希望得到一些帮助，找出实施我的解决方案的最 "Rusty" 方式。我还没有真正让它工作，但这是我到目前为止的代码：
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<_>>()
}
}
我仍然需要为我的包装器 class 实现 drain()，但我什至不确定我的方向是否正确。你会如何解决这个问题？您将如何在 HashSet 上实施 Hash？我很想知道！
以下是编译器给我的错误：
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
我刚刚浏览了您的代码和人们的评论。我认为您对 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