HashSet 作为其他 HashSet 的键

标签 hash rust hashset

我正在尝试使用 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/

相关文章:

rust - 如何将 Iterator<String> 作为 Iterator<&str> 传递?

rust - 如何使用通用 VecDeque?

java - HashSet 添加重复字符串

PHP/MySQL : What data type to chose for encrypted passwords (bcrypt, 最大。 100 个字符)

.net - 创建 sha1 哈希时如何使用 machineKey validationKey?

PHP 和 SQL 哈希帮助 : What am I doing wrong?

rust - 无法为返回引用的闭包推断适当的生存期

java - 订购哈希集示例?

.net - HashSet<T> 与 Dictionary<K, V> 相对于查找项目是否存在的搜索时间

php - 如何使用散列密码后登录页面