可以将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`

- jojoshua

---

可以使用BTreeSet作为HashMap的键，因为BTreeSet实现了适当的特性。我知道这不是原问题的严格答案，但它似乎仍在范围内：原问题正是我在寻找的，但对我来说，BTreeSet是一个完全可以接受的答案。 - Danek Duvall

Answer 1

要将某个东西作为 HashMap 的键，需要满足以下三个特征：

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 的文档，你可以看到它实现的 trait（列在页面底部）。 HashSet 没有实现 Hash，所以不能作为 HashMap 的键。即便如此，如果你有一种合理的计算 HashSet 哈希值的方法，那么你可以创建一个围绕 HashSet 的“新类型”，并在其上实现这三个属性。

以下是“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();
}

- Shepmaster

---

谢谢你的回答！它证实了我需要学习的很多东西。 - jojoshua

Answer 2

实现HashMap或HashSet的哈希（Hash）比你想象的要简单。 要计算哈希，我们只需将HashSet中的每个元素的哈希值相加（或HashMap中的键值对的哈希值）。

编辑：基于这个解决方案，我决定在crates.io上发布一个crate hash-that-set。它允许将哈希映射和集合包装在SumHashes::new(my_set_or_map)中。这个包装器包括下面解决方案中的所有内容，以及与标准特性更好的互操作性。

注意：

- 我们所做的每个元素的哈希化有些不典型，因为我们必须每次重新创建哈希器。 - 我们可以将我们的Hash实现参数化为与HashMap/HashSet相关联的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是如何解决的。

- A248

---

加法相对于异或运算有什么优势？ - undefined

好问题 @leo848。我没有考虑到异或（XOR），但是另一个Stack Overflow的问题似乎回答了为什么异或不是首选的组合哈希技术的原因： https://stackoverflow.com/a/27952689 - undefined

从链接的帖子中提到的两个观点在这种情况下都是不相关的，因为HashSet已经是唯一的，而且交换律是被积极需要的。 - undefined

提到那篇文章，重要的是要记住，成对相同的哈希值，不一定是相同的元素，会映射到0。两个元素可能会生成相同的哈希值；这取决于哈希函数的实现和Hash::hash的实现，这种情况可能更常见或更少见。例如，我曾经看到过一些代码，它使用一个ID整数作为哈希值，但在相等比较中考虑了其他字段。 - undefined