是否有可能使用HashSet作为HashMap的关键？ [英] Is it possible to use a HashSet as the key to a HashMap?

问题描述

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

 使用std :: collections :: {HashMap，HashSet}; 
 
 fn main（）{
 let hmap：HashMap< HashSet< usize> String> = HashMap :: new（）; 
 
 $ / code> 

给出以下错误：



error [E0277]：特征绑定的`std :: collections :: HashSet< usize> ;: std :: hash :: Hash`不是满意
- > src / main.rs：4：49
|
4 |让hmap：HashMap< HashSet< usize>，String> = HashMap :: new（）;
| ^ std :: hash :: Hash`没有为std :: collections :: HashSet< usize>实现`
|
= note：必须由< std :: collections :: HashMap< K，V>> :: new`


解决方案为了使 HashMap 的关键是你需要满足3个特性：

PartialEq - 您如何确定某个类型的两个实例是否相同？

Eq - 你能保证等式是自反的，对称的和传递的吗？这需要 PartialEq 。

这是基于 HashMap ：

  impl< K：Hash + Eq，V> HashMap< K，V，RandomState> {
 pub fn new（） - > HashMap< K，V，RandomState> {/ * ... * /} 
} 
  

检出 HashSet ，你可以看到它实现的特性（在页面底部列出）。

没有实现 Hash 为 HashSet ，所以它不能用作 HashMap 中的键。这就是说，如果你有一个计算 HashSet 的散列的理性方法，那么你可以在 HashSet 中创建一个newtype



下面是newtype的一个例子：

 使用std :: collections :: {HashMap，HashSet}; 
使用std :: hash :: {Hash，Hasher}; 
 
 struct Wrapper< T>（HashSet< T>）; 
 
 impl< T> PartialEq for Wrapper< T> 
其中
 T：Eq + Hash，
 {
 fn eq（& self，other：& Wrapper< T>） - > bool {
 self.0 == other.0 
} 
} 
 
 impl< T>包装的等式< T> 
其中
 T：Eq + Hash，
 {
} 
 
 impl< T> Hash for Wrapper< T> {
 fn hash< H>（& self，_state：& mut H）
其中
 H：哈希，
 {
 //在这里做些聪明的事情！ 
 
 
 
 fn main（）{
 let hmap：HashMap< Wrapper< u32>，String> = HashMap :: new（）; 
} 
  




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();
}

gives the following error:

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`

解决方案

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

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.

This is based on the definition of HashMap:

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

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

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};
use std::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的关键？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！