在Rust中，我如何从HashMap的键创建一个HashSet？

Question

我有两个 HashMap，想要计算它们的键的交集。是否可以通过 HashMap::keys() 返回的内容构建一个 HashSet 呢？例如：

use std::collections::{HashSet, HashMap};

fn main() {
    let mut map1: HashMap<i64, i64> = HashMap::new();
    let mut map2: HashMap<i64, i64> = HashMap::new();

    // Add some values into the HashMaps for demonstration
    map1.insert(1, 10);
    map1.insert(5, 50);
    map2.insert(3, 30);
    map2.insert(5, 50);

    let set1: HashSet<i64> = HashSet::from(map1.keys());  // How to do this?
    let set2: HashSet<i64> = HashSet::from(map2.keys());  // How to do this?

    let set3 = set1.intersection(&set2); // What I'm looking to accomplish
    // set3 should contain [5], as this is the one key shared by the two HashMaps
}

- Marijn van Vliet

---

你是在寻找高效的解决方案，还是简单的解决方案？ - Matthieu M.

我正在努力学习这门语言，所以我希望能得到一个优雅但可能较慢的解决方案和一个快速解决方案的示例。 - Marijn van Vliet

Answer 1

简单的解决方案

你的代码只需要些微调整即可编译（请参见Playground）：

use std::collections::{HashSet, HashMap};

fn main() {
    let mut map1 = HashMap::new();
    let mut map2 = HashMap::new();

    // Add some values into the HashMaps for demonstration
    map1.insert(1, 10);
    map1.insert(5, 50);
    map2.insert(3, 30);
    map2.insert(5, 50);

    let set1: HashSet<i64> = map1.keys().cloned().collect();
    let set2: HashSet<i64> = map2.keys().cloned().collect();

    let set3 = set1.intersection(&set2);
    println!("{:?}", set3);
}

特别注意 map1.keys().cloned().collect()：

• HashMap<K, V>::keys() 返回一个 Iterator<Item = &'a K>,
• .cloned() 将其转换为 Iterator<Item = K>，
• .collect() 从中构建一个集合，因为 HashSet 实现了 FromIterator 特性。

然而，这并不是非常有效：

• 从时间复杂度上来看：为 O(map1.size() + map2.size())。
• 从内存占用上来看：可能会有很大的分配。

高效解决方案

直接在 HashMap 的键上实现 intersection。

- Matthieu M.

---

“lots of allocations” - 仅有两个额外的分配。HashMap::keys() 返回一个 ExactSizeIterator，因此收集器可以一步分配 HashSet。 - Peter Hall

@PeterHall：重新表述一下，问题不在于数字本身，而在于它们的大小。 - Matthieu M.

&'a K代表什么？是指类型为K的某个项目的引用吗？ - Marijn van Vliet

@MarijnvanVliet：是的，哈希映射的一个不可变引用键。 - Matthieu M.

Answer 2

您只需要将其收集到 HashSet 中：

let set1: HashSet<i64> = map1.keys().copied().collect(); 
let set2: HashSet<i64> = map2.keys().copied().collect();

使用copied()将取消引用键并复制它们，因为您需要的是HashSet<i64>而不是HashSet<&i64>。

- Peter Hall