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

问题描述

我想使用 HashSet 作为 HashMap 的键.这可能吗?

I would like to use a HashSet as the key to a HashMap. Is this possible?

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`

推荐答案

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

To make something the key of a HashMap, you need to satisfy 3 traits:

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

1. Hash — How do you calculate a hash value for the type?
2. PartialEq — How do you decide if two instances of a type are the same?
3. Eq — Can you guarantee that the equality is reflexive, symmetric, and transitive? This requires PartialEq.

这是基于HashMap的定义:

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

查看 HashSet 的文档/a>，你可以看到它实现了哪些特征(在页面底部列出).

Checking out the docs for HashSet, you can see what traits it implements (listed at the bottom of the page).

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

There isn't an implementation of Hash for HashSet, so it cannot be used as a key in a HashMap. That being said, if you have a rational way of computing the hash of a HashSet, then you could create a "newtype" around the HashSet and implement these three traits on it.

以下是新类型"的示例:

Here's an example for the "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 的键?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！