内部连接Rust中的两个"HashMap"

Question

假设我们有两个std::collections::HashMap-，比如HashMap<K, V1>和HashMap<K, V2>，以及一个函数Fn(V1, V2) -> R。

如何在这些哈希映射上执行内部联接，从而在它们的共享密钥上获得HashMap<K, R>？这里有一个参考实现来说明我的意思：

use std::collections::HashMap;
fn main() {
let mut map_a = HashMap::<&str, i32>::new();
map_a.insert("foo", 1);
map_a.insert("bar", 2);
map_a.insert("qux", 3);
map_a.insert("quux", 4);

let mut map_b = HashMap::<&str, i32>::new();
map_b.insert("foo", 5);
map_b.insert("bar", 6);
map_b.insert("quuux", 7);
map_b.insert("quuuux", 8);

// To keep it simple I'm just combining respective values into a tuple:
let joined_map = map_a
.into_iter()
.filter_map(|(key, value_a)| map_b.remove(key).map(|value_b| (key, (value_a, value_b))))
.collect::<HashMap<&str, (i32, i32)>>();

println!("{:?}", joined_map);
}

预期输出为：

{"foo": (1, 5), "bar": (2, 6)}

这很好用，我可以在utils.rs中使其通用，但我觉得在标准库或crates.io中找不到现有的实现是不对的。此外，不执行某种排序合并联接似乎不太理想，因为我们已经在HashMap下对哈希代码进行了排序。我在监督什么吗？还是因为查找是O(1)而过于挑剔？

Answer 1

正如您链接的答案所提到的，对于没有固有排序的哈希表，没有办法更有效地做到这一点。(使用对象的哈希代码没有帮助，因为除非您使用了备用哈希器，否则每个HashMap都使用不同的哈希函数来防止提交故意冲突的哈希密钥的拒绝服务攻击。(

您可以对算法进行一个高级改进：迭代两个哈希表中较小的，因为这需要最少的查找。

---

如果您有一个排序的集合，例如BTreeMap，那么itertools::Itertools::merge_join_by可以帮助您实现排序数据的合并：

use std::collections::BTreeMap;
use itertools::{Itertools, EitherOrBoth};
fn main() {
let mut map_a = BTreeMap::<&str, i32>::new();
map_a.insert("foo", 1);
map_a.insert("bar", 2);
map_a.insert("qux", 3);
map_a.insert("quux", 4);

let mut map_b = BTreeMap::<&str, i32>::new();
map_b.insert("foo", 5);
map_b.insert("bar", 6);
map_b.insert("quuux", 7);
map_b.insert("quuuux", 8);

let joined_map = map_a
.into_iter()
.merge_join_by(map_b, |(key_a, _), (key_b, _)| Ord::cmp(key_a, key_b))
.filter_map(|elem| match elem {
// Keep only paired elements, discard all others (making this an inner join).
EitherOrBoth::Both((k, val_a), (_, val_b)) => Some((k, (val_a, val_b))),
_ => None,
})
.collect::<BTreeMap<&str, (i32, i32)>>();

println!("{:?}", joined_map);
}

如果映射的大小相当，则这是对单个查找的性能改进，因为BTreeMap的查找是O(log(n((，因此整个联接算法将是O(n-log(n((，而不是使用merge的O(n(，其中n是两个映射的最大大小。

另一方面，如果其中一个映射小得多，则在该较小的映射上迭代是更好的算法，因为如果n比m小log(n(的因子，则O(n-log(n((比O(m(好。

---

总之，有不止一种可能的算法，哪种算法最好取决于集合类型和相对集合大小。并且可以使用排序来加速联接，但只有当您已经具有排序性时，这才是有益的，而哈希映射中没有排序性。