是否有可能使用HashSet作为HashMap的关键？

问题描述

我想用为了使中创建一个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的关键？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！