是否可以使用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个特征：

1. Hash

   — 如何计算该类型的哈希值？

2. PartialEq

   — 如何判断一个类型的两个实例是否相同？

3. 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

创建一个“新类型”并在其上实现这三个特征。

这是“新类型”的示例：

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

Answer 2

为 HashMap 或 HashSet 实现

Hash

更容易，谢谢你的想法。 要计算哈希值，我们只需将

HashSet

中每个元素（或

HashMap

中的键值对）的哈希值相加即可。

备注：

• 像我们一样对每个元素进行哈希处理有点不典型，因为我们每次都必须重新创建哈希器。
• 可以在与 HashMap/HashSet 关联的

  Hash

  上参数化我们的

  BuildHasher

  实现。
• Deref 和 DerefMut 使包装器更易于使用。一般来说，应该谨慎使用这些特征，因为它们使外部类型看起来和说话都像内部类型。
• 以下代码适用于 HashSet 和 HashMap，后者进行了一些调整。

#[derive(Clone, Debug, Default, Eq, PartialEq)]
struct HashSetWrapper<O: Eq + Hash + PartialEq>(HashSet<O>);

impl<O: Eq + Hash + PartialEq> Hash for HashSetWrapper<O> {
    // IMPLEMENTING HASH HERE
    fn hash<H: Hasher>(&self, state: &mut H) {
        // Use Wrapping<u64> to allow wrapping overflow
        let mut sum = Wrapping::default();
        for value in &self.0 {
            let mut hasher = DefaultHasher::new();
            Hash::hash(value, &mut hasher);
            sum += hasher.finish();
        }
        state.write_u64(sum.0);
    }
}

impl<O: Eq + Hash + PartialEq> Deref for HashSetWrapper<O> {
    type Target = HashSet<O>;

    fn deref(&self) -> &Self::Target {
        &self.0
    }
}

impl<O: Eq + Hash + PartialEq> DerefMut for HashSetWrapper<O> {
    fn deref_mut(&mut self) -> &mut Self::Target {
        &mut self.0
    }
}

有趣的事实：这个实现实际上与 Java 用于

java.util.HashMap

和

java.util.HashSet

的实现相同。我一直在思考 Rust 中的问题，直到我想起 Java 做了什么。