时间戳

首页 > 解决方案 > 在 Rust 中内连接两个 `HashMap`

join - 在 Rust 中内连接两个 `HashMap`

问题描述

假设我们有两个std::collections::HashMap-s，比如说HashMap<K, V1>andHashMap<K, V2>和一个 function 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上找不到它的现有实现，这感觉不对。此外，不执行sort-merge join似乎不是最理想的，因为我们已经在下面有排序的哈希码。我在监督什么吗？还是因为无论如何都要查找而过于挑剔？HashMapO(1)

标签： joinrusthashmapinner-join

解决方案

正如您链接的答案所提到的，对于没有固有顺序的哈希表，没有办法更有效地做到这一点。（使用对象的散列码没有帮助，因为除非您使用了备用散列器，否则每个散列器都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）。

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

推荐阅读