在 Rust 中内部加入两个 HashMap

Question

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

如何对这些散列图执行内部联接，以便在它们的共享密钥上得到 HashMap<K, R> 结果？这里有一个 reference implementation 来说明我的意思：

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. Also, it seems suboptimal not to perform kind of sort-merge join，因为我们已经在 HashMap 下排序了哈希码。我在监督什么吗？或者只是因为查找 O(1) 太挑剔了？

Answer 1

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

您可以对该算法进行一项高级改进：迭代两个散列 table 的 smaller，因为这需要最少的查找.

如果你有一个排序的集合，比如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 是两个映射的 maximum 大小。

另一方面，如果其中一个地图小得多，那么迭代那个较小的地图是一个更好的算法，因为如果 n 更小，O(n log(n)) 比 O(m) 更好比 m 乘以 log(n) 倍。

总而言之，可能的算法不止一种，哪种算法最好取决于集合类型和相关集合大小。你可以使用排序来加速连接，但它只有在你已经有排序的情况下才有用，而你在 hash 映射中没有.

在 Rust 中内部加入两个 HashMap

Inner join two `HashMap`s in Rust

join

hashmap

inner-join

rust