Rust 中的内连接两个 `HashMap`

Question

假设我们有两个std::collections::HashMap-s，例如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)}

这工作得很好，我可以让它在 a 中通用，但我在标准库或crates.ioutils.rs中找不到它的现有实现，这感觉不太对劲。另外，不执行排序合并连接似乎不是最理想的，因为我们已经在下面排序了哈希码。我在监督什么吗？或者只是因为查找太挑剔了？HashMapO(1)

Answer 1

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

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

如果您有一个排序的集合，例如 a 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)) 而不是 O (n) 使用合并，其中 n 是两个映射的最大大小。

另一方面，如果其中一个映射小得多，则迭代该较小的映射是一种更好的算法，因为如果 n 比 m 小一个因子，则 O(n log(n)) 优于 O(m)的日志（n）。

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