是否可以使用 HashSet 作为 HashMap 的键？

Question

我想使用 HashSet 作为 HashMap 的键。这可能吗？

use std::collections::{HashMap, HashSet};

fn main() {
    let hmap: HashMap<HashSet<usize>, String> = HashMap::new();
}

出现以下错误：

error[E0277]: the trait bound `std::collections::HashSet<usize>: std::hash::Hash` is not satisfied
 --> src/main.rs:4:49
  |
4 |     let hmap: HashMap<HashSet<usize>, String> = HashMap::new();
  |                                                 ^^^^^^^^^^^^ the trait `std::hash::Hash` is not implemented for `std::collections::HashSet<usize>`
  |
  = note: required by `<std::collections::HashMap<K, V>>::new`

Answer 1

要使某物成为 HashMap 的关键，您需要满足 3 个特征：

Hash — 如何计算该类型的哈希值？
PartialEq — 如何判断一个类型的两个实例是否相同？
Eq — 你能保证等式是自反、对称和传递的吗？这需要 PartialEq.

这是基于HashMap的定义：

impl<K: Hash + Eq, V> HashMap<K, V, RandomState> {
    pub fn new() -> HashMap<K, V, RandomState> { /* ... */ }
}

查看 HashSet 的文档，您可以看到它实现了哪些特征（列在页面底部）。

HashSet 没有 Hash 的实现，因此它不能用作 HashMap 中的键。话虽这么说，如果您有一种合理的方法来计算 HashSet 的哈希值，那么您可以围绕 HashSet 创建一个 "newtype" 并在其上实现这三个特征。

下面是 "newtype" 的示例：

use std::{
    collections::{HashMap, HashSet},
    hash::{Hash, Hasher},
};

struct Wrapper<T>(HashSet<T>);

impl<T> PartialEq for Wrapper<T>
where
    T: Eq + Hash,
{
    fn eq(&self, other: &Wrapper<T>) -> bool {
        self.0 == other.0
    }
}

impl<T> Eq for Wrapper<T> where T: Eq + Hash {}

impl<T> Hash for Wrapper<T> {
    fn hash<H>(&self, _state: &mut H)
    where
        H: Hasher,
    {
        // do something smart here!!!
    }
}

fn main() {
    let hmap: HashMap<Wrapper<u32>, String> = HashMap::new();
}

是否可以使用 HashSet 作为 HashMap 的键？

Is it possible to use a HashSet as the key to a HashMap?

hashmap

rust