HashSet 作为其他 HashSet 的键

Question

我正在尝试使用 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 wrapper 不是正确的做法，因为我丢失了所有重要的 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 )

Answer 1

您的代码有几个问题，主要问题是您试图通过在新类型包装器上调用它们来访问 HashSet 上的方法。您需要通过将 self 替换为 self.0 直接在 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.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)) 排序的实现更快。