我正在尝试使用 HashSet<String>
作为其他的 key HashSet
。
我找到了this question and answer指出要实现Hash
HashSet<String>
的特征,但我无法使我的具体案例发挥作用。
幸运的是,我的情况比较有约束力,所以我需要的是:
- 实现
hash
仅类型HashSet<String>
的特征 - 现在哈希应该非常简单:
套装{"q3", "q1", "q2"}
应该被散列为它的简单有序、连接字符串版本,例如 hash("q1-q2-q3")
。获取"q1-q2-q3"
不是问题,但在 hash
中使用它抛出各种我无法处理的错误。
这是我的实现尝试,但它不起作用。我认为StateSet
包装器不是正确的做法,因为我丢失了所有重要的 HashSet
方法
use std::collections::{HashMap,HashSet};
use std::hash::{Hash,Hasher};
type State = String;
struct StateSet(HashSet<State>);
impl PartialEq for StateSet {
fn eq(&self, other: &StateSet) -> bool {
self.is_subset(&other) && other.is_subset(&self)
}
}
impl Eq for StateSet {}
impl Hash for StateSet {
fn hash<H>(&self, state: &mut H) where H: Hasher {
let a: Vec<State> = self.iter().collect();
a.sort();
for s in a.iter() {
s.hash(state);
}
}
}
fn main() {
let hmap: HashSet<StateSet> = HashSet::new();
}
( playground )
最佳答案
您的代码存在几个问题,主要问题是您尝试通过在 newtype 包装器上调用 HashSet 上的方法来访问它们。您需要直接在 HashSet
上调用它们,方法是将 self
替换为 self.0
。这是最终的工作代码:
use std::collections::{HashMap,HashSet};
use std::hash::{Hash,Hasher};
type State = String;
struct StateSet(HashSet<State>);
impl PartialEq for StateSet {
fn eq(&self, other: &StateSet) -> bool {
self.0.is_subset(&other.0) && other.0.is_subset(&self.0)
}
}
impl Eq for StateSet {}
impl Hash for StateSet {
fn hash<H>(&self, state: &mut H) where H: Hasher {
let mut a: Vec<&State> = self.0.iter().collect();
a.sort();
for s in a.iter() {
s.hash(state);
}
}
}
fn main() {
let hmap: HashSet<StateSet> = HashSet::new();
}
此外,我强烈建议您使用 BTreeSet
这里,它实现了Hash
,因为它按排序顺序存储元素。它的 Hash
实现绝对应该比对所有项目进行 O(n log(n))
排序的实现更快。
关于HashSet 作为其他 HashSet 的键,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/36562419/